java - 大型 TicTacToe 5x5 棋盘的非常好的启发式评估规则

Question

我创建了 TicTacToe 游戏。我使用最小最大算法。

当棋盘为 3x3 时，我只是计算游戏直到结束为止的所有可能的移动，-1 表示失败，0 表示平局，1 表示获胜。

当涉及到 5x5 时，它无法完成(对于许多选项(例如 24^24)，因此我创建了评估方法，该方法给出:10^0 对于 1 个 CIRCLE 内联，10^1 对于 2 个 CIRCLE 内联，。 ..，10^4 为 5 个 CIRCLES 内联，但没有用。

有人有更好的评估想法吗？

示例:

O|X|X| | |
----------
 |O| | | |
----------
X|O| | | |
----------
 | | | | |
----------
 | | | | |

Evaluation -10, 2 circles across once and inline once (+200), 2 crosses inline(-100), and -1 three times and + 1 three times for single cross and circle.

这是我现在的评估方法:

public void setEvaluationForBigBoards() {
        int evaluation = 0;
        int howManyInLine = board.length;
        for(; howManyInLine > 0; howManyInLine--) {
            evaluation += countInlines(player.getStamp(), howManyInLine);
            evaluation -= countInlines(player.getOppositeStamp(), howManyInLine);
        }
        this.evaluation = evaluation;
    }

    public int countInlines(int sign, int howManyInLine) {
        int points = (int) Math.pow(10, howManyInLine - 1);
        int postiveCounter = 0;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                //czy od tego miejsca jest cos po przekatnej w prawo w dol, w lewo w dol, w dol, w prawo
                if(toRigth(i, j, sign, howManyInLine))
                    postiveCounter++;
                if(howManyInLine > 1) {
                    if(toDown(i, j, sign, howManyInLine))
                        postiveCounter++;
                    if(toRightDiagonal(i, j, sign, howManyInLine))
                        postiveCounter++;
                    if(toLeftDiagonal(i, j, sign, howManyInLine))
                        postiveCounter++;
                }
            }
        }
        return points * postiveCounter;
    }

Answer 1

第一次移动后的选项数量(可能的移动顺序)是 24!而不是 24^24。它仍然是一个过高的数字，因此实现启发式方法是正确的。

请注意，关于好的启发式的答案必然基于作者的意见，因此我给出我的意见，但要找出什么是“最好的启发式”，您应该通过以下方式使各种想法相互竞争:

• 采用您想要比较的两个启发式 A 和 B
• 随机生成起始配置
• 让 A 和 O 一起玩，B 和 X 一起玩
• 在相同的起始配置中，让 A 与 X 一起玩，B 与 O 一起玩
• 统计哪一方获胜较多

现在我对获胜序列长度为 n 的 nxn 游戏场的良好可能启发式起点的想法:

• 由于玩家的获胜条件是形成其标记的直线序列，因此我的想法是使用每个玩家仍可用于构建此类直线序列的可能性数量作为基值。
• 在空场中，O 和 X 理想情况下都有可能通过多种方式实现获胜顺序:
  • 水平可能性:n
  • 垂直可能性:n
  • 对角线的可能性:2
  • 总可能性:2n+2
• 在一轮中间，玩家的剩余机会数计算如下:<the number of rows without opponent's marks> + <the number of columns without opponent's marks> + <the number of diagonals without opponent's marks>
• 而不是每次都计算所有，可以认为:
  • 一名玩家移动后，仍然可用的可能性数量为:
    • 对他来说没有改变
    • 与对手相同或较低(如果标记已放置在行/列/对角线上，而所考虑的玩家尚未放置标记)
• 作为启发，我可以建议:<my possibilities> - <opponent possibilities>
  • 有可能 <my possibilities> - k * <opponent possibilities> k > 1 会给出更好的结果，最终这可能与如何考虑平局与输球有关。

一方面考虑:

• 比赛 field 单元格为 n^2
• 如果我们保持获胜长度等于 field 边缘大小，获胜的可能性是 2n+2
• 这给了我这样的想法:尺寸增加得越多，玩起来就越没意思，因为在少量移动(引用比赛 field 区域)后平局的概率会变得越来越高。
• 出于这个原因，我认为获胜长度低于 n(例如与比赛 field 大小无关的 3)的游戏更有趣。
  • 将 l 命名为获胜长度，可能性的数量为 2*((n+1-l)*(2n+1-l)) = O(n^2)与 field 面积的比例非常好。