電腦圍棋的算法UCT語言Java實現
/* same as on main page, but translated to java */
// CHANGED: randomresult non-global
CLASS Node
{
public int wins=0;
public int visits=0;
public Move move=null;
public Node bestNode=null;
public Node child=null;
public Node sibling=null;
Node(Move m) 
{
this.m=m;
}
public void setBest()
{
Node next = child;
Node best = null;
double best_winrate=-1;
double winrate; // 0..1
while (next!=null) 
{ // for all children
winrate = ((double)next.wins) / next.visits;
if (winrate>best_winrate)
{
best=next;
best_winrate = winrate;
}
next = next.sibling;
}
bestNode=best;
}
double getWinRate() 
{
if (visits>0) return (double)wins / visits;
else return 0.5; /* should not happen */;
}
}//end of class Node

CLASS Board { /* BEGIN CLASS */
double UCTK = 1;
// Larger values give uniform search
// Smaller values give very selective search
Board clone;
public Node UCTSelect(Node node)
{
Node res=null;
Node next = node.child;
double best_uct=0;
while (next!=null) 
{ // for all children
double uctvalue;
if (next.visits > 0)
{
double winrate=next.getWinRate();
double uct = UCTK * Math.sqrt( Math.log(node.visits) / (5*next.visits) );
uctvalue = winrate + uct;
}
else 
{
// Always play a random unexplored move first
uctvalue = 10000 + 1000*Math.random();
}
if (uctvalue > best_uct)
{ // get max uctvalue of all children
best_uct = uctvalue;
res = next;
}
next = next.sibling;
}
return res;
}//end of UCTselect
// returns 0 or 1 (=randomresult)
int playSimulation(Node n) 
{
int randomresult=0;
if (n.visits==0)
{ // node exists, but no evaluation done yet (for this node)
randomresult = 1-clone.playRandomGame();
}
else
{
if (n.child == null)
createChildren(n);
Node next = UCTSelect(n); // select a move
if (next==null) { /* ERROR */ }
clone.makeMove(next.move);
randomresult = 1-playSimulation(next);
}
n.visits++;
n.wins+=randomresult;
if (n.child!=null)
n.setBest();
}//end of playSimulation
Move UCTSearch(int numsim)
{
for (int i=0;i<numsim;i++) 
{
clone.copyStateFrom(this);
playSimulation(root);
}
return root.bestNode.move;
}//end of UCTsearch
// NOT IMPLEMENTED YET: 
int size_MAX=19;
int[][] f = new int[size_MAX][size_MAX];
int game_turn_player=1;
void makeMove(int x, int y)
{
fx?y?=game_turn_player;
game_turn_player=3-game_turn_player;
}//end make move
public void makeRandomMove() 
{
int x=0;
int y=0;
while (true)
{
x=rand.nextInt(size_MAX);
y=rand.nextInt(size_MAX);
if (fx?y?==0 && isOnBoard(x,y)) break;
}
makeMove(x,y);
}//end of make randommove
int playRandomGame() 
{
return 0; // or 1
}end of playrandomgame
// returns: number childs created
void createChildren(Node parent) 
{
int cnt=0;
Node last=parent;
for (int i=0; i<size_MAX; i++)
for (int j=0; j<size_MAX; j++)
if (isOnBoard(i, j) && fi?j?==0) 
{
Node node=new Node(i, j);
if (cnt==0) last.child=node;
else last.sibling=node;
last=node;
cnt++;
}
return cnt;
}//end of createchildren
void copyStateFrom(Board b) 
{
}
} /* END CLASS board*/

搜索更多相關主題的帖子: Java UCT算法