Index

1. Game tree searching

• 

• the diagram shows that it is blacks turn to move
  • a positive score for black indicates a good move
  • +∞ indicates a win for black
  • 0 indicates a neutral position
  • any value <0 indicates a good position for white
• we assume that white evaluates the board in exactly the same way as black
• if black chooses move 1, white will respond with move a
  • we can see that white is attempting to minimise the score
  • whereas black is attempting to maximise the score
    

2. Minimax algorithm

• def minimax (colour, board):
      if gameOver(board) or lookedFarEnough(board):
          return evaluateScore(board)
      moves = getLegalMoves(colour, board)
      if colour == black:
         score = -infinity;
         for i in moves:
             score = max(minimax(white, makeMove(board, i)),
                         score)
      else:
         score = +infinity;
         for i in moves:
             score = min(minimax(black, makeMove(board, i)),
                         score)
      return score

• we assume
  • getLegalMoves returns a list of legal moves
  • makeMove(board, i) applies a move, i , to a board and returns the new board
• also assume evaluateScore will return a reasonably accurate score based on the board position
• however there is a paradox here:
  • we need an accurate evaluateScore function
  • yet if it were really accurate we wouldn't need to look ahead!
    

3. Evaluation functions

• are the limitation to game tree searching
  • often an evaluation function reports a good score for a potential board position in the future
  • when we get to that position and look ahead the picture may not look as good!
• often called a local maximum, rather similar to hill climbing

4. Returning to Game tree searching

• examine the first game tree diagram
• notice that black calculates the score for move 1, as +10
  • when it examines move 2 (it can remember the previous score)
  • it examines move C which white might play, and it sees this score as 0
• at this point the search algorithm is able to conclude:
  • there is no point in examining move, d, since no matter what score it might deliver, white can still make move, c
  • and the score for move, c, is worse that the score for move 1
  • so there is no point black choosing move, 2, and therefore no point examining move, d

5. AlphaBeta algorithm

• implements the previous optimisation
  • the AlphaBeta algorithm always returns the same results as the minimax algorithm, only it is more efficient
• it is significantly more efficient than the minimax algorithm when the game has a high branching factor
  • for example chess has an approximate branching factor of 20
    • very roughly 20 different moves can be played at each board position
• Alphabeta also is more efficient if the first move it examines is a good move, as this is likely to cut off many subsequent poor moves

6. AlphaBeta

• remember a low value score is good for white
• remember a high value score is good for black
• the parameter, alpha , is the best move for white
  • initially set to ∞
  • low value is good
• the parameter, beta , is the best move for black
  • initially set to -∞
  • high value is good

• def alphaBeta (colour, board, alpha, beta):
      if gameOver(board) or lookedFarEnough(board):
          return evaluateScore(board)
      moves = getLegalMoves(colour, board)
      if colour == black:
        for i in moves:
          try = alphaBeta(white, makeMove(board, i), alpha, beta)
          if try > beta:
            beta = try    # found a better move
          if beta >= alpha:
            return beta   # no point searching further as WHITE would
                          # choose a different previous move
        return beta  # the best score for a move BLACK has found
      else:
        for i in moves:
          try = alphaBeta(black, makeMove(board, i), alpha, beta)
          if try < alpha:
            alpha = try     # found a better move
          if beta >= alpha: # black would chose a previous move
            return alpha
        return alpha  # the best score for a move WHITE has found

• notice that alpha will contain the best known score for white
• notice that beta will contain the best known score for black
• also notice that the loop for black will always return beta
• also notice that the loop for white will always return alpha
• also notice that alphaBeta must only return a value which is a decendent of the current position
• it must not return a cousin value
  

7. Single stepping the alpha beta algorithm

• initially a call is made with the following parameters

• foo = alphaBeta(black, <board>, ∞, -∞)

• only necessary to examine the following code, when considering black

