1

所以我有一个井字游戏板，以嵌套元组的形式，如下所示：

type Row = (Field, Field, Field)
type Board = (Row, Row, Row)

data Field = X | O | B
    deriving (Eq, Ord)

其中B代表空。我需要选择一个玩家，一个给定的棋盘状态，然后在下一步之后生成所有可能的棋盘状态的列表。

moves :: Player -> Board -> [Board]

但是，我就是想不通。我最初的想法是我需要遍历每个字段，检查它是否为空，然后在列表中添加一个新的 Board 或者什么都不做。但是，我看不到遍历所有字段的方法。即使我使用 if 语句或守卫手动检查每个字段，我如何移动到下一个字段来检查它，无论我最终是否有可能的移动？

如果我将板格式转换为列表，我可以做到，但我觉得这违背了这个问题的目的。必须有一个不需要重组董事会的更好的解决方案。

4

3 回答 3

1

您将无法遍历元组的字段——元组不是为此而设计的。列表的列表可能是这个问题的更自然的表示。

也就是说，您可以按照类型使用您正在使用的板表示来实现此功能。对 aBoard的移动是对第一行、第二行或第三行的移动。连续移动是玩家在第一、第二或第三场的位置。您的表示的困难在于没有简单的方法来映射元组，因为元组通常是异构的。因此，您可以做的一件事是自己编写一种通用方法，将函数应用于元组中的某个位置。这是一种方法（如果这些Monad东西让您感到困惑，请在您看到的任何地方用心理替换“foo 列表” m foo，您会没事的）：

mReplace1 :: Monad m => (a -> m d) -> (a,b,c) -> m (d,b,c)
mReplace1 f (a,b,c) = f a >>= \d -> return (d,b,c)

mReplace2 :: Monad m => (b -> m d) -> (a,b,c) -> m (a,d,c)
mReplace2 f (a,b,c) = f b >>= \d -> return (a,d,c)

mReplace3 :: Monad m => (c -> m d) -> (a,b,c) -> m (a,b,d)
mReplace3 f (a,b,c) = f c >>= \d -> return (a,b,d)

这些函数提供了一种将函数分别应用于元组中的第一个、第二个和第三个槽的方法。它们被包装在一个 monad 中，这样我们就可以有一个函数返回插槽的可能性列表，并自动将其转换为整个元组的可能性列表。

有了这些，我们只需将这些调用串在一起就可以编写整个函数。

moves p board = mReplace1 rowMoves board ++
                mReplace2 rowMoves board ++
                mReplace3 rowMoves board
    where rowMoves row = mReplace1 fieldMoves row ++
                         mReplace2 fieldMoves row ++
                         mReplace3 fieldMoves row
          fieldMoves B = [p]
          fieldMoves _ = []

也就是说：棋盘的走法是第 1 行的所有可能性，加上第 2 行的所有可能性，再加上第 3 行的所有可能性。对于给定的行，可能的移动是插槽 1 的所有移动，加上槽 2 的所有移动，加上槽 3 的所有移动。对于给定的槽，如果那里已经有 X 或 O，则没有可能的移动；否则有一个可能的动作（将玩家放在那个位置）。

于 2013-10-03T23:12:45.573 回答
0

正如其他人所说，元组对于这种方法不是一个好主意，因为没有办法遍历它们。

你说你需要元组，所以你去吧，我几乎可以肯定它有效，测试它。

首先你的代码我会怎么做

import Control.Monad (msum)
import Control.Applicative ((<*>), pure)

data Player = P1 | P2 deriving (Eq, Show)

data Field = X | O | B deriving (Eq, Show)

type Board = ((Field,Field,Field)
             ,(Field,Field,Field)
             ,(Field,Field,Field))

symbolToPlayer :: Field -> Player
symbolToPlayer X = P1
symbolToPlayer O = P2

checkThree :: (Field,Field,Field) -> Maybe Player
checkThree (a,b,c)
    | a == b && a == c = Just $ symbolToPlayer a
    | otherwise        = Nothing

winHorizontal :: Board -> Maybe Player
winHorizontal (r1, r2, r3) = msum $ map checkThree [r1, r2, r3]

winVertical :: Board -> Maybe Player
winVertical ((a,b,c), (d,e,f), (g,h,i)) =
    msum $ map checkThree [(a,d,g), (b,e,h), (c,f,i)]

winDiagonal :: Board -> Maybe Player
winDiagonal ((a,_,c), (_,e,_), (g,_,i)) =
    msum $ map checkThree [(a,e,i), (c,e,g)]

hasWinner :: Board -> Maybe Player
hasWinner b = msum $ [winHorizontal, winVertical, winHorizontal] <*> pure b

这是 nextStates 函数的一部分

boardBlanks :: Board -> Int
boardBlanks (r1,r2,r3) = rowBlanks r1 + rowBlanks r2 + rowBlanks r3

rowBlanks :: (Field, Field, Field) -> Int
rowBlanks (a,b,c) = foldr hack 0 [a,b,c]
    where hack B c = 1 + c
          hack _ c = c

changeBoard :: Field -> Int -> Board -> Board
changeBoard f i (a,b,c)
    | hack [a] > i    = (changeRow f (i - hack []) a, b, c)
    | hack [a,b] > i  = (a, changeRow f (i - hack [a]) b, c)
    | hack [a,b,c] > i= (a, b, changeRow f (i - hack [a,b]) c)
    where
        hack ls = sum $ map rowBlanks ls

changeRow f 0 row =
    case row of
         (B,a,b)   -> (f,a,b)
         (a,B,b)   -> (a,f,b)
         (a,b,B)   -> (a,b,f)
         otherwise -> row
changeRow f 1 row =
    case row of
        (B,B,a)   -> (B,f,a)
        (a,B,B)   -> (a,B,f)
        otherwise -> row
changeRow f 2 row =
    case row of
        (B,B,B)   -> (B,B,f)
        otherwise -> row

nextStates :: Board -> [Board]
nextStates b = os ++ xs
    where
        os = foldr (hack O) [] . zip [0..] $ replicate (boardBlanks b) b
        xs = foldr (hack X) [] . zip [0..] $ replicate (boardBlanks b) b
        hack f (i,a) ls = changeBoard f i a : ls
于 2013-10-03T23:28:22.063 回答
0

这是我以前使用过的简单解决方案

import qualified Data.Map as Map

data Piece    = O | X deriving (Eq,Ord)
type Position = (Int,Int)
type Board    = Map.Map Position Piece

positions = [(i,j) | i <- [0,1,2], j <- [0,1,2]]

spaces board = map (\pos -> Map.notMember pos board) positions

moves player board = map (\pos -> Map.insert pos player board) (spaces board)
于 2013-10-03T22:42:33.007 回答