06-用井字棋测试极小化极大算法

8.2.3　用井字棋测试极小化极大算法

井字棋游戏十分简单，因此人类能够轻松找出对于给定棋局的绝对正确的走法。这样单元测试就很容易开发了。在代码清单8-10所示的代码段中，本章的极小化极大算法将迎接挑战，为3种不同的井字棋局查找下一步的正确走法。第一个棋局很容易，只需要考虑下一步如何赢棋。第二个棋局需要挡一手（block），而且AI必须阻止对手获胜。最后一个棋局的挑战性稍强一点，需要AI思考后面的两步棋。

代码清单8-10　tictactoe_tests.py

import unittest
from typing import List
from minimax import find_best_move
from tictactoe import TTTPiece, TTTBoard
from board import Move
class TTTMinimaxTestCase(unittest.TestCase):
    def test_easy_position(self):
        # win in 1 move
        to_win_easy_position: List[TTTPiece] = [TTTPiece.X, TTTPiece.O, TTTPiece.
          X, TTTPiece.X, TTTPiece.E, TTTPiece.O, TTTPiece.E, TTTPiece.E, TTTPiece.O]
        test_board1: TTTBoard = TTTBoard(to_win_easy_position, TTTPiece.X)
        answer1: Move = find_best_move(test_board1)
        self.assertEqual(answer1, 6)
    def test_block_position(self):
        # must block O's win
        to_block_position: List[TTTPiece] = [TTTPiece.X, TTTPiece.E, TTTPiece.E, 
          TTTPiece.E, TTTPiece.E, TTTPiece.O, TTTPiece.E, TTTPiece.X, TTTPiece.O]
        test_board2: TTTBoard = TTTBoard(to_block_position, TTTPiece.X)
        answer2: Move = find_best_move(test_board2)
        self.assertEqual(answer2, 2)
    def test_hard_position(self):
        # find the best move to win 2 moves
        to_win_hard_position: List[TTTPiece] = [TTTPiece.X, TTTPiece.E, TTTPiece.E, 
          TTTPiece.E, TTTPiece.E, TTTPiece.O, TTTPiece.O, TTTPiece.X, TTTPiece.E]
        test_board3: TTTBoard = TTTBoard(to_win_hard_position, TTTPiece.X)
        answer3: Move = find_best_move(test_board3)
        self.assertEqual(answer3, 1)
if __name__ == '__main__':
    unittest.main()

运行tictactoe_tests.py的时候，3个测试过程都应该都能顺利通过。

提示 　实现极小化极大算法并没有用太多的代码，而且该算法不但可以用于井字游戏，而且可以用于很多其他游戏。如果你想要为其他游戏实现极小化极大算法，那么走向成功的重要一点就是，创建与极小化极大算法设计方案相适应的数据结构，类似于 Board 类。学习极小化极大算法存在一个常见错误，即采用可修改的数据结构，这种数据结构在极小化极大算法的递归调用过程中会被改动，因此无法回到原始状态进行再次调用。