井字棋系统设计

        人机对弈的难点在于当人走一步棋之后，计算机如何走下一步，即计算机如何找出最合适的位置去走棋。这就需要一定的算法，或者叫做计算机的 AI。对于井字棋、五子棋等两方较量的游戏来说，Minimax算法（极小极大算法）是最基本也是最常用的。算法的原理不在这里解释了，我们直接看该算法在井字棋中的应用。
        井字棋中，假设使用“X”的是人，使用“O”的是计算机。“X”方先走，设定X方的最大利益为正无穷（程序使用常量+INFINITY表示)，О方的最大利益为负无穷（程序中使用-INFINITY表示)，即X方和О方走的每步棋都要力图使自己的利益最大化，而使对方的利益最小化。这样我们称X方为MAX(因为他总是追求更大的值)，О方为MIN（它总是追求更小的值)，各自都为争取自己的最大获益而努力。现在举例说明，如图所示的棋局树:

         X方先走，有三种选择，如图4中第二层所示。假设X方选择最左边的走法，那么О方接下来将有5种走法，О方会选择最小化的走法，即值为-1的走法，因为它的最大利益是负无穷;同理，X方的另外两种走法会分别得到О方的最小值1和-2。这样，对于X方来说，三种走法会导致О方最小化值分别为-1、1、-2，X 方的最佳策略则是选择其中最大的，即第二层中间的走法，因为它的最大利益是正无穷，这就是极小极大算法的体现——X方的选择总是极大化，О方的选择总是极小化。
        对于其中那些值的是如何计算的，我们举例说明，比如对于第三层最左边的棋局，在这种状态下，如果把棋局空白处都填上X，则X共有6中3连子情况，即获胜情况;如果把空白处都填上O，则О共有5种3连子情况，所以结果是二者相减等于1。
        在具体走起过程中，MAX面对MIN最大获利中的最小值时，会选择其中最大的，比如图第二层小括 内的值都是第三层中能使MIN最大获利的最小值，这时候MAX选择其中最大的，这对 MAX最为有利，所以MAX方选择图4第二层中间的走法最好。同样道理，MIN也会一样，选择对自己最有利的，即MAX有可能获得的最大值。这时候，MIN在走棋时会考虑MAX方占据哪个位置对MAX最有利，然后MIN把这个位置先占了。有点难理解，其实就是抢先把对对手有利的位置抢占了。
        简单说，X方或者MAX方的走棋时由人来控制的，我们不仔细说了。对于О方或者MIN方，它走棋时要考虑哪个位置对X方最有利,然后把该位置占据，即О的最佳走棋就是X的最佳走棋。所以О在走棋之前，先站在X的角度寻找最佳走棋位置。后文中 minimax方法就是站在X角度来考虑极小极大算法，找到X的最佳走棋位置，然后由О方来占据该位置。
2、极小极大算法
整个算法包括如下几个部分:
        首先要有一个评估方法 gameState，对每走一步棋后的棋局进行评估，估值为WIN常量说明X方，即 MAX方获胜;估值为LOSE则О方，即 MIN方获胜;估值DRAW 为平局;估值为INPROGRESS，说明棋未走完;估值为DOUBLE_LINK，说明棋局中有两连子情况
        然后用一个minimax方法寻找在当前棋局状态下X方的最佳位置，X方的最佳位置就是当X走该位置后，О方所有走法中最小值里的最大值，如图中第二层X 的位置选择。当找到该位置后，由О方来抢先占据该位置。
        最后用两个递归方法 min和 max来遍历所有的棋局。min方法负责找出О方的最小值，如图第二层最左边的棋局会导致5中О方的走法，min方法就是找出这5种走法中的最小值。同理，max方法负责找出X方的最大值，如图第二层三种棋局中的中间棋局。