Beta Pruning algorithm for a Othello/Reversi game
I'm implementing an Alpha-Beta Pruning algorithm that will be used to get the best move in an Othello game. When the algorithm have reached a leaf node (ie there is no valid moves or it reached the maximum depth) I calculate the heuristic value of that node based on this:
How many bricks does the maximising player (the player that is running the algorithm and is gonna use the move which the algorithm returns) have on the board at this node? (+1 for each brick)
How many valid moves does the maximising player have at this node? (+10 for each move)
How many corner bricks does the maximising player have? (+100 for each corner brick)
The problem is: What should I do when it's not the maximisings players turn in the leaf node? Then it's impossible to calculate his valid moves as it's not his turn. I might have misunderstood the whole alpha-beta pruning algorithm, or atleast how the heuristic function should work. Can someone please give me a hint?
Thanks
Whether you are using the traditional minimax formulation of the algorithm, or a negamax formulation, you are supposed to evaluate the board on the view of the side to move.
Then, both algorithms deal with the values differently; minimax just has separate pieces of code whether it is the MAX or MIN player's turn, while negamax assigns "val = - negamax(child)".
ChessProgrammingWiki has nice explanations and pseudocode: Minimax and Negamax.
链接地址: http://www.djcxy.com/p/56410.html