Skip to main content
deleted 374 characters in body; added 73 characters in body
Source Link

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

#based off http://www.webkinesia.com/games/gametree.php
# (converted from C++ code from the alpha - betaWIN pruning= section)1
# returns 0 if draw
LOSS = -1
DRAW = 0
WIN = 1
@next_moveDRAW = 0
def calculate_ai_next_move
    scoreINFINITY = self.get_best_move(COMPUTER, WIN, LOSS)100
    returndef @next_move
end
calculate_ai_next_move
def get_best_move(player, alpha, beta)
    best_score best_move = nil-1
    score = nil
    ifbest_score not= self.has_available_moves?-INFINITY
      return false 
    elsif self.has_this_player_won?(player)
   cur_player = COMPUTER
 return WIN
    elsif  self.has_this_player_won?(1remaining_moves.each -do player)|move|
      return LOSS
   self.make_move_with_index(move, elsecur_player)
      best_score = alpha
    score = NUM_SQUARES-self.timesalphabeta(-INFINITY,INFINITY, do1 |square|- cur_player)
        if best_score >= betaself.undo_move(move)
          break
        end
  if score > best_score
   
         if self.state[square].nil?
best_score = score
        self.make_move_with_index(square, player)
   best_move = move
     # set to negative of opponent'send
 best move; we only need the returned score;end
        
   # the returned move is irrelevant.return best_move
    end
     
  score = -get_best_movedef alphabeta(1-playeralpha, -beta, -alphaplayer)
        best_score = -INFINITY
          if (score >not bestScore)self.has_available_moves?
         return WIN if @next_moveself.has_this_player_won?(player) === squareplayer
         return LOSS if best_scoreself.has_this_player_won?(1 =- score
player) == 1 - player
      endelse
        self.remaining_moves.each do undo_move(square)|move|
        end
  break if alpha > endbeta
    end
    return best_score
end

the problem is that this is returning nil.

some support methods that are used above:

  
   WAYS_TO_WIN = [[0, 1, 2], [3, 4, 5]self.make_move_with_index(move, [6,player)
 7, 8], [0, 3, 6], [1, 4, 7], [2, 5,move_score 8],[0,= 4-alphabeta(-alpha, 8]-beta, [2,1 4,- 6]]
player)
      
     def has_this_player_won?self.undo_move(playermove)
      result = false
   
    WAYS_TO_WIN.each {|solution| result = self.state[solution[0]]  if contains_win?(solution)move_score }> alpha
      return (result == player)
   alpha end= move_score
    
    def contains_win?(ttt_win_state)
    ttt_win_state.eachnext_move do= |pos|move
      return false if self.state[pos] !=end
 self.state[ttt_win_state[0]] or self.state[pos].nil?
    end
   best_score = alpha
    return true
   end
 
   def make_move(x, y, player)end
        self.set_square(x,y,return player)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.

#based off http://www.webkinesia.com/games/gametree.php
# (converted from C++ code from the alpha - beta pruning section)
# returns 0 if draw
LOSS = -1
DRAW = 0
WIN = 1
@next_move = 0
def calculate_ai_next_move
    score = self.get_best_move(COMPUTER, WIN, LOSS)
    return @next_move
end

def get_best_move(player, alpha, beta)
    best_score = nil
    score = nil
    if not self.has_available_moves?
      return false
    elsif self.has_this_player_won?(player)
      return WIN
    elsif self.has_this_player_won?(1 - player)
      return LOSS
    else
      best_score = alpha
      NUM_SQUARES.times do |square| 
        if best_score >= beta
          break
        end
        
         if self.state[square].nil?
          self.make_move_with_index(square, player)
          # set to negative of opponent's best move; we only need the returned score;
          # the returned move is irrelevant.
          score = -get_best_move(1-player, -beta, -alpha)
          
          if (score > bestScore)
            @next_move = square
            best_score = score
          end
          undo_move(square)
        end
      end
    end
    return best_score
end

the problem is that this is returning nil.

some support methods that are used above:

    WAYS_TO_WIN = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],[0, 4, 8], [2, 4, 6]]

      
     def has_this_player_won?(player)
      result = false
      WAYS_TO_WIN.each {|solution| result = self.state[solution[0]] if contains_win?(solution) }
      return (result == player)
    end
    
    def contains_win?(ttt_win_state)
    ttt_win_state.each do |pos|
      return false if self.state[pos] != self.state[ttt_win_state[0]] or self.state[pos].nil?
    end
    
    return true
  end
 
   def make_move(x, y, player)
        self.set_square(x,y, player)
    end

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.

Source Link

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

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

#based off http://www.webkinesia.com/games/gametree.php
# (converted from C++ code from the alpha - beta pruning section)
# returns 0 if draw
LOSS = -1
DRAW = 0
WIN = 1
@next_move = 0
def calculate_ai_next_move
    score = self.get_best_move(COMPUTER, WIN, LOSS)
    return @next_move
end

def get_best_move(player, alpha, beta)
    best_score = nil
    score = nil
    if not self.has_available_moves?
      return false
    elsif self.has_this_player_won?(player)
      return WIN
    elsif self.has_this_player_won?(1 - player)
      return LOSS
    else
      best_score = alpha
      NUM_SQUARES.times do |square| 
        if best_score >= beta
          break
        end
        
        if self.state[square].nil?
          self.make_move_with_index(square, player)
          # set to negative of opponent's best move; we only need the returned score;
          # the returned move is irrelevant.
          score = -get_best_move(1-player, -beta, -alpha)
          
          if (score > bestScore)
            @next_move = square
            best_score = score
          end
          undo_move(square)
        end
      end
    end
    return best_score
end

the problem is that this is returning nil.

some support methods that are used above:

    WAYS_TO_WIN = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],[0, 4, 8], [2, 4, 6]]

      
    def has_this_player_won?(player)
      result = false
      WAYS_TO_WIN.each {|solution| result = self.state[solution[0]] if contains_win?(solution) }
      return (result == player)
    end
    
   def contains_win?(ttt_win_state)
    ttt_win_state.each do |pos|
      return false if self.state[pos] != self.state[ttt_win_state[0]] or self.state[pos].nil?
    end
    
    return true
  end

   def make_move(x, y, player)
        self.set_square(x,y, player)
    end