井字游戏战略性减少 [英] TicTacToe strategic reduction

问题描述

我决定编写一个解决TicTacToe的小程序，以尝试一些修剪技术对普通游戏的影响.使用minimax求解的完整游戏树最终只包含549,946种可能的游戏.通过alpha-beta修剪，评估所需的状态数减少到18,297.然后，我应用了一个换位表，将数字减少到2,592.现在，我想看看这个数字有多低.

I decided to write a small program that solves TicTacToe in order to try out the effect of some pruning techniques on a trivial game. The full game tree using minimax to solve it only ends up with 549,946 possible games. With alpha-beta pruning, the number of states required to evaluate was reduced to 18,297. Then I applied a transposition table that brings the number down to 2,592. Now I want to see how low that number can go.

我要应用的下一个增强功能是策略性的降低.基本思想是合并具有同等战略价值的国家.例如，在第一步中，如果X先打，选择一个角而不是另一个就没有策略上的差异(假设您的对手打得最佳).在相同的情况下，板壁的中心也是如此，并且该中心也很重要.通过只减少到重要状态，您在第一步中只得到3个状态来进行评估，而不是9个.该技术应该非常有用，因为它会修剪游戏树顶部附近的状态.这个想法来自CMU小组创建的GameShrink方法，只是我试图避免编写一般形式，而只是做了将技术应用于TicTacToe所需的工作.

The next enhancement I want to apply is a strategic reduction. The basic idea is to combine states that have equivalent strategic value. For instance, on the first move, if X plays first, there is nothing strategically different (assuming your opponent plays optimally) about choosing one corner instead of another. In the same situation, the same is true of the center of the walls of the board, and the center is also significant. By reducing to significant states only, you end up with only 3 states for evaluation on the first move instead of 9. This technique should be very useful since it prunes states near the top of the game tree. This idea came from the GameShrink method created by a group at CMU, only I am trying to avoid writing the general form, and just doing what is needed to apply the technique to TicTacToe.

为了实现这一点，我修改了哈希函数(用于换位表)，以枚举所有战略上等效的位置(使用旋转和翻转功能)，并仅返回每个板的最低值.不幸的是，现在我的程序认为X可以在第一个开始时从一个空局中赢得5步胜利.经过长时间的调试，对我来说很明显，该程序始终将具有战略意义的最低动作返回该动作(我将最后一个动作存储在换位表中作为我的状态的一部分).有什么更好的方法可以添加此功能，或者有一种简单的方法来确定适用于当前情况的正确动作，以及已经执行的操作?

In order to achieve this, I modified my hash function (for the transposition table) to enumerate all strategically equivalent positions (using rotation and flipping functions), and to only return the lowest of the values for each board. Unfortunately now my program thinks X can force a win in 5 moves from an empty board when going first. After a long debugging session, it became apparent to me the program was always returning the move for the lowest strategically significant move (I store the last move in the transposition table as part of my state). Is there a better way I can go about adding this feature, or a simple method for determining the correct move applicable to the current situation with what I have already done?

推荐答案

出于好奇，我编写了一个程序来构建完整的换位表来玩游戏，而无需任何其他逻辑.考虑到8个对称性，并假设计算机(X)启动并具有确定性，那么只需要49个表项即可！

Out of curiosity, I wrote a program to build a full transposition table to play the game without any additional logic. Taking the 8 symmetries into account, and assuming computer (X) starts and plays deterministic, then only 49 table entries are needed!

1个空板条目

2个条目中有5个条目

5 entries for 2 pieces

21个条目，共4个

18个条目，共6件

4个条目，共8件

这篇关于井字游戏战略性减少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！