第 11 章：不可战胜的井字棋（Unbeatable tic-tac-toe）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 11。维护者已确认本书可翻译并发布用于学习研究。
本章通过开发一个玩井字棋的交互式程序，说明到目前为止介绍过的概念。我们先实现一个允许两名人类玩家互相对战的版本，然后开发一个使用博弈树和 minimax 算法的计算机玩家，保证它不可战胜，也就是说，总能获胜或打成平局。
11.1 引言（Introduction）
井字棋（tic-tac-toe，也称 noughts and crosses）传统上在一个最初为空的 3 x 3 网格上进行：
| |
| |
| |
两名玩家 O 和 X 轮流把自己的标记放在网格中的空白位置。第一个把自己的三个标记连成水平、垂直或对角线的玩家获胜。例如，下面的网格底行有三个 X，因此 X 获胜：
|O|O
O|X|O
X|X|X
如果网格被完全填满，但没有任何玩家获胜，那么游戏以平局结束，如下面的例子所示：
O|O|X
X|X|O
O|X|O
如果以完美方式进行游戏，也就是每一步都总是走出最佳可能移动，那么无论先手还是后手，玩家总能强制达成平局。本章余下部分展示如何在 Haskell 中实现一个完美的井字棋玩家。
11.2 基本声明（Basic declarations）
首先导入一些标准库。它们提供本实现中会使用的字符函数、列表函数和输入输出动作：
import Data.Char
import Data.List
import System.IO
与其假设井字棋网格固定为 3 x 3，不如允许网格大小被修改为任何大于零的整数值：
size :: Int
size = 3
我们把网格表示为玩家值的列表的列表，并假设每个内部列表以及外部列表的长度都是 size：
type Grid = [[Player]]
接着，玩家值要么是 O，要么是 X，其中额外的值 B 表示尚未被占用的空白位置：
data Player = O | B | X
deriving (Eq, Ord, Show)
例如，上一节中的获胜网格可以表示为 [[B,O,O],[O,X,O],[X,X,X]] :: Grid。上面的 deriving 子句确保玩家值支持标准相等和排序运算符，并且可以显示到屏幕上。回忆一下，构造子的顺序由它们在数据声明中的位置决定，因此有 O < B < X。当我们考虑 minimax 算法时，这一点会很重要。
下一位玩家只需在 O 和 X 之间切换即可。空白值 B 的情况也包含进来以保持完整，尽管这个函数永远不应该应用到该值上：
next :: Player -> Player
next O = X
next B = B
next X = O
11.3 网格辅助函数（Grid utilities）
我们会使用若干井字棋网格上的辅助函数。首先，空网格通过复制空白玩家值来创建一个空行，然后复制这一行来创建空网格：
empty :: Grid
empty = replicate size (replicate size B)
反过来，如果网格中的所有玩家值都不是空白，那么这个网格就是满的：
full :: Grid -> Bool
full = all (/= B) . concat
像上面这个定义一样，先把 concat 应用于网格，将其展平成单个列表，然后再处理其中的玩家值，这个思路会在后面定义的多个函数中使用。例如，可以通过比较展平网格中 O 和 X 的数量来判断轮到谁行动：
turn :: Grid -> Player
turn g = if os <= xs then O else X
where
os = length (filter (== O) ps)
xs = length (filter (== X) ps)
ps = concat g
注意，turn empty = O 意味着我们假设玩家 O 先手；在最终实现中，它会是人类玩家。
现在转向判断游戏是否已经获胜，也就是某位玩家是否在网格的任意行、列或任意一条对角线上拥有完整的一条线。使用局部定义提高可读性后，这个思路可以直接翻译成判断某位玩家是否在网格中获胜的函数：
wins :: Player -> Grid -> Bool
wins p g = any line (rows ++ cols ++ dias)
where
line = all (== p)
rows = g
cols = transpose g
dias = [diag g, diag (map reverse g)]
上面使用的函数 transpose :: [[a]] -> [[a]] 由库 Data.List 提供。它接收一个表示为行列表的网格，并沿着从左上到右下的主对角线翻转它，使列变成行，行变成列。例如：
> transpose [[1,2,3],[4,5,6],[7,8,9]]
[[1,4,7],[2,5,8],[3,6,9]]
接着，函数 diag 返回一个网格的主对角线：
diag :: Grid -> [Player]
diag g = [g !! n !! n | n <- [0..size-1]]
另一条从右上到左下的对角线，可以像上面 wins 的定义那样，先反转网格中的每一行再取得。最后，可以定义一个函数判断是否有任意一位玩家获胜：
won :: Grid -> Bool
won g = wins O g || wins X g
11.4 显示网格（Displaying a grid）
为了把井字棋网格显示到屏幕上，我们希望定义一个具有如下示例行为的函数：
> putGrid [[B,O,O],[O,X,O],[X,X,X]]
| |
| O | O
| |
-----------
| |
O | X | O
| |
-----------
| |
X | X | X
| |
这种行为可以很容易通过函数组合实现：
putGrid :: Grid -> IO ()
putGrid =
putStrLn . unlines . concat . interleave bar . map showRow
where bar = [replicate ((size*4)-1) '-']
也就是说，先用 showRow 把每一行转换为字符串列表，再用 interleave 在每行之间插入水平分隔线，然后用 concat 展平得到的嵌套列表结构，再用库函数 unlines :: [String] -> String 在每一行末尾加上换行字符并连接所有字符串，最后用 putStrLn 把得到的字符串显示到屏幕上。
接着，函数 showRow 把一行转换为字符串列表，并在每个条目之间放入长度为三的竖线：
showRow :: [Player] -> [String]
showRow = beside . interleave bar . map showPlayer
where
beside = foldr1 (zipWith (++))
bar = replicate 3 "|"
上面使用的库函数 foldr1 与 foldr 类似，但只能应用于非空列表；而 zipWith 与 zip 类似，只是会把给定函数应用于结果列表中的每一对值。例如，showRow [O,B,X] 返回下面的列表：
[" | | ",
" O | | X ",
" | | "]
剩下两个函数只是把玩家值转换为字符串列表，并把一个值插入到列表每两个元素之间：
showPlayer :: Player -> [String]
showPlayer O = [" ", " O ", " "]
showPlayer B = [" ", " ", " "]
showPlayer X = [" ", " X ", " "]
interleave :: a -> [a] -> [a]
interleave x [] = []
interleave x [y] = [y]
interleave x (y:ys) = y : x : interleave x ys
11.5 落子（Making a move）
为了识别玩家在游戏中希望落子的位置，我们用自然数为网格中的每个位置编号，从左上角的零开始，然后依次沿每一行前进：
0 1 2
3 4 5
6 7 8
尝试在某个特定编号处落子时，如果该编号在适当范围内，并且对应位置当前为空，那么这次移动有效：
valid :: Grid -> Int -> Bool
valid g i = 0 <= i && i < size^2 && concat g !! i == B
现在定义一个函数，把移动应用到网格上。为了考虑移动可能无效的情况，我们返回一列网格作为结果，约定单元素列表表示成功应用移动，空列表表示失败：
move :: Grid -> Int -> Player -> [Grid]
move g i p =
if valid g i then [chop size (xs ++ [p] ++ ys)] else []
where (xs,B:ys) = splitAt i (concat g)
也就是说，如果移动有效，就在落子编号处拆分网格中的玩家值列表，用给定玩家替换空白玩家值，然后再次重建网格。库函数 splitAt 会在给定编号处把列表分成两部分，而辅助函数 chop 会把列表拆分为给定长度的最大分段：
chop :: Int -> [a] -> [[a]]
chop n [] = []
chop n xs = take n xs : chop n (drop n xs)
11.6 读取数字（Reading a number）
为了从人类玩家那里读取网格编号，我们定义函数 getNat，它显示提示并从键盘读取自然数。它的定义方式与第 10 章尼姆游戏中的函数 getDigit 类似，只是它读取的是自然数而不是单个数字：
getNat :: String -> IO Int
getNat prompt = do putStr prompt
xs <- getLine
if xs /= [] && all isDigit xs then
return (read xs)
else
do putStrLn "ERROR: Invalid number"
getNat prompt
上面使用的函数 isDigit :: Char -> Bool 由库 Data.Char 提供，用于判断字符是否为数字字符。
11.7 人类对战人类（Human vs human）
现在已经拥有实现两名人类玩家井字棋所需的机制。我们定义一个动作，用两个相互递归的函数实现游戏，这两个函数都把当前网格和玩家作为参数：
tictactoe :: IO ()
tictactoe = run empty O
第一个函数只是显示网格并调用第二个函数：
run :: Grid -> Player -> IO ()
run g p = do cls
goto (1,1)
putGrid g
run' g p
屏幕辅助函数 cls 和 goto 是第 10 章为生命游戏定义的。接着，第二个函数使用一系列守卫判断游戏是否结束；如果没有结束，就提示玩家移动。如果移动无效，就显示错误消息并重新提示该玩家；否则用更新后的棋盘和下一位玩家调用第一个函数：
run' :: Grid -> Player -> IO ()
run' g p | wins O g = putStrLn "Player O wins!\n"
| wins X g = putStrLn "Player X wins!\n"
| full g = putStrLn "It's a draw!\n"
| otherwise =
do i <- getNat (prompt p)
case move g i p of
[] -> do putStrLn "ERROR: Invalid move"
run' g p
[g'] -> run g' (next p)
辅助函数 prompt 定义如下：
prompt :: Player -> String
prompt p = "Player " ++ show p ++ ", enter your move: "
现在你可以找一位朋友试试这个游戏。与所有扩展示例一样，代码可以从本书网站获取。
11.8 博弈树（Game trees）
现在展示如何基于博弈树开发一个井字棋计算机玩家。基本思路是构建一种树结构，用它捕获从当前网格出发游戏可能继续进行的所有方式，然后用这棵树决定下一步的最佳移动。
举例来说，假设给定下面的井字棋网格，现在轮到玩家 O 移动：
X| |
O|O|X
X|O|
玩家可以把标记放在剩余三个空白位置中的任何一个，也就是位置 1、2 和 8，从而得到三个可能的后续网格。随后轮到 X 移动，我们对这三个网格分别重复同样的过程，并在出现胜者或网格已满时停止。通过这种方式，可以从起始网格产生一棵博弈树。
对于这个例子，可以看到：如果游戏沿着树的最左或最右分支推进，玩家 X 会获胜；否则玩家 O 会获胜。因此，博弈树表明玩家 O 的最佳下一步，是树顶端三个可能移动中间的那个，因为它保证 O 获胜，而另外两个可能的下一步都可能导致 X 获胜。
表示这种树的合适类型可以声明如下：
data Tree a = Node a [Tree a]
deriving Show
也就是说，给定类型的树是一个节点，其中包含该类型的一个值和一列子树。关于这个声明还需要注意三点。首先，它并不特定于井字棋网格，而是允许在节点中存储任意类型的值；当我们考虑 minimax 算法时，这一点会很重要，因为该算法会为博弈树中的每个网格标注额外信息。其次，没有叶子构造子，因为拥有空子树列表的节点可以扮演这个角色；这样避免了叶子拥有两种可能表示，否则会让树上函数的定义变复杂。最后，deriving 子句确保树可以显示到屏幕上。
使用上面的树类型，可以很直接地定义一个函数：从给定起始网格和玩家构建博弈树。我们只需把起始网格作为根节点的值，然后对当前玩家走出一个有效移动后产生的每个网格，递归构建博弈树，并用下一位玩家继续这个过程：
gametree :: Grid -> Player -> Tree Grid
gametree g p = Node g [gametree g' (next p) | g' <- moves g p]
接着，返回有效移动列表的函数 moves 定义如下。它先检查游戏是否已经结束；如果已经结束，就返回空网格列表，这会在 gametree 中停止递归。否则，返回在空白位置落子后得到的所有网格：
moves :: Grid -> Player -> [Grid]
moves g p | won g = []
| full g = []
| otherwise = concat [move g i p | i <- [0..((size^2)-1)]]
11.9 裁剪树（Pruning the tree）
可以想象，博弈树可能变得非常大。因此，有时需要把博弈树裁剪到特定深度，以限制构建树所需的时间和内存。为此，我们定义一个函数，把树裁剪到给定深度：
prune :: Int -> Tree a -> Tree a
prune 0 (Node x _) = Node x []
prune n (Node x ts) = Node x [prune (n-1) t | t <- ts]
例如，prune 5 (gametree empty O) 会产生一棵从空网格出发、玩家 O 先手、最大深度为五的博弈树。注意，在惰性求值下，只有 prune 函数实际需要的那部分树会被产生。也就是说，这个例子中深度超过五的网格永远不会由 gametree 生成。
我们还定义一个常量，指定博弈树的最大深度。在现代机器上，为 3 x 3 网格生成整棵树是可行的，因此默认深度设为这种大小的网格所需的最大值。对于更大的网格，可能需要降低这个值。
depth :: Int
depth = 9
11.10 Minimax 算法（Minimax algorithm）
一旦产生了博弈树，就可以使用 minimax 算法确定最佳下一步。该算法首先以下列方式为树中的每个节点标注一个玩家值：
- 叶子节点（没有子树的节点）标注为此处的获胜玩家；如果没有获胜玩家，则标注为空白玩家；
- 其他节点（带有子树的节点）根据此处轮到谁行动，标注为下一层子节点玩家标注中的最小值或最大值：在玩家
O的回合取子标注的最小值，在玩家X的回合取最大值。
例如，对上一节中的博弈树应用该算法，会得到一棵玩家标注树。最左侧叶子标注为 X，因为玩家 X 在该处获胜；而根节点标注为 O，因为此处轮到玩家 O 移动，因此取子标注 X、O 和 X 的最小值。在排序 O < B < X 下，这个最小值就是 O。
使用一系列守卫决定标注后，minimax 算法可以直接翻译为标注博弈树的函数。其中局部定义 ts' 会把算法递归应用于节点的每棵子树，而 ps 会从得到的树中选出顶部标注：
minimax :: Tree Grid -> Tree (Grid,Player)
minimax (Node g [])
| wins O g = Node (g,O) []
| wins X g = Node (g,X) []
| otherwise = Node (g,B) []
minimax (Node g ts)
| turn g == O = Node (g, minimum ps) ts'
| turn g == X = Node (g, maximum ps) ts'
where
ts' = map minimax ts
ps = [p | Node (_,p) _ <- ts']
一旦博弈树以这种方式完成标注，minimax 算法下的最佳下一步就是移动到任何与根节点拥有相同标注的网格。因此，对于我们的示例树，最佳移动是从初始网格出发的三个可能移动中的第二个，因为它会到达一个与根节点拥有相同标注的网格，也就是玩家 O。这是该点的最佳移动，因为它保证玩家 O 获胜，而另外两个可能移动都可能导致玩家 X 获胜。
把所有组件组合起来，现在可以定义一个函数，返回给定井字棋网格和玩家的最佳下一步：
bestmove :: Grid -> Player -> Grid
bestmove g p = head [g' | Node (g',p') _ <- ts, p' == best]
where
tree = prune depth (gametree g p)
Node (_,best) ts = minimax tree
也就是说，先构建到指定深度的博弈树，再应用 minimax 算法为树标注，最后选择一个玩家标注与根节点相同的网格。总是至少存在一个“最佳移动”，因为从非空有限列表中选择最小值或最大值，总会得到列表中存在的一个值。如果存在多个最佳移动，上面的定义只是选择其中第一个。
11.11 人类对战计算机（Human vs computer）
现在可以很直接地修改前面的井字棋程序，让计算机扮演其中一位玩家。与第 9 章中的倒计时程序一样，我们使用 GHC 编译器提高性能，并用名为 main 的顶层动作定义程序：
main :: IO ()
main = do hSetBuffering stdout NoBuffering
play empty O
函数 hSetBuffering 由库 System.IO 提供。上面用它关闭输出缓冲，而 GHC 默认会打开输出缓冲。和之前一样，游戏本身通过两个相互递归的函数实现，只是现在玩家 X 是计算机玩家：
play :: Grid -> Player -> IO ()
play g p = do cls
goto (1,1)
putGrid g
play' g p
play' :: Grid -> Player -> IO ()
play' g p | wins O g = putStrLn "Player O wins!\n"
| wins X g = putStrLn "Player X wins!\n"
| full g = putStrLn "It's a draw!\n"
| p == O =
do i <- getNat (prompt p)
case move g i p of
[] -> do putStrLn "ERROR: Invalid move"
play' g p
[g'] -> play g' (next p)
| p == X =
do putStr "Player X is thinking... "
(play $! (bestmove g p)) (next p)
函数 play' 定义中使用的运算符 $! 会在调用函数 play 之前强制求值计算机玩家的最佳移动。如果没有这样做，在惰性求值下，清屏与在 play 中显示网格之间可能会有一段延迟，因为最佳移动会在那时才被计算。第 15 章在更详细讨论惰性求值时，会进一步讨论这种控制求值顺序的方式。
最后，如果所有定义都放在名为 tictactoe.hs 的文件中，就可以编译程序并运行游戏：
$ ghc -O2 tictactoe.hs
[1 of 1] Compiling Main
Linking tictactoe ...
$ ./tictactoe
| |
| |
| |
-----------
| |
| |
| |
-----------
| |
| |
| |
Player O, enter your move:
在一台合理的现代机器上，计算机第一步大约需要一秒，后续移动会随着博弈树变小而逐渐变快。注意，因为计算机总是从最佳移动列表中选择第一个移动，它并不总会选择最快获胜路径，但保证不可战胜。
11.12 章注（Chapter remarks）
对于大小为 3 x 3 的井字棋网格，生成完整博弈树是可行的。对于更大的网格，除了限制树的最大深度之外，还可以使用 alpha-beta 剪枝 [16] 来减小树的大小。该技术会避免生成那些在 minimax 算法下不可能通向最佳下一步的博弈树部分。
11.13 练习（Exercises）
-
使用函数
gametree验证：从空网格开始的3 x 3井字棋完整博弈树共有 549,946 个节点，并且该树的最大深度为 9。 -
我们的井字棋程序总是从最佳移动列表中选择第一个移动。修改最终程序，让它从最佳移动列表中随机选择一个移动，使用
System.Random中的函数randomRIO :: (Int,Int) -> IO Int在给定范围内生成随机整数。 -
另一种方式是，修改最终程序，让它选择试图最快获胜的移动，方法是计算结果博弈树的深度，并选择导致树深度最小的移动。
-
修改最终程序，使其：
a. 让用户决定自己想先手还是后手；
b. 允许胜利连线的长度也可以修改；
c. 只生成一次博弈树，而不是为每一步都生成；
d. 使用 alpha-beta 剪枝减小博弈树大小。
练习 1 和 2 的解答见附录 A。