井字游戏启发式 AI
Tic Tac Toe heuristic AI
我为 3x3 井字游戏设计了简单的 AI。但是我既不想做完整搜索,也不想做 MinMax。相反,我想到了一种启发式方法,可以评估所有 9 个字段的值,然后 AI 会选择具有最高值的字段。问题是,我完全不知道如何确定它是否是一个完美(无与伦比)的算法。
详情如下:
每个 Field 在网格上都有几个 WinPaths。中间一个有 4 个(水平、垂直和两个对角线),角各有 3 个(水平、对角线和一个垂直),侧面各有 2 个(水平和垂直)。每个字段的值等于其 WinPaths 值的总和。而 WinPath 值取决于其内容:
- 空:
[ | | ]
- 1 点
- 一个符号:
[X| | ]
- 10 点// can be any symbol in any place
- 两个不同的符号:
[X|O| ]
- 0 分 // they can be arranged in any possible way
- 两个相同的对手符号:
[X|X| ]
- 100 分 // arranged in any of three ways
- 两个相同的 "my" 符号:
[O|O| ]
- 1000 点 // arranged in any of three ways
这种方式例如开始情况的值如下:
3 | 2 | 3
---+---+---
2 | 4 | 2
---+---+---
3 | 2 | 3
不过后面的可以这样(现在X在动):
X | 10| O
---+---+---
O | O |110
---+---+---
X | 20| 20
那么有什么可靠的方法可以判断这个算法是否完美,或者它有什么缺点吗?
PS。我试图(从玩家的角度)创造一个分叉的情况,这样我就可以打败这个人工智能,但我失败了。
Wikipedia: tic-tac-toe 表示只有 362,880 种可能的井字游戏。证明你的算法的一种蛮力方法是彻底搜索游戏树,让你的对手在每一轮尝试每一个可能的移动,看看你的算法是否曾经失败(如果完美,它保证获胜或平局)。 space 足够小,程序可以非常快速地执行此操作。当然,你接下来要证明你的测试程序是正确的。
要知道你的机器人是否足够好,你必须玩很多游戏机器人与顶级玩家以及机器人与市场上最好的机器人(通常是国际象棋或围棋等复杂游戏)。
你试过这个吗(我先玩)?
13| 12| 13
---+---+---
12| 14| 12
---+---+---
13| 12| O
对吗?
| |
---+---+---
| X |
---+---+---
| | O
O |20 |30
---+---+---
20| X |20
---+---+---
30|20 | O
如果我理解得很好,X 下一步就会在拐角处
O |20 | X
---+---+---
20| X |20
---+---+---
30|20 | O
从这里我赢了..
如果这个通过(如果我错过了什么..)那么你的解决方案看起来很完美
我为 3x3 井字游戏设计了简单的 AI。但是我既不想做完整搜索,也不想做 MinMax。相反,我想到了一种启发式方法,可以评估所有 9 个字段的值,然后 AI 会选择具有最高值的字段。问题是,我完全不知道如何确定它是否是一个完美(无与伦比)的算法。
详情如下: 每个 Field 在网格上都有几个 WinPaths。中间一个有 4 个(水平、垂直和两个对角线),角各有 3 个(水平、对角线和一个垂直),侧面各有 2 个(水平和垂直)。每个字段的值等于其 WinPaths 值的总和。而 WinPath 值取决于其内容:
- 空:
[ | | ]
- 1 点 - 一个符号:
[X| | ]
- 10 点// can be any symbol in any place
- 两个不同的符号:
[X|O| ]
- 0 分// they can be arranged in any possible way
- 两个相同的对手符号:
[X|X| ]
- 100 分// arranged in any of three ways
- 两个相同的 "my" 符号:
[O|O| ]
- 1000 点// arranged in any of three ways
这种方式例如开始情况的值如下:
3 | 2 | 3
---+---+---
2 | 4 | 2
---+---+---
3 | 2 | 3
不过后面的可以这样(现在X在动):
X | 10| O
---+---+---
O | O |110
---+---+---
X | 20| 20
那么有什么可靠的方法可以判断这个算法是否完美,或者它有什么缺点吗?
PS。我试图(从玩家的角度)创造一个分叉的情况,这样我就可以打败这个人工智能,但我失败了。
Wikipedia: tic-tac-toe 表示只有 362,880 种可能的井字游戏。证明你的算法的一种蛮力方法是彻底搜索游戏树,让你的对手在每一轮尝试每一个可能的移动,看看你的算法是否曾经失败(如果完美,它保证获胜或平局)。 space 足够小,程序可以非常快速地执行此操作。当然,你接下来要证明你的测试程序是正确的。
要知道你的机器人是否足够好,你必须玩很多游戏机器人与顶级玩家以及机器人与市场上最好的机器人(通常是国际象棋或围棋等复杂游戏)。
你试过这个吗(我先玩)?
13| 12| 13
---+---+---
12| 14| 12
---+---+---
13| 12| O
对吗?
| |
---+---+---
| X |
---+---+---
| | O
O |20 |30
---+---+---
20| X |20
---+---+---
30|20 | O
如果我理解得很好,X 下一步就会在拐角处
O |20 | X
---+---+---
20| X |20
---+---+---
30|20 | O
从这里我赢了..
如果这个通过(如果我错过了什么..)那么你的解决方案看起来很完美