井字棋的变种游戏：扭曲井字棋。

Question

井字棋的变种游戏：扭曲井字棋。

6

我正在编写一个井字棋程序，但它不是传统的井字棋游戏。

首先，棋盘是4×4的，获胜的方法是在一行、一列或对角线上放置3个自己的棋子和1个对手的棋子。因此，以下情况将是 "O" 在第一列获胜的情况：

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

我正在尝试实现极小化-极大化算法，以便为程序提供“困难”模式，让人无法击败。

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

我的问题是，我该如何想出这样的功能？

- rage

第一步是确定/制定一个“获胜策略”（使用词语描述所需的决策过程，以确保获胜）。 - goat

“3 of a kind and 1 of your opponents...”这句话的意思是，‘O’玩家可以通过类似于‘OOXO’的排列方式获胜，而不仅仅是‘OOOX’或‘XOOO’。此外，解决这个问题是否需要使用极小化极大算法（minimax）？如果有其他方法，您是否欢迎尝试？ - user1201210

任何方法都可以，我只是想尝试使用极小化极大算法，但我已经花了4个小时，没有取得任何进展。现在我只是使用一堆if语句：\。是的，你对于获胜游戏的不同组合的想法是正确的。 - rage

2个回答

2

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

一些可能的启发式函数：

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

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

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

难点在于学习a_1，...，a_n的得分 - 这可以通过各种方式完成 - 其中一种是蒙特卡罗学习 - 基本上意味着：创建具有不同a_1，..，a_n值的各种代理，运行它们之间的锦标赛，当锦标赛结束时 - 根据获胜者调整权重 - 并在你还有时间的情况下重复这个过程（这是一个任何时候算法）。
完成后，使用学习到的权重来创建最终代理。

P.S. 可能的游戏数量约为16！（需要确定选择的方格顺序 - 它选择了游戏的其余部分将如何结束）- 请问自己它是否“小”到足以在您的限制条件内开发 - 或者它是否太多，确实需要启发式解决方案。

- amit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric · Accepted Answer

这个游戏的规模足够小，可以采用暴力枚举法。总共有16个方格，每个方格有3种可能的取值（X、O或空）。

3^16 = 43046721，约为4300万。

这意味着一个表格只需要一个字节来描述每个状态的可赢性，总大小只有43兆字节。

我会创建一个函数，将每个状态映射到1到4300万之间的索引（你只需要状态，不需要可能的下棋顺序），基本上将其表示为一个三进制数，并允许您从索引创建状态。

选择4个可赢性值，每个状态都可以采取-对于O可赢，对于X可赢，不可赢和未知。

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

遍历所有索引号，标记获胜状态。然后遍历并逐步填充其余状态的可赢性（如果已知，则根据轮到谁来检查所有后继状态）。这最多需要16次迭代来处理索引集合，因此我认为这里没有任何原因不使用暴力方法。

还有一些优化措施，比如利用对称性、利用所有n个棋子下去的状态都被n+1个棋子的状态所继承等，但我认为您在一开始不需要这些。