7

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

我正在重新实现这个应用程序，尽管这次使用了一个测试套件和（希望）更漂亮的代码，这些代码利用了更有趣的结构，如 monoids 或 monads。

正如你在原始代码中看到的（或者不是，它非常复杂，这就是我重写它的原因）我已经定义了一个“移动”，如下所示：

  1. 我正在传递我的董事会名单，Pot以及我所在董事会的起始位置。
  2. 我拿起并放下弹珠，直到到达列表的末尾Pot。
  3. 在“一圈”结束时，我归还更改过的棋盘（[Pot]），我手里可能拿着多少个弹珠，以及一个 ADT，表示我是否应该再跑一圈（LapResult）。

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

因此，如果我将一个“移动”定义为所有的拾取和丢弃弹珠，直到你降落在一个空罐或商店中，是否有一些明显的方法可以重写“移动”如何工作的代码？

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

4

1 回答 1

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.

现在你可以编写一个移动函数了。对于非法移动，我们将让它返回 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 函数的变体。这有点不雅；我们想知道导致该位置的移动，但初始位置没有导致它的移动。因此，也许。

展开树函数接受一个函数（下面代码中的 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

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

于 2013-10-27T21:06:33.927 回答