algorithm - Haskell - 如何使用列表 monad 在井字游戏中生成下一步

Question

我正在 Haskell 中为 n * n 棋盘实现一个井字游戏，我需要生成我可以从下一步行动中获得的所有棋盘配置。

我的板子定义如下:

data Cell = E
      | X  
      | O 
      deriving (Eq,Show)

type Row a = [a]
type Board = Row (Row Cell)

iniBoard :: Int -> Board
iniBoard n = let row = replicate n E in replicate n row

我可以确定给定的棋盘配置是否让玩家 x 获胜，所以我有

win :: Cell -> Board -> Bool
win E _   = False
win x brd = any full $ diags brd ++ rows brd ++ cols brd
where
    diags brd = mainDiag : [secondDiag]
    mainDiag = zipWith (!!) brd [0..]
    secondDiag = zipWith (!!) revBrd [0..]
    revBrd = do
        xs <- brd
        return (reverse xs)
    rows = id
    cols = transpose
    full xs = all (==x) xs

但我不知道如何生成玩家 x 下一步可以做出的所有棋盘配置。

我明白，我需要遍历所有单元格并检查，如果单元格为空，那么我可以在此处放置标记并返回新配置。如果我已经有获胜配置，那么就没有下一步，我必须返回空列表

我有这样的代码:

nxt :: Cell -> Board -> [Board]
nxt x brd = do
if (win x brd || win (switch x) brd)
    then
        []
    else
        undefined

我该怎么做，使用 list monad？感谢您的帮助!

Answer 1

与

picks :: [x] -> [([x], x, [x])]
picks [] = []
picks (x : xs) = ([] , x, xs) : [(x : sy, y, ys) | (sy, y, ys) <- picks xs]

(这是 this 的调整版本)，所有可能的下一个板都是

import Data.List.Split (chunksOf)

next :: Int -> Cell -> Board -> [Board]
next n who b =  
    picks (concat b) >>= \(sy, y, ys) ->
             case y of E -> [chunksOf n $ sy ++ [who] ++ ys] ;
                       _ -> []

其中 who 是 X 或 O 之一，或者是 course。

这只不过是一个过滤器，用于保留空的，同时在那些已经过滤的那些上绘制 map 。使用列表理解甚至更简单，

next n who b = [ chunksOf n $ sy ++ [who] ++ ys
                 | (sy, E, ys) <- picks $ concat b ]

picks 函数在连接的行中一个接一个地挑选所有可能的单元格，同时保留前缀和后缀； chunksOf n 从一长排单元格重建电路板，以连续 n 单元格的 block 为单位。所以整体效果是所有可能的板的列表，其中 E 被替换为 who。

更高效的picks会以相反的顺序构建它的前缀(sy)；创建一个所谓的“ zipper ”列表。然后在重建时必须相应地反转它们。

编辑:如列表理解所示，它本来可以首先用 do 符号编写的:

next n who b =  do 
    (sy, E, ys) <- picks $ concat b
    return (chunksOf n $ sy ++ [who] ++ ys])

在 do 表示法中，模式不匹配被转换为对 fail 的调用，在列表 monad 中，这会导致跳过一个元素，同时继续进行整个计算没有失败。

edit2: 一个基于 Data.List 的代码，一次完成输入，是

import Data.List (mapAccumL)

-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
next who b = concat . snd $ mapAccumL f (id, drop 1 xs) xs 
  where
    xs = concat b
    n = length b
    f (k,r) x = ( (k.(x:), drop 1 r) , [chunksOf n $ k (who:r) | x==E] ) 

感谢גלעד ברקן供讨论。