On Jan 14, 2009, at 10:55 PM, Daniel Waeber wrote:
Accessing the AMAF values depends on your implementation. The
following is a code-snippet from my MCTS reference implementation
that
updates the AMAF values in the tree:
if (_useAMAF)
{
IntStack playoutMoves = _searchAdministration.getMoveStack();
byte color = _monteCarloAdministration.getColorToMove();
int start = _monteCarloAdministration.getMoveStack().getSize();
int end = playoutMoves.getSize();
double weight = 1.0;
double weightDelta = 1.0 / (end - start + 1); // Michael Williams'
idea to use decreasing weights
GoArray.clear(_weightMap);
GoArray.clear(_colorMap);
for (int i=start; i<end; i++)
{
int moveXY = playoutMoves.get(i);
if (_colorMap[moveXY]==0)
{
_colorMap[moveXY] = color;
_weightMap[moveXY] = weight;
}
weight -= weightDelta;
color = opposite(color);
}
until here it's clear to me.
OK, I hope so. Until here it's pretty much the same as in the original
AMAF ref-bot without tree-search as defined by Don.
while (playoutNode!=null)
{
color = opposite(playoutNode.getContent().getMove().getColor());
boolean playerWins = (blackWins && color==BLACK) || (!blackWins
&& color==WHITE);
double score = playerWins ?
MonteCarloTreeSearchResult.MAX_SCORE :
MonteCarloTreeSearchResult.MIN_SCORE;
for (int i=0; i<playoutNode.getChildCount(); i++)
{
TreeNode<MonteCarloTreeSearchResult<MoveType>> nextNode =
playoutNode.getChildAt(i);
MonteCarloTreeSearchResult<MoveType> result =
nextNode.getContent();
GoMove move = (GoMove) result.getMove();
int xy = move.getXY();
if (_colorMap[xy]==color)
result.increaseVirtualPlayouts(_weightMap[xy]*score,_weightMap[xy]);
if i understand this code correctly, it updates the amaf vaules of all
direct children of the playoutNode according to the weight/color maps.
Yes.
And that update is done for all nodes on the selected path.
Yes, until the root, which is the starting position from which the
search is performed.
}
playoutNode = playoutNode.getParent();
First of all, I miss an weight/colorMap update for xy here. Souldn't
the
move of the current playoutNode be considered as an amaf move for all
the nodes below this one?
This is in fact done in this code, see further remarks below.
}
}
But, most of all, I miss that the code only updates the amaf values of
all direct children, and not of all nodes n below the playoutNode,
where
there is no play at n.move on the path between n and the playoutNode.
Finding all these nodes n would be a costy thing to do, but wouldn't
that be the "right" thing to do? Implementing a realistic subset of
RAVE
is another story, but first of all I want to understand the pure
concept
of RAVE.
You have to understand that the 'start' variable really starts at the
root from the position for which we do the search. So all the moves
'below' the playoutNode are also taken into account. The check in the
earlier part "if (_colorMap[moveXY]==0)" makes sure there's no move
between the playoutNode and the n.move as you call it.
That is, if I understand you correctly. Because I'm not quite sure
what you mean by 'finding all these nodes n'. This is not a sub-set of
RAVE as I understand it. What you see in the code is the accumulation
of the AMAF values after each playout. The RAVE value is calculated
using these values when comparing move-candidates, which is in an
altogether different place. (The MonteCarloTreeSearchResult class in
my project).
I'm afraid I haven't made things much clearer for you.
Mark
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
