我正在尝试用alpha-beta修剪来实现一个3d tic-tac-toe游戏的minimax。然而,该算法似乎选择了次优路径。
例如,你可以通过直接穿过立方体的中间或者穿过一块木板来取胜。人工智能似乎选择了下一个回合而不是当前回合的最佳单元。
我试过重新创建和使用我返回的启发式算法,但没有取得太大进展不管是哪一层,似乎都有同样的问题。
代码是here。
相关的部分是computers_move
和think_ahead
(还有'2'变体,它们只是我在尝试一种稍微替代的方法)。
我希望这可能是我忽略的一件简单的事情,但据我所知,我不确定问题是什么如果有人能澄清这个问题,我将不胜感激。
def computers_move2(self):
best_score = -1000
best_move = None
h = None
win = False
for move in self.allowed_moves:
self.move(move, self.ai)
if self.complete:
win = True
break
else:
h = self.think_ahead2(self.human, -1000, 1000)
self.depth_count = 0
if h >= best_score:
best_score = h
best_move = move
self.undo_move(move)
else:
self.undo_move(move)
if not win:
self.move(best_move, self.ai)
self.human_turn = True
def think_ahead2(self, player, a, b):
if self.depth_count <= self.difficulty:
self.depth_count += 1
if player == self.ai:
h = None
for move in self.allowed_moves:
self.move(move, player)
if self.complete:
self.undo_move(move)
return 1000
else:
h = self.think_ahead2(self.human, a, b)
if h > a:
a = h
self.undo_move(move)
else:
self.undo_move(move)
if a >= b:
break
return a
else:
h = None
for move in self.allowed_moves:
self.move(move, player)
if self.complete:
self.undo_move(move)
return -1000
else:
h = self.think_ahead2(self.ai, a, b)
if h < b:
b = h
self.undo_move(move)
else:
self.undo_move(move)
if a >= b:
break
return b
else:
diff = self.check_available(self.ai) - self.check_available(self.human)
return diff
最佳答案
结果我的算法看起来运行良好。这个问题是由我的助手函数move
和undo_move
引起的。另外,根本问题是我允许的一组移动。
我注意到当它在探索树的时候,在computer_plays
的最外层循环中移动的次数大大减少了。即使在第一次扫描中,计算机和人类玩家每两圈允许移动的次数也会从27次减少到20次,然后是10次,最后是5次。
结果临时测试的动作没有被替换。所以我把这个集合换成了一个标准列表,并在每次移动/撤消之后对列表进行排序,这样就完全解决了我的问题。