Ruby:对井字游戏进行alpha-beta修剪

所以,alpha-beta修剪似乎是除了硬编码之外的最有效的algorithm(针对tic tac toe)。 但是,我有问题转换algorithm从链接中提供的C + +示例: http : //www.webkinesia.com/games/gametree.php

玩家是1或0,所以做1人玩家将会切换玩家

WIN = 1 LOSS = -1 DRAW = 0 INFINITY = 100 def calculate_ai_next_move best_move = -1 best_score = -INFINITY cur_player = COMPUTER self.remaining_moves.each do |move| self.make_move_with_index(move, cur_player) score = -self.alphabeta(-INFINITY,INFINITY, 1 - cur_player) self.undo_move(move) if score > best_score best_score = score best_move = move end end return best_move end def alphabeta(alpha, beta, player) best_score = -INFINITY if not self.has_available_moves? return WIN if self.has_this_player_won?(player) == player return LOSS if self.has_this_player_won?(1 - player) == 1 - player else self.remaining_moves.each do |move| break if alpha > beta self.make_move_with_index(move, player) move_score = -alphabeta(-alpha, -beta, 1 - player) self.undo_move(move) if move_score > alpha alpha = move_score next_move = move end best_score = alpha end end return best_score end 

目前,该algorithm玩的非常糟糕。 它将首先select最后一个空间,然后select第一个(从左到右)可用空间。

任何想法与什么是错的呢?

另外,我一直在做TDD,所以我知道self.has_this_player_won?,self.undo_move和self.remaining_moves是正确的。

您需要一个能够重现问题的最小testing用例 – input一个将用algorithm的一个步骤解决的板子,然后使用debugging器进行处理,或者在不可能的情况下打印报表。

你可以找出哪个返回实际上返回了nil值 – 你可以在每条return语句之前的行上插入一个断点,或者在每次返回之前添加一个唯一的print语句。 然后追溯发现零引入的地方。

另一种方法是使用debugging器遍历整个get_best_move函数,并检查它是否符合您的期望(代码足够短,这种方法是现实的)。

其他意见:

  • 电脑没有定义
  • 这看起来更像极小值比alpha-beta
  • 从你的问题不清楚,如果是calculate_ai_next_move或get_best_move返回零。