Evaluation function (minmax/a-b pruning)

[tnclark8012]

I've been tasked with implementing either the min-max function or alpha-beta pruning to code AI for the game Gumoku (connect 5, vertical, horizontal, or diagonal).

In both algorithms an evaluation function is called to analyze the board of play. Is there any "easy" way to do this? My initial plan is to store the board as a 2D array and then compare values stored in the array to determine each players position on the board. The board looks something like this:

0 0 0 0 0
1 0 0 1 1
0 0 0 0 0
2 0 1 2 2
0 0 0 0 0

where 0's are open spaces, 1's are player one's pieces and 2's are player two's pieces. In order to evaluate how advantageous the board is I would need to check how many in a row each player has and assign a value to how good it is (i.e. 2 in a row is worth 5, 3 in a row is worth 8 ... 5 in a row is worth 30 and is a win).

The way I started doing is is a vector of points for the position of each player's piece on the board, then comparing adjacent indexes in the board array to see if a player had two or more pieces in a row. However, this seems very inefficient and requires several sets of nested if-statements. Is there a faster, better way to handle this?

Thanks for any input or ideas :)

[MyrtleTurtle]

Have you thought about using a matrix to store the board instead of a 2D array? Of course, you'd still have to compare adjacent positions in the rows/columns.

Maybe you could do something like:

for(int i =0; i<SIZE-1; i++){
   if(rowPos[i] ==rowPos[i+1]){
      points++;
  }
}

Where SIZE is the amount of positions in the row. Then just put it in a function and call it for each row. And make a similar function for the columns.

I'm not sure if this idea would be better or not, since I haven't actually coded it.

You'd have to add checks for if they have two in a row, then two more in a row (assuming your board is always 5x5). Also, the way you want to add your points is different than my code, but it's just an example.

Good luck. :)

[tnclark8012]

Have you thought about using a matrix to store the board instead of a 2D array? Of course, you'd still have to compare adjacent positions in the rows/columns.

Maybe you could do something like:

for(int i =0; i<SIZE-1; i++){
   if(rowPos[i] ==rowPos[i+1]){
      points++;
  }
}

Where SIZE is the amount of positions in the row. Then just put it in a function and call it for each row. And make a similar function for the columns.

I'm not sure if this idea would be better or not, since I haven't actually coded it.

You'd have to add checks for if they have two in a row, then two more in a row (assuming your board is always 5x5). Also, the way you want to add your points is different than my code, but it's just an example.

Good luck. :)

Thanks for the reply. It definitely seems like brute computing force is the only way to evaluate the board... I was hoping there was a better way to do it because my program will be timed and will race other programs. Also, the board can be 5x5 up to 15x15... that's a lot of comparisons! :O

[MyrtleTurtle]

You know what? I should have done more checking before replying. I think that a matrix actually IS a 2d array (or is made by using one?)

heh...live & learn.

There may yet be an easier way of doing this. Maybe another member will be able to help you. Sorry I wasn't much help, but I tried! :)