haskell - 我应该使用什么结构来表达棋盘游戏中的回合？

Question

我有一个 working implementation的Kalah求解器，一个计算游戏第一回合的最佳连续移动的应用程序。

我正在重新实现这个应用程序，尽管这次使用了测试套件和(希望)更漂亮的代码，利用了更有趣的结构，如幺半群或单子(monad)。

正如您在 original code 中看到的那样(或者不是，它非常复杂，这就是我重写它的原因)我定义了一个“移动”如下:

1. 我将传入一个 Pot 列表作为我的棋盘，以及我这边棋盘的起始位置。
2. 我捡起并放下弹珠，直到到达 Pot 列表的末尾。
3. 在“一圈”结束时，我返回修改后的棋盘 ([Pot])、我手中可能持有多少颗弹珠以及表示我是否应该再跑一圈的 ADT或不(LapResult)。

问题是，我怀疑如果我用一些巧妙的数据结构来表达棋盘状态，我就不需要将移动分成几圈，我既可以将其作为函数的输入参数传递并拥有相同的数据结构作为返回值出现。至少这是我的猜测，我的想法是董事会状态让我想起了我读过的有关幺半群的内容。

因此，如果我将一个“移动”定义为所有拾取和掉落的弹珠，直到您落在空 jar 或商店中，是否有一些明显的方法可以重写“移动”的代码有效吗？

可以找到重新实现的当前状态 here .

Answer 1

注意:我还没有测试过这些。它可能有问题。

我认为你的问题是你需要从两个角度来考虑董事会，称它们为“白”和“黑”。

data Player = White | Black

otherPlayer :: Player -> Player
otherPlayer White = Black
otherPlayer Black = White

Mancala 板是一个循环结构，这表明模块化运算。我建议类似:

import Data.Vector -- More efficient version of Array

type PotNum = Int  -- Use Int for simple index of pot position.

type Pot = Int   -- Just record number of marbles in the pot.

通过使用 Data.Word8 而不是 Int，您可能会获得更紧凑的数据结构，但我不确定。暂时保持简单。

type Board = Vector Pot

然后让 isStore 成为 PotNum 和播放器的简单函数

isStore :: Player -> PotNum -> Bool
isStore White 0 = True
isStore Black 7 = True
isStore _ _ = False

您还想在棋盘上向前移动，跳过其他玩家的商店..

nextPot :: Player -> PotNum -> PotNum
nextPot White 6 = 8  -- Skip Black's store
nextPot White 13 = 0
nextPot Black 12 = 0 -- Skip White's store
nextPot _ n = n + 1

每个玩家控制的底池列表

playerPots :: Player -> [PotNum]  -- Implementation omitted.

给定 jar 中的弹珠数量

marblesIn :: PotNum -> Board -> Int  -- Implementation omitted.

现在您可以编写移动函数了。对于非法移动，我们将让它返回 Nothing。

move :: Player -> PotNum -> Board -> Maybe Board   -- Implementation omitted.

使用 List monad，您可以使其产生所有潜在的移动和结果板状态

allMoves :: Player -> Board -> [(PotNum, Board)]
allMoves p b1 = do
    n <- playerPots p
    case move p n b1 of
       Nothing -> fail ""   -- List monad has this as []
       Just b2 -> return (n, b2)

现在您可以使用 Data.Tree.unfold 从任何起始位置获取完整的游戏树，它采用 move 函数的变体。这有点不优雅；我们想知道导致该位置的移动，但初始位置没有导致该位置的移动。因此，也许。

unfoldTree 函数采用一个函数(下面代码中的 f)，该函数采用当前状态并返回当前节点和子节点值列表。当前状态和当前节点都是刚刚移动的玩家、他们所做的移动以及结果棋盘的三重关系。因此是“f”的第一位。 “f”的第二位调用“opponentMoves”函数，该函数转换“allMoves”返回的值以添加正确的数据。

unfoldGame :: Player -> Board -> Tree (Player, Maybe PotNum, Board)
unfoldGame p b = unfoldTree f (p, Nothing, b)
   where 
      f (p1, n1, b1) = ((p1, n1, b1), opponentMoves (otherPlayer p1), b1
      opponentMoves p2 b2 = map (\(n3, b3) -> (p2, Just n3, b3)) $ allMoves p2 b2  

现在你只需要走树即可。每一片叶子都是游戏的结束，因为没有剩下合法的 Action 。 ExpandGame 函数是惰性函数，因此您只需要内存来保存当前正在考虑的游戏状态。