• if gameOver(board) or lookedFarEnough(board):
     return evaluateScore(board)
  moves = getLegalMoves(colour, board)
  if colour == black:
     for i in moves:
        try = alphaBeta(white, makeMove(board, i), alpha, beta)
        if try > beta:
           beta = try    # found a better move
        if beta >= alpha:
           return beta   # no point searching further as WHITE would
                         # choose a different previous move
     return beta  # the best score for a move BLACK has found

• 

• if gameOver(board) or lookedFarEnough(board):
     return evaluateScore(board)
  moves = getLegalMoves(colour, board)

• moves = [1, 2, 3]

• for i in moves:
     # now we see what move white plays if we were to play move 1
     # alpha is +∞, beta is -∞
     try = alphaBeta(white, <board position after move 1>, alpha, beta)
     if try > beta:
        beta = try    # found a better move
     if beta >= alpha:# notice since alpha is +∞ we can ignore at present
        return beta   # no point searching further as WHITE would
                      # choose a different previous move
  return beta  # the best score for a move BLACK has found

• another call to alphaBeta

• 

8. exploring white's response to black move, 1

• def alphaBeta (colour, board, alpha, beta):
      if gameOver(board) or lookedFarEnough(board):
          return evaluateScore(board)
      moves = getLegalMoves(colour, board)
      if colour == black:
        ...
      else:
        #   moves = [a, b]
        #   alpha = +∞
        #   beta  = -∞
        for i in moves:
          try = alphaBeta(black, makeMove(board, i), alpha, beta)
          if try < alpha:
            alpha = try     # found a better move
          if beta >= alpha: # black would chose a previous move
            return alpha
        return alpha  # the best score for a move WHITE has found

9. exploring white's response, a, to black move, 1

•       #   moves = [a, b]
        #   alpha = +∞
        #   beta  = -∞
        for i in moves:
          # first iteration the value of i = move a
          try = alphaBeta(black, makeMove(board, i), alpha, beta)
          # try first time = +10
          if try < alpha:   # first time this will be true
            alpha = try     # alpha = +10
          if beta >= alpha: # false
            return alpha    # not executed
        return alpha  # the best score for a move WHITE has found

10. exploring white's response, b, to black move, 1

• second iteration of loop

•       #   moves = [a, b]
        #   alpha = +10
        #   beta  = -∞
        for i in moves:
          # second iteration the value of i = move b
          try = alphaBeta(black, makeMove(board, i), alpha, beta)
          # try second time = +∞
          if try < alpha:   # second time this will be false
            alpha = try     # not executed
          if beta >= alpha: # false
            return alpha    # not executed
        return alpha  # the best score for WHITE scores +10

• alphaBeta returns +10

•     if colour == black:
        for i in moves:
          try = alphaBeta(white, makeMove(board, i), alpha, beta)
          if try > beta:  # +10
            beta = try    # +10 is better than -∞
          if beta >= alpha: # false
            return beta
        return beta

• try is set to +10

•         try = alphaBeta(white, makeMove(board, i), alpha, +10)

11. exploring white's response, c, to black move, 2

• 

•       #   moves = [c, d]
        #   alpha = ∞
        #   beta  = +10
        for i in moves:
          # first iteration the value of i = move c
          try = alphaBeta(black, makeMove(board, i), alpha, beta)
          # try first time = 0
          if try < alpha:   # first time this will be true
            alpha = try     # alpha = 0
          if beta >= alpha: # true
            return alpha    # return 0  (notice we do not return +10)
        return alpha  # the best score for a move WHITE has found

12. Question

• is it necessary for the Alphabeta search algorithm to examine the board position created by move, f? Give reasons for your answer...

13. Tutorial

• modify the source of Othello so that it takes into consideration position advantage
  • rather than just material
• to do this, use an editor and modify the line 59 of source code from

• #undef USE_CORNER_SCORES

• to

• #define USE_CORNER_SCORES

• save the source and rebuild the game via: gcc o64bit.c
• run the game by: ./a.out
• now modify the game so that the function evaluate in o64bit.c awards points for taking squares: 42, 45, 18 and 21
  • hint you should be able to borrow the code which awards scores for the outer corners and adapt it

Index

This document was produced using groff-1.22.