上次的MiniMax算法虽然在效果上已经达到了预期的目的，即不可战胜的棋力，但在效率上仍然不够理想。电脑每次走步都得估计往下N层棋局的所有情况并估值，层数虽然可以控制，但在大棋局（如五子棋，象棋等）游戏中如此生成的博弈树分支叶子仍然相当庞大，由此有了在此基础上进行“剪枝”的改进算法–Alpha-beta剪枝算法（Alpha-Beta algorithms）。此算法主要优点在于其在边生成博弈树时候边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。

Read the rest of this entry »

这几天在用Python写Tic-Tac-Toe小游戏，顺便接触了一些简单的人机博弈算法，其实在算法方面我完全算是个新手，所以这也算是一个反复折腾学习的过程。而Tic-Tac-Toe应该算是人机博弈里最简单的应用了，最经典的算法是miniMax算法，也叫极大极小值算法，主要方法就是通过考虑双方博弈N步后，从所有可能的走法中选一步最佳的走法来走。
Read the rest of this entry »