Member Avatar for 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 :)

Edited by tnclark8012 because: n/a
  • 2 Contributors
  • 3 Replies
  • 180 Views
  • 20 Hours Discussion Span
  • Latest Post Latest Post by MyrtleTurtle

Dani AI

Generated

A few practical notes and a compact evaluation strategy that avoids the nested-if brute force was worried about (and clarifies ’s matrix comment — a matrix is just a 2D array).

Keep the board as a 2D array and score lines instead of comparing every pair of stones. Check only four directions (horizontal, vertical, two diagonals). For each occupied cell treat it as a sequence start only if the previous cell in that direction is not the same player — this prevents double counting. Walk forward to count contiguous stones, then inspect the two ends to see if they are empty (open) or blocked. Map (length, openEnds) to a weight and sum player scores; final evaluation = myScore - oppScore. Treat five-in-a-row as an immediate win.

A compact pseudocode sketch:

for each cell (x,y):
  for each direction (dx,dy):
    if board[x][y] == player and not sameAs(x-dx,y-dy):
      count = walkForwardCount(x,y,dx,dy,player)
      leftOpen = isEmpty(x-dx,y-dy)
      rightOpen = isEmpty(x+dx*count,y+dy*count)
      score += weight(count, leftOpen + rightOpen)

Speed tips: restrict move generation to empty cells within a small radius (1–2) of existing stones to cut branching on 15x15 boards; use iterative deepening + good move ordering to let alpha-beta prune aggressively; cache positions with a transposition table and use Zobrist hashing if performance matters. Tune weights by distinguishing open-three, closed-three, open-four, etc., and normalize weights for different board sizes. Finally, keep evaluation incremental where possible (update affected lines when making/unmaking a move) so repeated full-board rescans are avoided.

Recommended Answers

All 3 Replies

Member Avatar for 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. :)

Edited by MyrtleTurtle because: n/a
Member Avatar for 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

Member Avatar for 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! :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.