我应该用什么结构来表达棋盘游戏？

Question

我有一个Kalah求解器的工作实现,这是一个计算游戏第一回合最佳连续动作的应用程序.

我正在重新实现这个应用程序,虽然这次是一个测试套件和(希望)更漂亮的代码,它利用了更有趣的结构,如monoids或monad.

正如你在原始代码中看到的那样(或者不是,它是非常复杂的,这就是我重写它的原因)我已经定义了一个"移动",如下所示:

1. 我正在列出Pot我的董事会名单,以及我在董事会一侧的起始位置.
2. 我拿起弹珠直到我到达列表的末尾Pot.
3. 在"一圈"结束时,我返回改变的板子([Pot]),我手里拿着多少个大理石,一个ADT表示我是否应该去另一圈(LapResult).

问题是我怀疑如果我用一些聪明的数据结构表示我可以作为输入参数传递给一个函数并且具有相同的数据结构的板状态,我就不需要将一个移动分成几圈.作为回报值.至少这是我的猜测,我的想法是,董事会状态让我想起了我读过的关于幺半群的内容.

因此,如果我将一个"移动"定义为所有拾取弹珠直到你落入空锅或商店,是否有一些明显的方法来重写代码以便"移动"如何工作？

可以在此处找到重新实现的当前状态.

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.

给定罐中的弹珠数量

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

现在您可以编写一个移动函数。对于非法移动，我们将不返回任何内容。

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 函数的变体。这有点不优雅；我们想知道导致该位置的移动，但初始位置没有导致该位置的移动。因此，也许。

ExpandTree 函数采用一个函数（下面代码中的 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  

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