1

Sorry for the image, it's straight from my notes.

alpha

I've been reading over minimax trees and alpha data pruning for the last day and a bit in preparation for my project. Which is an implementation for Othello in c.

I have read a ton of resources about it, and I know it gets asked a lot. Before I start my evaluation functions I would like to understand this fully.

In the attached image, I cannot figure out what the function Min_Node(pos) and Max_Node(pos) would do exactly, any input would be greatly appreciated.

If anyone has any tips or things I should look out for when implementing this and my evaluation function for Othello, I'm willing to take any help I can find.

2 Answers2

0

The minimax algorithm, which is also described here, needs to find moves of optimal value given the current position in the game tree. The position consists out of the board configuration and the current player (which for some games can be decided on the board configuration alone). Usually the value of the moves is defined recursively; for a board in eding position (which is a leaf of the game tree), the value is 1 if player one has won, -1 if player two has won and 0 for a draw game. The value of a move is determined by performing that move and recursively evaluate the value. Then, a move with maximum (for player one) or minimum (for player two) is chosen; in the recursive evaluation, the value is the maximum (or minimum) value of all leaves of the subtree rootet at the current position. This is apparently what the functions mentioned in the original question are supposed to to.

Alpha-beta-pruning, as described here, is a refinement of this approach. As the optimal values are known (they are 1 or -1), evaluation can be stopped as soon as a move with the desired value is found.

This approach is independent from the actual game. However, I suggest a first step where an easier game (such as Tic-Tac-Toe) is used as a toy example which might be easier to debug.

Codor
  • 17,447
  • 9
  • 29
  • 56
  • I'm aware how minimax and alphadata works. I'm just having trouble interpreting the pseudo code given for me to implement. –  Apr 11 '17 at 14:33
0

I managed to figure out what max and min node was, in this case, Max_Node(pos) checks to see if this is the player, and it returns true because this should be maximized and Min_Node(pos) checks if its the opponent, if true, then it should be minimized.