用 Haskell 表示棋盘

Question

我正在尝试在Haskell中实现一个函数，该函数返回一个列表，其中包含当前玩家的所有可能移动。该函数的唯一参数是由棋盘的实际状态（用Forsyth-Edwards Notation表示）和移动的玩家(b/w)组成的字符串。

符号示例：rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w（起始棋盘状态）

移动被传输为形式为[origin]-[destination]的字符串。目标位置始终是形式为[column][row]的位置，其中左下角的方格称为a1，右上角的方格称为h8。例如，移动“b3-c4”就是一个移动（没有王车易位/吃过路兵）。

在Java中，我会使用2D数组来表示棋盘，但在Haskell中，我找不到类似的解决方案（我是函数式编程的新手）。

什么是表示国际象棋棋盘的好方法/数据结构？

- Lino

---

https://github.com/OlivierNicole/haskell-chess/blob/master/ChessBoard.hs - Gertjan Brouwer

Answer 1

存储棋盘状态有两个主要选项。第一个是使用 Maybe 的 2D 列表，其中棋子的表示方式为例如 Just $ Piece Black King，空格则表示为 Nothing。这种方法优化了检测方格是否被占用的操作，而不是列出每个棋子所在的位置（如果您计划添加渲染功能，则可能很重要）：

type Board = Vector (Vector (Maybe Piece))

data Piece = Piece { color :: Color
                   , type  :: PieceType }

第二种选项是存储每个棋子及其位置的列表。这种实现方式更快地枚举所有棋子的位置，但在检查特定位置是否有棋子时较慢：

type Pieces = [Placement]

type Placement = { position :: Position
                 , piece    :: Piece }

data Position = 
    Pos { rank :: Int
        , file :: Int }
    deriving (Show, Eq)

data Piece = 
    Piece { color :: Color
          , ptype :: PieceType }
    deriving Show

注：需要注意的是，在8x8网格和最多32个棋子的情况下，无论哪种方式，性能影响都将是最小的，除非您进行了大量计算。

- Andrew Ray

Answer 2

Data.Vector，可以通过索引进行常数时间查找。

棋盘可以表示为 Vector (Vector (Maybe Piece))。要定义Piece，请参见ADTs。

- 414owen

---

我无法使用Vector（仅限于Haskell项目中的默认库限制）。也许Data.Array可能是一种替代方案。 - Lino

当然。 GHC Haskell 提供了 GHC.Arr。 - 414owen