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

Question

我创建了 TicTacToe 游戏。我使用 minmax 算法。

当棋盘是 3x3 时，我只计算游戏的每一步可能的移动直到结束，输 -1，平局 0，赢 1。

当谈到 5x5 时，它无法完成(许多选项(如 24^24)所以我创建了评估方法，它给出:10^0 用于一个 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 给出更好的结果，最终这可能与平局如何被视为输球有关。

一方面考虑:

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