zhangshun97/ai_gomocup

Here are some Python implementations of Gomoku AIs, including MCTS, Minimax and Genetic Alg.

ai_gomocup's Issues

MCTS的几个BUG

作者，您好！
我详细地阅读了您的MCTS实现五子棋的代码，其中发现了几个BUG。现提交于您。
BUG 1、当expand一个child node之后即可胜利（如current state已经四子相连，此时使得五子相连的child node，将该child node称为必胜的child node），必胜的child node的win percent居然小于1。
很明显您已经注意到了这个问题，所以您在选择最佳的child时候，写了如下的代码进行修正：
percent_wins, move = max( (child.win_num / child.sim_num + child.winner, child.move) for child in self.root.children ) # choose a move with highest winning rate
您添加了一个child.winner项，这样可以使得必胜的child node的win percent大于1而被选中。
然而，您并没有从根本上解决这个BUG。
这个BUG的根源在于：当expand一个child node必胜的情况下，该child node不需要继续被select和expand了。您的代码中并没有这一部分，造成已经五子相连的child node还在以一定概率被select和expand，造成在simulate中有可能出现六子相连和七子相连的情况。这些大于五子相连的情况并不被您的代码判断为win，通过back propagation后使得必胜的child node的win percent小于1。
解决这个BUG有两种思路：1）、在select的时候，对于必胜的child node不再进行选择，可以通过将其UCB值设置为0实现；2）、在判断win or not的时候，对于五子以上相连的情况，依然判断为win。两种都很容易修改，但是明显方法1）效率更高。
BUG 2、您代码中设置的参数confidence在计算UCB的时候并没用到。
按理说confidence应该在计算UCB中用于平衡exploration和exploitation，是可调节的参数。