在 4x4 井字游戏中确定获胜者
Determine the winner in 4x4 tic tac toe
4x4 井字棋是在四行（从上到下编号为 0 到 3）和 4 列（从左到右编号为 0 到 3）的棋盘上进行的。 X 总是先走一步。
第一个在同一行、同一列或对角线（仅 2 个主对角线）上获得四块棋子的玩家获胜。如果棋盘已满且没有玩家获胜，则游戏平局。
假设现在轮到X走棋，如果X可以下棋，那么X被认为是强制获胜，无论走什么棋O使得剩下的比赛，X可以赢。这并不一定意味着 X 将在下一步行动中获胜，尽管这是有可能的。这意味着 X 有一个获胜策略，无论 O 做什么，都能保证最终的胜利。
鉴于 X 部分完成的游戏接下来要移动，我必须确定 X 是否有强制获胜。该游戏将代表真实世界的游戏，并且不存在错误（例如 x 的数量多于 o 的数量等）。如果有这样的强迫获胜，应该报告发现的第一个这样的强迫获胜。本题以棋盘位置决定首胜。
通过检查位置 (0,0)、(0, 1)、(0, 2)、(0, 3)、(1, 0)、(1, 1) 来搜索强制获胜, ..., (2, 2),...(3, 3) 的顺序，并输出找到的第一个强制获胜。请注意，X 可能有很多动作可能导致强制获胜 - 因此以这种方式找到第一个这样的强制获胜。
示例：
....
.xo.
.ox.
....
这里，X没有强制获胜。但这是另一个例子：
o...
.ox.
.xxx
xooo
(0, 1) by X 是强制获胜。 （尽管在 (0, 3) 和 (2, 0) 处标记 x 会使 x 在同一着法中获胜，但我们不允许跳转到任何特定位置。必须执行顺序扫描每个位置和顺序都在上面提到。）
我的方法：
因此，假设对于上面提到的第二个示例，如果我在 (0, 1) {这是可以进行移动的第一个空位}进行 x 移动，我将递归调用此方法以确定是否通过标记这个地方作为 x 并在 3 个不同的子例程下检查以下内容，
x赢了吗？- 有平局吗？
o赢了吗？
这 3 个条件将在单独的方法中进行评估，每个 returning 一个布尔值。如果 1 的 return 值为真，我将 return 直接作为答案。但是如果 2 为真，那么对于 x 在 (0, 1) 移动的当前棋盘，我将移动 o 以防止 x 获胜。可以根据作为参数传递给函数的当前 bool 值进行轮次更改。为了确定此步，我必须扫描整个棋盘（4 行、4 列和 2 条对角线），看看棋盘上是否有任何地方 x 在 4 个标记中有 3 个标记。
我无法想出下一步，我强烈觉得我走错了方向。我知道它涉及递归和回溯。（如果不是，请纠正我）。任何形式的指导将不胜感激。
更新：
我试图自己弄清楚一些事情。
- 如果游戏中的标记少于 6 个，则为平局。
- 因此，即使对已经存在 6 个标记的游戏使用蛮力，复杂度也将是 9！对于分析的每场比赛（如果模拟到最后。但是一旦我们知道这是
x 的强制胜利，我们可以立即 return）。
- 如果标记 x 产生超过 2 条得分为 3 或更高的线，并且没有 o 得分为 -3 或更高的线，则
x 强制获胜（在棋盘上，我使用 1 表示标记为 x，-1 表示标记为 o，0 表示空 space).
- 如果标记 0 生成超过 2 行且分数为 -3 或更高，则强制执行
o 并且 x 丢失。
- 不需要检查超出这些点。
- 在每次移动前执行绘制检查。
更新2：
Tricont 建议我在这里使用 minmax 算法方法。但我相信这对这个问题来说可能有点矫枉过正。这不是人类与人工智能的游戏。我只需要确定导致x逼赢的位置。如果不存在这样的位置，那么它肯定不是逼赢（可能输掉x或平局）。
每个场地都被玩家 1 覆盖，被玩家 2 覆盖，或者空着。那是 $3^{16}$ 的可能性，这比 1 亿要少得多。
根据 X 与 Y 覆盖的场数，将每个位置标记为 X、Y 或“不允许”：相同的数字 -> x 正在比赛，多一个 X 场 -> Y 正在比赛，其他 - > 不允许。
将每个允许的位置标记为获胜、失败、平局或未知：四个对手颜色 = 失败，四个你自己的颜色 = 不允许，所有填充 = 平局，否则未知。
现在遍历所有未知位置：任何移动到“丢失”（对手）位置 -> 获胜。任何移动到“未知”位置 -> 未知。任何移动到“绘制”->绘制。否则所有动作都为对手赢得 -> 失败。
Minimax 是这个问题的解。
这里最重要的想法是玩家 O 可以对平局感到满意，并且当它放置 [=63] 时至少可以确保平局=]o 在网格上任何可能的四行中的至少一个单元格中。有 10 条这样的线（4 条水平线、4 条垂直线和 2 条对角线）。 O 在所有 10 行中都出现并不难。比如O已经占据了这4个位置，那么X就不可能赢：
...o
.o..
..o.
o...
这意味着 O 很容易阻止 X 获胜，因此预计搜索不会必须下棋直到棋盘被完全填满，因为两位玩家中的一个在游戏中早就达到了他们的目标。
评价函数
极小极大实现需要评估函数。在这种情况下，它可以决定最后一步的玩家是否达到了他们的目标。
- X 的目标是获胜。
- O 的目标是获胜或平局。
因此评估函数可以检查所有 10 条四人行，看看最后上场的玩家是否已经完全占据了这条线。如果找到，评估函数应该 return 1 -- 表明玩家已经达到他们的目标。
接下来，评估函数应该检查 O 是否是最后一个上场的玩家。如果是这样，它可以再次检查所有 10 行四行，并查看 O 是否在 each 行中至少有一个存在。如果是这样，它也应该 return 1 -- 表明 O 已经达到了他们的目标。
在所有其他情况下，评估函数可能 return 0 -- 表示还没有明确的答案。
由于唯一的结果是 0 或 1，评估函数也可以 return 布尔值。我将调用该函数 happy.
极小极大
极小极大函数return是一个值。在这种情况下，我们将支持值 -1、0 或 1：
- -1: 最后上场的玩家无法达到目标
- 0：未定
- 1：最后出场的玩家可以强行达到目标。
Minimax 将执行所有对手的移动并找出哪一个给出“最佳”结果，在这种情况下，其评估值为 1。如果找到这样的移动，则前一个玩家将获得否定的评估返回他们的最后一步，即-1。对于可以从 minimax.
的递归调用返回的其他评估值，也会发生类似的逻辑。
董事会代表
游戏的表现方式有很多种。我选择为两个玩家使用一个位图，每个位置一个位。所以每个玩家都有一个 16 位位图，位图中的每个 1 位代表他们所做的一步。导致特定状态的移动顺序无关紧要。
4 行也可以表示为位图，以便通过用它们覆盖玩家的位图轻松检测到获胜。
步数用数字表示，从 0 到 15。
记忆
Minimax 可以从记忆中受益，这样它就不需要通过相同的搜索树来评估相同的棋盘状态两次。由于我选择用两个 16 位数字表示电路板，因此很容易通过 32 位数字识别（散列）状态。
实施
这是一个 JavaScript 实现。你可以在这里 运行 它，它会输出你给出的两个例子的结果。一个非负整数的输出，意味着该移动是强制获胜。输出 -1 表示不可能强制获胜。
class TicTacToe {
static memo = new Map; // For memoization
constructor(str) {
str = str.toLowerCase().replace(/[^.xo]/gi, "");
if (str.length !== 16) throw "Invalid board size";
this.players = [0x0000, 0x0000]; // bitmaps for both players
this.lines = [ // bitmaps of winning lines
0xF000, 0x0F00, 0x00F0, 0x000F,
0x1111, 0x2222, 0x4444, 0x8888,
0x1248, 0x8421
];
this.turn = 0; // 0 or 1
// collect moves into bitmaps
let bit = 1;
let balance = 0;
for (let ch of str) {
let player = "xo".indexOf(ch);
if (player >= 0) {
this.players[player] ^= bit;
balance += player || -1;
}
bit *= 2;
}
if (balance != 0) throw "Number of X and O should be equal";
}
doMove(move) {
this.players[this.turn] ^= 1 << move;
this.turn ^= 1;
}
undoMove(move) {
this.turn ^= 1;
this.players[this.turn] ^= 1 << move;
}
happy() {
// Returns whether the player (that last moved) has reached their goal (boolean)
// For "X" this means they have 4-in-a-row.
// For "O" this means they have 4-in-a-row OR have a presence in all 10 lines
let mask = this.players[1 - this.turn];
for (let line of this.lines) {
if ((line & mask) === line) return true; // Game over. Last move was winner.
}
if (this.turn == 1) return false;
// Check whether last player ("O") cannot lose:
for (let line of this.lines) {
if ((line & mask) == 0) return false; // Opponent could still win here
}
return true; // Second player is happy with draw
}
getMoveList() {
let occupied = this.players[0] ^ this.players[1];
let moveList = [];
for (let move = 0; move < 16; move++) {
if (((occupied >> move) & 1) == 0) moveList.push(move);
}
return moveList;
}
minimax() { // Return value for player that just played (-1, 0 or 1).
let key = (this.players[0] << 16) + this.players[1];
let value = TicTacToe.memo.get(key); // Using memoization
if (value === undefined) { // Not encountered before
value = 1;
if (!this.happy()) { // Undecided?
for (let move of this.getMoveList()) {
this.doMove(move);
// What is good for opponent is bad for current player:
value = Math.min(value, -this.minimax());
this.undoMove(move);
if (value == -1) break; // Opponent can reach their goal
}
}
TicTacToe.memo.set(key, value); // Memoize...
}
return value;
}
bestMove() { // Returns winning move (0..15) for X or -1 if none found
if (this.happy()) return -1; // "O" already ensured at least a draw.
for (let move of this.getMoveList()) {
this.doMove(move);
let value = this.minimax();
this.undoMove(move);
if (value == 1) return move; // forced win: return this winning move
}
return -1; // no forced win found
}
toString() { // To ease printing...
let str = "";
for (let bit = 1; bit < 0x10000; bit *= 2) {
if (this.players[0] & bit) str += "x";
else if (this.players[1] & bit) str += "o";
else str += ".";
if (bit & 0x8888) str += "\n";
}
return str;
}
}
let game;
// Test case 1:
game = new TicTacToe(`
o...
.ox.
.xxx
xooo`);
console.log(game.toString());
console.log("bestMove() returned", game.bestMove());
// Test case 2:
game = new TicTacToe(`
....
.ox.
.xo.
....`);
console.log(game.toString());
console.log("bestMove() returned", game.bestMove());
人们可以想到许多优化，但由于这已经 运行s 在可接受的时间内，我就这样离开了。
4x4 井字棋是在四行（从上到下编号为 0 到 3）和 4 列（从左到右编号为 0 到 3）的棋盘上进行的。 X 总是先走一步。
第一个在同一行、同一列或对角线（仅 2 个主对角线）上获得四块棋子的玩家获胜。如果棋盘已满且没有玩家获胜，则游戏平局。
假设现在轮到X走棋，如果X可以下棋，那么X被认为是强制获胜，无论走什么棋O使得剩下的比赛，X可以赢。这并不一定意味着 X 将在下一步行动中获胜，尽管这是有可能的。这意味着 X 有一个获胜策略，无论 O 做什么，都能保证最终的胜利。
鉴于 X 部分完成的游戏接下来要移动，我必须确定 X 是否有强制获胜。该游戏将代表真实世界的游戏，并且不存在错误（例如 x 的数量多于 o 的数量等）。如果有这样的强迫获胜，应该报告发现的第一个这样的强迫获胜。本题以棋盘位置决定首胜。
通过检查位置 (0,0)、(0, 1)、(0, 2)、(0, 3)、(1, 0)、(1, 1) 来搜索强制获胜, ..., (2, 2),...(3, 3) 的顺序，并输出找到的第一个强制获胜。请注意，X 可能有很多动作可能导致强制获胜 - 因此以这种方式找到第一个这样的强制获胜。
示例：
....
.xo.
.ox.
....
这里，X没有强制获胜。但这是另一个例子：
o...
.ox.
.xxx
xooo
(0, 1) by X 是强制获胜。 （尽管在 (0, 3) 和 (2, 0) 处标记 x 会使 x 在同一着法中获胜，但我们不允许跳转到任何特定位置。必须执行顺序扫描每个位置和顺序都在上面提到。）
我的方法：
因此，假设对于上面提到的第二个示例，如果我在 (0, 1) {这是可以进行移动的第一个空位}进行 x 移动，我将递归调用此方法以确定是否通过标记这个地方作为 x 并在 3 个不同的子例程下检查以下内容，
x赢了吗？- 有平局吗？
o赢了吗？
这 3 个条件将在单独的方法中进行评估，每个 returning 一个布尔值。如果 1 的 return 值为真，我将 return 直接作为答案。但是如果 2 为真，那么对于 x 在 (0, 1) 移动的当前棋盘，我将移动 o 以防止 x 获胜。可以根据作为参数传递给函数的当前 bool 值进行轮次更改。为了确定此步，我必须扫描整个棋盘（4 行、4 列和 2 条对角线），看看棋盘上是否有任何地方 x 在 4 个标记中有 3 个标记。
我无法想出下一步，我强烈觉得我走错了方向。我知道它涉及递归和回溯。（如果不是，请纠正我）。任何形式的指导将不胜感激。
更新：
我试图自己弄清楚一些事情。
- 如果游戏中的标记少于 6 个，则为平局。
- 因此，即使对已经存在 6 个标记的游戏使用蛮力，复杂度也将是 9！对于分析的每场比赛（如果模拟到最后。但是一旦我们知道这是
x的强制胜利，我们可以立即 return）。 - 如果标记 x 产生超过 2 条得分为 3 或更高的线，并且没有 o 得分为 -3 或更高的线，则
x强制获胜（在棋盘上，我使用 1 表示标记为x，-1表示标记为o，0表示空 space). - 如果标记 0 生成超过 2 行且分数为 -3 或更高，则强制执行
o并且x丢失。 - 不需要检查超出这些点。
- 在每次移动前执行绘制检查。
更新2：
Tricont 建议我在这里使用 minmax 算法方法。但我相信这对这个问题来说可能有点矫枉过正。这不是人类与人工智能的游戏。我只需要确定导致x逼赢的位置。如果不存在这样的位置，那么它肯定不是逼赢（可能输掉x或平局）。
每个场地都被玩家 1 覆盖，被玩家 2 覆盖，或者空着。那是 $3^{16}$ 的可能性，这比 1 亿要少得多。
根据 X 与 Y 覆盖的场数，将每个位置标记为 X、Y 或“不允许”：相同的数字 -> x 正在比赛，多一个 X 场 -> Y 正在比赛，其他 - > 不允许。
将每个允许的位置标记为获胜、失败、平局或未知：四个对手颜色 = 失败，四个你自己的颜色 = 不允许，所有填充 = 平局，否则未知。
现在遍历所有未知位置：任何移动到“丢失”（对手）位置 -> 获胜。任何移动到“未知”位置 -> 未知。任何移动到“绘制”->绘制。否则所有动作都为对手赢得 -> 失败。
Minimax 是这个问题的解。
这里最重要的想法是玩家 O 可以对平局感到满意，并且当它放置 [=63] 时至少可以确保平局=]o 在网格上任何可能的四行中的至少一个单元格中。有 10 条这样的线（4 条水平线、4 条垂直线和 2 条对角线）。 O 在所有 10 行中都出现并不难。比如O已经占据了这4个位置，那么X就不可能赢：
...o
.o..
..o.
o...
这意味着 O 很容易阻止 X 获胜，因此预计搜索不会必须下棋直到棋盘被完全填满，因为两位玩家中的一个在游戏中早就达到了他们的目标。
评价函数
极小极大实现需要评估函数。在这种情况下，它可以决定最后一步的玩家是否达到了他们的目标。
- X 的目标是获胜。
- O 的目标是获胜或平局。
因此评估函数可以检查所有 10 条四人行，看看最后上场的玩家是否已经完全占据了这条线。如果找到，评估函数应该 return 1 -- 表明玩家已经达到他们的目标。
接下来，评估函数应该检查 O 是否是最后一个上场的玩家。如果是这样，它可以再次检查所有 10 行四行，并查看 O 是否在 each 行中至少有一个存在。如果是这样，它也应该 return 1 -- 表明 O 已经达到了他们的目标。
在所有其他情况下，评估函数可能 return 0 -- 表示还没有明确的答案。
由于唯一的结果是 0 或 1，评估函数也可以 return 布尔值。我将调用该函数 happy.
极小极大
极小极大函数return是一个值。在这种情况下，我们将支持值 -1、0 或 1：
- -1: 最后上场的玩家无法达到目标
- 0：未定
- 1：最后出场的玩家可以强行达到目标。
Minimax 将执行所有对手的移动并找出哪一个给出“最佳”结果，在这种情况下，其评估值为 1。如果找到这样的移动，则前一个玩家将获得否定的评估返回他们的最后一步，即-1。对于可以从 minimax.
董事会代表
游戏的表现方式有很多种。我选择为两个玩家使用一个位图，每个位置一个位。所以每个玩家都有一个 16 位位图，位图中的每个 1 位代表他们所做的一步。导致特定状态的移动顺序无关紧要。
4 行也可以表示为位图，以便通过用它们覆盖玩家的位图轻松检测到获胜。
步数用数字表示，从 0 到 15。
记忆
Minimax 可以从记忆中受益，这样它就不需要通过相同的搜索树来评估相同的棋盘状态两次。由于我选择用两个 16 位数字表示电路板，因此很容易通过 32 位数字识别（散列）状态。
实施
这是一个 JavaScript 实现。你可以在这里 运行 它，它会输出你给出的两个例子的结果。一个非负整数的输出，意味着该移动是强制获胜。输出 -1 表示不可能强制获胜。
class TicTacToe {
static memo = new Map; // For memoization
constructor(str) {
str = str.toLowerCase().replace(/[^.xo]/gi, "");
if (str.length !== 16) throw "Invalid board size";
this.players = [0x0000, 0x0000]; // bitmaps for both players
this.lines = [ // bitmaps of winning lines
0xF000, 0x0F00, 0x00F0, 0x000F,
0x1111, 0x2222, 0x4444, 0x8888,
0x1248, 0x8421
];
this.turn = 0; // 0 or 1
// collect moves into bitmaps
let bit = 1;
let balance = 0;
for (let ch of str) {
let player = "xo".indexOf(ch);
if (player >= 0) {
this.players[player] ^= bit;
balance += player || -1;
}
bit *= 2;
}
if (balance != 0) throw "Number of X and O should be equal";
}
doMove(move) {
this.players[this.turn] ^= 1 << move;
this.turn ^= 1;
}
undoMove(move) {
this.turn ^= 1;
this.players[this.turn] ^= 1 << move;
}
happy() {
// Returns whether the player (that last moved) has reached their goal (boolean)
// For "X" this means they have 4-in-a-row.
// For "O" this means they have 4-in-a-row OR have a presence in all 10 lines
let mask = this.players[1 - this.turn];
for (let line of this.lines) {
if ((line & mask) === line) return true; // Game over. Last move was winner.
}
if (this.turn == 1) return false;
// Check whether last player ("O") cannot lose:
for (let line of this.lines) {
if ((line & mask) == 0) return false; // Opponent could still win here
}
return true; // Second player is happy with draw
}
getMoveList() {
let occupied = this.players[0] ^ this.players[1];
let moveList = [];
for (let move = 0; move < 16; move++) {
if (((occupied >> move) & 1) == 0) moveList.push(move);
}
return moveList;
}
minimax() { // Return value for player that just played (-1, 0 or 1).
let key = (this.players[0] << 16) + this.players[1];
let value = TicTacToe.memo.get(key); // Using memoization
if (value === undefined) { // Not encountered before
value = 1;
if (!this.happy()) { // Undecided?
for (let move of this.getMoveList()) {
this.doMove(move);
// What is good for opponent is bad for current player:
value = Math.min(value, -this.minimax());
this.undoMove(move);
if (value == -1) break; // Opponent can reach their goal
}
}
TicTacToe.memo.set(key, value); // Memoize...
}
return value;
}
bestMove() { // Returns winning move (0..15) for X or -1 if none found
if (this.happy()) return -1; // "O" already ensured at least a draw.
for (let move of this.getMoveList()) {
this.doMove(move);
let value = this.minimax();
this.undoMove(move);
if (value == 1) return move; // forced win: return this winning move
}
return -1; // no forced win found
}
toString() { // To ease printing...
let str = "";
for (let bit = 1; bit < 0x10000; bit *= 2) {
if (this.players[0] & bit) str += "x";
else if (this.players[1] & bit) str += "o";
else str += ".";
if (bit & 0x8888) str += "\n";
}
return str;
}
}
let game;
// Test case 1:
game = new TicTacToe(`
o...
.ox.
.xxx
xooo`);
console.log(game.toString());
console.log("bestMove() returned", game.bestMove());
// Test case 2:
game = new TicTacToe(`
....
.ox.
.xo.
....`);
console.log(game.toString());
console.log("bestMove() returned", game.bestMove());
人们可以想到许多优化，但由于这已经 运行s 在可接受的时间内，我就这样离开了。