Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question

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.
share|improve this answer
    
oh, COMPUTER is a static variable defined at the top of the class. –  NullVoxPopuli Feb 1 '11 at 13:39
    
@CiscolPPhone, I just updated my question, the code has changed. –  NullVoxPopuli Feb 1 '11 at 19:44
2  
@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. :) –  Noctrine Feb 1 '11 at 20:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.