Tree Class Reference

Uct tree. More...

#include <uct.h>

List of all members.

Public Member Functions
	Tree (Node *root)
	Constructor with predefined root.
	Tree (player_t firstPlayer)
	Constructor which creates root node.
	~Tree ()
	Destructor.
void	syncMaster ()
	Commits the tree to the master tree.
void	expandNode (Node *node, const StepArray &steps, uint len, const HeurArray *heurs=NULL)
	Node expansion.
void	expandNodeLimited (Node *node, const Move &move)
void	uctDescend ()
	UCT-based descend to next level.
void	randomDescend ()
	Random descend.
void	firstChildDescend ()
	First child descend.
Node *	findBestMoveNode (Node *subTreeRoot)
	Finds the best move node.
Move	findBestMove (Node *bestMoveNode)
	Move for given Node.
void	updateHistory (float)
	Backpropagation of playout sample.
void	historyReset ()
	History reset.
Node *	root ()
	Gets tree root(bottom of history stack).
Node *	actNode ()
	Gets the actual node (top of history stack).
int	getNodesNum ()
	Nodes num getter.
int	getNodesPrunedNum ()
	Nodes pruned getter.
int	getNodesExpandedNum ()
	Nodes expanded getter.
string	toString ()
	String representation of the tree.
string	pathToActToString (bool onlyLastMove=false)
	Path to actNode() to string.
void	updateTT (Node *father, const Board *board)
	Updates Transposition tables.
Private Member Functions
	Tree ()
	Simple constructor.
void	init ()
	Constructor wide init.
Static Private Member Functions
static int	calcNodeLevel (Node *father, const Step &step)
	Level calculation.
Private Attributes
Node *	history [2 *UCT_MAX_DEPTH]
	Simulation history.
uint	historyTop
	Index of actual node in the history.
int	nodesExpandedNum_
	Expanded nodes.
int	nodesNum_
	Nodes in the tree.
int	nodesPrunedNum_
	Number of pruned nodes in tt.
TWsteps	twSteps_
	Map of tree wide steps.
TT *	tt_
	Transposition table.
Friends
class	Uct

---

Detailed Description

Uct tree.

---

Constructor & Destructor Documentation

Tree::Tree

(

Node *

root

)

Constructor with predefined root.

Sets the root to be node. Used in tree mockups.

Tree::Tree

(

player_t

firstPlayer

)

Constructor which creates root node.

Root node is created(bottom of history stack) with given player.

Tree::~Tree

(

)

Destructor.

Recursively deletes the tree.

Tree::Tree

(

)

[private]

Simple constructor.

Sets the root to NULL.

---

Member Function Documentation

int Tree::calcNodeLevel	(	Node *	father,
		const Step &	step
	)			[static, private]

Level calculation.

Parameters:

	father	Node father
	step	Step representid in node.

Returns:

Level(move num) belonging to node.

void Tree::expandNode	(	Node *	node,
		const StepArray &	steps,
		uint	len,
		const HeurArray *	heurs = NULL
	)

Node expansion.

Creates children for every given step.

Parameters:

	steps	- Given steps (already filtered through repetition tests, virtual pass test, transposition tables).
	len	- Length of steps array.
	heurArray	- Heuristics connected to the steps.

Move Tree::findBestMove

(

Node *

bestMoveNode

)

Move for given Node.

After finding best node. This method finds appropriate move for this node in the tree.

Returns:

best move in search.

Node * Tree::findBestMoveNode

(

Node *

subTreeRoot

)

Finds the best move node.

Node for the best move in the subtree under subTreeRoot. BFS in the tree topmost level(relative to subTreeRoot) of the tree..

void Tree::firstChildDescend

(

)

First child descend.

Always descends to first child..i

void Tree::historyReset

(

)

History reset.

Performed after updateHistory. Points actual node to the root.

string Tree::pathToActToString

(

bool

onlyLastMove = false

)

Path to actNode() to string.

Returns string with steps leading to actNode().

Parameters:

onlyLastMove

if true then only steps from last move are returned.

void Tree::randomDescend

(

)

Random descend.

Mostly for testing purposes.

void Tree::uctDescend

(

)

UCT-based descend to next level.

Crucial method implementing core idea of UCT algorithm - the descend by UCB1 formula. History is updated - simulating the descend.

void Tree::updateTT	(	Node *	father,
		const Board *	board
	)

Updates Transposition tables.

Every children of given father is checked: if it's position is unique in TT it's added if it's position already exists in TT, it's children are linked

Parameters:

father

it's children will get updated

---

Member Data Documentation

Node* Tree::history[2 *UCT_MAX_DEPTH] [private]

Simulation history.

Hardcoded length for speedup - in playout check for overflow.

int Tree::nodesExpandedNum_ [private]

Expanded nodes.

int Tree::nodesNum_ [private]

Nodes in the tree.

int Tree::nodesPrunedNum_ [private]

Number of pruned nodes in tt.

TT* Tree::tt_ [private]

Transposition table.

TWsteps Tree::twSteps_ [private]

Map of tree wide steps.

Every step with its value (average of all values in the tree) is stored here. This is used to init new node.

---

The documentation for this class was generated from the following files:

• uct.h
• uct.cpp