6

我对 OCaml 相当陌生，我想实现一个类似于四合一游戏。我需要一些数据结构来保持游戏状态。游戏板是一个 4x4 的正方形，共有 16 块瓷砖。我正在 OCaml 中为此寻找一种表示形式，它可以轻松快速地检索（或对其进行一些操作）整个列、行或对角线中的所有元素。我将在这个游戏上进行极小极大搜索，这就是为什么速度很重要。

到目前为止，我已经考虑了一个一维列表。列表的问题在于很难弄清楚哪些元素属于每一行/列/对角线，然后用List.map例如检索它们。

我考虑过使用Array.make 4 (Array.make 4 Empty);;. 当涉及到行时，这绝对是完美的。很容易得到它们并对其进行模式匹配。但是在单个列和对角线上进行模式匹配是一件苦差事。

我想做的是有一个函数，它接受一个游戏板并返回一个包含所有行/列/对角线的列表列表。然后我想做，例如，match (rows,columns,diagonals) with (Empty, Empty, Empty, Empty) -> something。

4

3 回答 3

2

由于长度是固定的，因此更喜欢数组而不是列表：它们使用更少的内存并且读写速度更快。

恐怕您需要编写一个函数来获取对角线，没有简单的模式匹配。当您编写“在 [对角线] 上执行一些操作”时，我假设您正在考虑f使用长度为 4 的数组存储元素的函数，例如[|Empty;Empty;Empty;Empty|]. 也许f可以改为将 positionp和 position 内的索引数组作为参数： f p [|x1,y1; x2,y2; x3,y3; x4,y4|]将提取 squares p.(x1).(y1) ... p.(x4).(y4)。然后只需传递不同x的 ' 和y' 来f对行/列/对角线进行操作。

一旦代码正常工作并且您正在转向优化，您可能想看看位向量：如果在您的 minmax 搜索的树中存储了很多位置，则减少内存占用意味着更多的缓存命中和更快的执行. 您可能想要自己在单个 int 中编码一个位置，但这是一些棘手的工作，您不想过早地这样做。

于 2012-11-10T22:24:42.937 回答
1

用相应的坐标索引你的瓷砖怎么样？因此，您的一维列表中的元素将采用以下形式：

(int * int * ref tile)

然后你可以像这样过滤行/列/对角线：

第 n 行：（ 前提条件：0 <= n, u, v <= 3）

List.filter tiles (fun x -> match x with (u, v, _) -> u = n);;

第 n 列：（ 前提条件：0 <= n, u, v <= 3）

List.filter tiles (fun x -> match x with (u, v, _) -> v = n);;

对角线 1：（ 前提条件：0 <= u, v <= 3）

List.filter tiles (fun x -> match x with (u, v, _) -> u = v);;

对角线 2：（ 前提条件：0 <= u, v <= 3）

List.filter tiles (fun x -> match x with (u, v, _) -> u + v = 3);;

也应该可以只用一个整数（一维列表中的图块的索引）来索引图块，但这需要在过滤器函数中进行一些计算（给定索引，找出坐标，然后决定是否属于所需的行/列/对角线）。

于 2012-11-11T11:36:49.337 回答
1

有时匹配不起作用。在这里，我认为你应该尽可能多地使用函数，然后让你的单元格先行或先列不会那么复杂，你甚至可以通过颠倒索引顺序从一种表示转移到另一种表示。

如果我使用以下类型：

type color = Red | Yellow;;
type cell  = Empty | Color of color;;
type board = Array.make 4 (Array.make 4 Empty);;

并首先决定列，然后以下函数将为我获取行或列：

let column (b: board) i j = b.(i).(j)
let row (b: board) i j = b.(j).(i)

对于对角线，有两组，一组从左上到右下，另一组在另一个方向（从右上到左下）：

let ldiag (b: board) i j = b.((i + j) mod 4).(j)
let rdiag (b: board) i j = b.((i - j + 4) mod 4).(j)

然后我想检查行、列或对角线只是检查该行的 4 个单元格。

let check predicate linef k = predicate (linef b k 0) && 
                               predicate (linef b k 1) && 
                               predicate (linef b k 2) && 
                               predicate (linef b k 3)

然后例如，检查是否有红色的对角线：

let has_line linef b color = 
    let cmp x = x = color in
    let check k = check cmp linef b k in
    check 0 || check 1 || check 2 || check 3

let has_ldiag b color = has_line ldiag b color
let has_rdiag b color = has_line rdiag b color

let has_red_diagonal b = has_ldiag b Red | has_rdiag b Red

等等。

于 2012-11-12T00:34:26.043 回答