6

我正在编写一个 tictactoe 程序，但它不是你传统的 tictactoe

首先，棋盘是 4x4，获胜的方法是在一行、一列或对角线上获得 3 个同类和 1 个对手。因此，通过第一列，以下将是“O”的胜利：

O|_|X|_
O|X|_|_
O| |_|_
X|_|_|_

我正在尝试实现一个极小极大算法，以便为程序提供一个无法击败的“硬”模式。

我的问题是我不能希望创建一个包含所有可能游戏状态的树，因此我必须想出某种函数来评估我可以生成的游戏状态。

我想我的问题是，我怎么能想出这样的功能？

4

2 回答 2

4

这个游戏对于蛮力来说绝对足够小。

您可以枚举所有状态。有 16 个方格，每个方格有 3 个可能的值（X、O 或空）。

3^16 = 43046721，约4300万。

这意味着一个用一个字节来描述每个州的可赢性的表格只有 43 兆字节。

我会创建一个函数，将每个状态映射到 1 到 4300 万之间的索引（您只需要状态，而不是可能的播放顺序），基本上将其表示为 base-3 中的数字，并允许您创建状态从一个索引。

选择每个状态可以采用的 4 个可赢性值 - O 可赢，X 可赢，不可赢和未知。

分配一个长度为 43046721 的缓冲区来存储每个游戏状态的胜率。

遍历所有索引号，标记获胜状态。然后遍历并迭代地填写其余每个状态的可赢性，如果知道的话（检查所有后继状态，根据轮到谁）。这将在一组索引上最多进行 16 次迭代，所以我看不出暴力在这里不起作用的任何原因。

有一些优化，比如利用对称性，利用 n 块向下的所有状态都被 n+1 块的状态取代等事实，但我认为你一开始不需要这些。

于 2012-10-21T07:35:35.610 回答
2

游戏的启发式函数是评估给定游戏状态的函数。在这里——状态基本上由两部分组成：（1）棋盘本身。(2) 轮到谁了。

一些可能的启发式函数：

  1. 行/列/对角线中 X（或 O，根据评估的玩家）的最大数量
  2. “几乎获胜”限制的数量（缺少一个动作） - 可以有效地最大化获胜可能性的数量

我想人们可以想到更多的启发式方法。
您可以将不同的启发式方法组合成一个“大”启发式函数，如下所示：

a_1 * h_1(state) + a_2 * h_2(state) + ... + a_n * h_n(state)

棘手的部分是学习 a_1,...,a_n 的分数 - 这可以通过多种方式完成 - 其中之一是蒙特卡罗学习- 这基本上意味着：创建具有不同a_1,..,a_n值的各种代理，在他们，当比赛结束时——根据获胜者调整权重——并在你还有时间的时候重复这个过程（这是一种随时算法）。
完成后，将学习到的权重用于最终代理。

PS 可能的游戏数量约为 16！（需要确定选择的方块的顺序——它决定了游戏的其余部分将如何结束）——问问自己它是否“小”到足以在你的约束范围内开发——或者它是否太多并且确实需要启发式解决方案.

于 2012-10-21T07:43:53.107 回答