Ruby: implementing alpha-beta pruning for tic-tac-toe

0
votes

So, alpha-beta pruning seems to be the most efficient algorithm out there aside from hard coding (for tic tac toe). However, I'm having problems converting the algorithm from the C++ example given in the link: http://www.webkinesia.com/games/gametree.php

Players are either 1 or 0, so doing 1 - player will switch the player

  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

currently, the algorithm is playing terribly. It will initially pick the last space, and then choose the first (from left to right) available space after that.

Any idea with whats wrong with it?

Also, I've been doing TDD, so I know that self.has_this_player_won?, self.undo_move and self.remaining_moves is correct.

Visit Website