编辑:如果你想看看是否能让AI表现得更好,我上传了完整的源代码:https://www.dropbox.com/s/ous72hidygbnqv6/MCTS_TTT.rar
编辑:搜索搜索空间,并找到导致丢失的移动。但是由于UCT算法,导致损失的移动并不经常被访问。
为了了解MCTS (蒙特卡洛树搜索),我使用该算法为经典游戏tic-tac-toe制作了一个AI。我已经使用以下设计实现了该算法:
树策略基于UCT,默认策略是执行随机移动,直到游戏结束。我在我的实现中观察到的是,计算机有时会做出错误的移动,因为它无法“看到”某个特定的移动将直接导致损失。
例如:
请注意,动作6(红色方块)的值略高于蓝色方块,因此计算机会标记此点。我认为这是因为游戏策略是基于随机移动的,因此很有可能人类不会在蓝框中放入"2“。如果玩家没有在蓝色框中输入2,则计算机将获得胜利。
My Questions
1)这是MCTS的已知问题还是实施失败的结果?
2)可能的解决方案是什么?我正在考虑限制选拔阶段的动作,但我不确定:-)
核心MCTS的代码:
//THE EXECUTING FUNCTION
public unsafe byte GetBestMove(Game game, int player, TreeView tv)
{
//Setup root and initial variables
Node root = new Node(null, 0, Opponent(player));
int startPlayer = player;
helper.CopyBytes(root.state, game.board);
//four phases: descent, roll-out, update and growth done iteratively X times
//-----------------------------------------------------------------------------------------------------
for (int iteration = 0; iteration < 1000; iteration++)
{
Node current = Selection(root, game);
int value = Rollout(current, game, startPlayer);
Update(current, value);
}
//Restore game state and return move with highest value
helper.CopyBytes(game.board, root.state);
//Draw tree
DrawTree(tv, root);
//return root.children.Aggregate((i1, i2) => i1.visits > i2.visits ? i1 : i2).action;
return BestChildUCB(root, 0).action;
}
//#1. Select a node if 1: we have more valid feasible moves or 2: it is terminal
public Node Selection(Node current, Game game)
{
while (!game.IsTerminal(current.state))
{
List<byte> validMoves = game.GetValidMoves(current.state);
if (validMoves.Count > current.children.Count)
return Expand(current, game);
else
current = BestChildUCB(current, 1.44);
}
return current;
}
//#1. Helper
public Node BestChildUCB(Node current, double C)
{
Node bestChild = null;
double best = double.NegativeInfinity;
foreach (Node child in current.children)
{
double UCB1 = ((double)child.value / (double)child.visits) + C * Math.Sqrt((2.0 * Math.Log((double)current.visits)) / (double)child.visits);
if (UCB1 > best)
{
bestChild = child;
best = UCB1;
}
}
return bestChild;
}
//#2. Expand a node by creating a new move and returning the node
public Node Expand(Node current, Game game)
{
//Copy current state to the game
helper.CopyBytes(game.board, current.state);
List<byte> validMoves = game.GetValidMoves(current.state);
for (int i = 0; i < validMoves.Count; i++)
{
//We already have evaluated this move
if (current.children.Exists(a => a.action == validMoves[i]))
continue;
int playerActing = Opponent(current.PlayerTookAction);
Node node = new Node(current, validMoves[i], playerActing);
current.children.Add(node);
//Do the move in the game and save it to the child node
game.Mark(playerActing, validMoves[i]);
helper.CopyBytes(node.state, game.board);
//Return to the previous game state
helper.CopyBytes(game.board, current.state);
return node;
}
throw new Exception("Error");
}
//#3. Roll-out. Simulate a game with a given policy and return the value
public int Rollout(Node current, Game game, int startPlayer)
{
Random r = new Random(1337);
helper.CopyBytes(game.board, current.state);
int player = Opponent(current.PlayerTookAction);
//Do the policy until a winner is found for the first (change?) node added
while (game.GetWinner() == 0)
{
//Random
List<byte> moves = game.GetValidMoves();
byte move = moves[r.Next(0, moves.Count)];
game.Mark(player, move);
player = Opponent(player);
}
if (game.GetWinner() == startPlayer)
return 1;
return 0;
}
//#4. Update
public unsafe void Update(Node current, int value)
{
do
{
current.visits++;
current.value += value;
current = current.parent;
}
while (current != null);
}
发布于 2014-05-23 18:52:03
好的,我通过添加代码解决了这个问题:
//If this move is terminal and the opponent wins, this means we have
//previously made a move where the opponent can always find a move to win.. not good
if (game.GetWinner() == Opponent(startPlayer))
{
current.parent.value = int.MinValue;
return 0;
}
我认为问题在于搜索空间太小。这确保了即使选择确实选择了实际上是终止的移动,该移动也不会被选择,而是使用资源来探索其他移动:)。
现在AI和AI总是并驾齐驱,Ai作为人类是不可能被击败的:-)
发布于 2015-06-24 01:49:09
我认为您的答案不应标记为已接受。对于Tic-Tac-Toe,搜索空间相对较小,应该在合理的迭代次数内找到最优动作。
看起来您的更新函数(反向传播)为不同树级别的节点添加了相同数量的奖励。这是不正确的,因为当前玩家的状态在不同的树级别上是不同的。
我建议您看看这个示例中的UCT方法中的反向传播:http://mcts.ai/code/python.html
您需要根据前一个玩家在特定级别(示例中为node.playerJustMoved)计算出的奖励来更新节点的总奖励。
发布于 2014-05-22 17:56:56
我的第一个猜测是,你的算法的工作方式选择了最有可能赢得比赛的步骤(在端节点中拥有最多的胜利)。
因此,如果我是正确的,你的例子显示了AI“失败”,因此不是一个“bug”。这种评估移动的方法是从敌人的随机移动中获得收益。这种逻辑是失败的,因为对于玩家来说,采取哪一步来赢得比赛是显而易见的。
因此,您应该擦除所有节点,其中包含玩家的win的下一个节点。
也许我错了,这只是我的初步猜测…
https://stackoverflow.com/questions/23803186
复制相似问题