大型TicTacToe 5x5电路板的相当不错的启发式评估规则 [英] Pretty good heuristic evaluation rules for big TicTacToe 5x5 board

问题描述

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

I have created TicTacToe game. I use minmax algorithm.

当棋盘为3x3时，我只是计算一场比赛的所有可能动作，直到结束，-1表示输球，0表示平局，1表示获胜.

When the board is 3x3 I just calculate every possible move for a game till the end and -1 for loss, 0 for tie, 1 for win.

当涉及到5x5时，它是不可能完成的(对于许多选项(例如24 ^ 24))，因此我创建了一种评估方法，该方法给出:一个CIRCLE内联为10 ^ 0，两个CIRCLE内联为10 ^ 1 ，. ..，10 ^ 4表示5个CIRCLES内联，但这没用.

When it comes to 5x5 it can't be done(to many options(like 24^24) so I have created evaluation method which gives: 10^0 for one CIRCLE inline, 10^1 for 2 CIRCLE inline, ..., 10^4 for 5 CIRCLES inline, but it is useless.

有人对评估有更好的主意吗?

Does anybody have better idea for assesment?

示例:

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.

这是我现在的评估方法:

This is my evaluation method now:

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;
    }

推荐答案

第一个举动之后的选项数量(可能的移动顺序)为24！而不是24 ^ 24.仍然太高了

Number of options (possible sequences of moves) after the first move is 24! and not 24^24. It is still a too much high

数字，因此实施启发式是正确的.

number so it is correct to implement an heuristic.

请注意，关于良好启发式的答案必定基于作者的观点，因此我给出了自己的观点，但找到了

Note that answers about good heuristics are necessarily based on the opinion of the writer so I give my opinion but to find

在什么是最佳启发式"中，您应该通过以下方式使各种想法相互冲突:

out what is "the best heuristic" you should make the various ideas playing one against the other in the following way:

• 采用您要比较的两种启发式方法A和B
• 随机生成一个初始配置
• 让A和O一起玩，B和X一起玩
• 在相同的起始配置中，让A与X一起玩，B与O一起玩
• 获得其中一项获胜的统计数据

现在，我想到了获胜序列长度为n的nxn运动场的良好可能启发式起点:

Now my thoughts about good possible heuristics starting points for an nxn playfield with winning sequence length of n:

• 由于玩家的获胜条件是它形成其记号的笔直序列，所以我的想法是将每个玩家仍然可以建立这样的笔直序列的可能性的数量用作基值.
• 在理想情况下，O和X都有可能以几种方式实现获胜顺序:
  • 水平可能性:n
  • 垂直可能性:n
  • 对角线可能性:2
  • 总可能性:2n + 2
  • since the winning condition for a player it to form a straight sequence of its marks my idea is to use as base values the number of possibilities that each player has still available to built such a straight sequence.
  • in an empty field both O and X have ideally the possibility to realize the winning sequence in several ways:
    • horizontal possibilities: n
    • vertical possibilities: n
    • diagonal possibilities: 2
    • total possibilities: 2n+2
    • 在一个玩家移动之后，仍然可用的可能性是:
      • 对他保持不变
      • 等于或降低对手(如果将标记放置在考虑的玩家尚未放置任何标记的行/列/对角线中)
      • after a move of one player the umber of still available possibilities are:
        • unchanged for him
        • equal or lowered for the opponent (if the mark has been placed in a row/col/diagonal where no marks had already been placed by the considered player)
        • -k *且k> 1可能会带来更好的结果，最终这可能与如何考虑输球有关平局有关.

        侧面考虑:

        • 游戏场单元为n ^ 2
        • 如果我们将获胜的长度保持等于场边大小，则获胜的可能性为2n + 2
        • 这给我的想法是，尺寸增加得越多，玩的乐趣就越小，因为少量移动(相对于运动场区域)后平局的概率越来越高.
        • 基于这个原因，我认为获胜长度小于n(例如独立于战场大小的3)的游戏更有趣.
          • 命名为l的获胜长度，我们得出可能性的数量为2 *((n + 1-l)*(2n + 1-l))= O(n ^ 2)，因此与场地面积成正比
          • playfield cells are n^2
          • winning possibilities are 2n+2 if we keep the winning length equal to the field edge size
          • this give me the idea that the more the size is increased the less interesting is to play because the probability of a draw after a low number of moves (with reference to the playfield area) becomes higher and higher.
          • for this reason I think that the game with a winning length lower that n (for example 3 independently from the playfield size) is more interesting.
            • Named l the wining length we have that the number of possibilities is 2*((n+1-l)*(2n+1-l)) = O(n^2) and so well proportioned with the field area.

            这篇关于大型TicTacToe 5x5电路板的相当不错的启发式评估规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！