python - 在 Negamax 中保存有效动作对速度几乎没有影响
问题描述
我有一个带有 alpha-beta 修剪的普通 Negamax 算法,它是通过迭代加深 (ID) 启动的。我认为要真正使用 ID,我将从深度 1 计算的有效移动保存在表格中,所以下次我去深度 2 并且相同的原始位置到达时,我可以从表格中获取有效移动来节省时间. 但是,我发现这个想法并没有真正节省任何时间,这让我想到:
- 我从未见过有人这样做,出于某种原因不值得吗?
- 我的实现是错误的?
- 我对 Negamax 的工作方式感到困惑,也许这首先是不可能做到的?
这是原始的迭代调用,以及 Negamax 函数本身的片段:
self.valid_moves_history = []
for depth in range(1, s.max_search_depth):
move, evaluation = self.negamax(gamestate, depth, -math.inf, math.inf, s.start_color)
# ----------------------------------------------------------------------------
def negamax(self, gamestate, depth, alpha, beta, color):
if self.zobrist_key in self.valid_moves_history:
children = self.valid_moves_history[self.zobrist_key]
else:
children = gamestate.get_valid_moves()
self.valid_moves_history[key] = children
if depth == 0 or gamestate.is_check_mate or gamestate.is_stale_mate:
return None, e.evaluate(gamestate, depth) * color
# Negamax loop
max_eval = -math.inf
for child in reversed(children):
gamestate.make_move(child[0], child[1])
score = -self.negamax(gamestate, depth - 1, -beta, -alpha, -color)[1]
gamestate.unmake_move()
if score > max_eval:
max_eval = score
best_move = child
alpha = max(alpha, max_eval)
if beta <= alpha:
break
我的完整程序中最耗时的任务是这样分布的(占游戏总运行时间的百分比):
- 计算有效动作:60%
- 评估函数(目前中等复杂度):25%
- Negamax 本身具有查找、表格保存等功能:5%
- 做出/取消动作:4%
计算移动时间这么高是否正常/合理?这是我首先考虑将有效动作保存在列表中的主要原因。
或者有人可以解释为什么这是一个好/坏的主意,我应该怎么做?感谢您的任何意见。
解决方案
我知道这个线程在这一点上已经很老了,但我认为这对某些人仍然有用。您正在谈论的整个主题在 Minimax 中称为转置表,您可以找到许多指向该主题的链接。Negamax 与 Minimax 相同,只是您没有为 Max 和 Min 播放器提供单独的函数,而是您只需调用一个 max 函数并将其转换为负数。我认为首先实现移动排序可能对您更有用,因为它可以使您的程序速度加倍。您还可以找到一种更有效的方法来找到有效的移动来加速程序。
推荐阅读
- java - 在循环中交换数组的值
- html - 通过ajax发送变量和图像
- ruby-on-rails - Rails 设计删除/取消用户不工作
- javascript - 如何在我的 React 表中使用列和行的拖放功能 - ReactJS
- java - GSON如何在第二级序列化中排除属性
- windows-services - 为什么在 Topshelf 中多次调用 Stop 方法
- pyspark - pyspark:删除所有行中具有相同值的列
- java - 从不同的方法访问数据?
- ios - 当我用opencv4构建“gomobile bind”一个go项目时,错误来了,我该如何解决
- c - 如何使用c构建sql查询