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)

          if score > best_score
            best_score = score
            best_move = move

        return best_move

    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
        self.remaining_moves.each do |move|
          break if alpha > beta

          self.make_move_with_index(move, player)
          move_score = -alphabeta(-alpha, -beta, 1 - player)

          if move_score > alpha
            alpha = move_score
            next_move = move
          best_score = alpha
      return best_score

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.


1 Answer 1


You need a minimal test case that reproduces the problem - input a board that will be solved with one step of the algorithm, and follow it with a debugger, or print statements if that isn't possible.

You can find out which return is actually returning the nil value - you could insert a breakpoint on the line previous to each return statement, or add a unique print statement before each return. Then track backwards to discover where the nil was introduced.

Another way would just be to step through the whole get_best_move function using a debugger and check it's doing what you expect (the code is short enough for this approach to be realistic).

Other observations:

  • COMPUTER isn't defined
  • This looks more like minimax than alpha-beta
  • It's not clear from your question if it's the calculate_ai_next_move or the get_best_move that is returning nil.
  • \$\begingroup\$ oh, COMPUTER is a static variable defined at the top of the class. \$\endgroup\$ Feb 1, 2011 at 13:39
  • \$\begingroup\$ @CiscolPPhone, I just updated my question, the code has changed. \$\endgroup\$ Feb 1, 2011 at 19:44
  • 2
    \$\begingroup\$ @DerNalia We prefer that you ask a new question instead of making massive scope changing edits to your existing one. Better for records, and rep and stuff. :) \$\endgroup\$ Feb 1, 2011 at 20:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .