How should I design a good evaluation function for Connect 4?

Question

I've a java implementation of "Connect 4" game (with a variable number of columns and rows) .

This implementation use (according to the choice of the user) Mini-max algorithm of Mini-max with Alpha-beta pruning with a maximum depth of searching of maxDepth

My problem now is the design of a good evaluation function for the state of the board (this is the value returned at maxDepth).

The value is between -100 (worst choise,it corresponds to a losing situation) and 100 (best choise,it corresponds to a winning situation) where 0 is supposed to be "draw" situation.

Actually I've implemented two functions (I report pseudo-code because the code is very long)

1)

• no win / no lose

--> if table is full ==> draw (0)

--> if table isn't full ==> unsure situation (50)

• win

--> if my win: 100

--> if win of opponent: -100

2)

Of me:
- InARow[0] = maximum number of pieces in a HORIZONTAL in a row
- InARow[1] = maximum number of pieces in a VERTICAL in a row
- InARow[2] = maximum number of pieces in a DIAGONAL (ascending) in a row
- InARow[3] = maximum number of pieces in a DIAGONAL (descending) in a row
Of the opponent
- InARow2[0] = maximum number of pieces in a HORIZONTAL in a row
- InARow2[1] = maximum number of pieces in a VERTICAL in a row
- InARow2[2] = maximum number of pieces in a DIAGONAL (ascending) in a row
- InARow2[3] = maximum number of pieces in a DIAGONAL (descending) in a row

value = (100* (InARow[0] + InARow[1] + InARow[2] + InARow[3]) )/16 - (100* (InARow2[0] + InARow2[1] + InARow2[2] + InARow2[3]) )/16  

I need to design a third (and if possible better) function. Any suggestion?

Thank you in advance.

Answer 1

Just count the number of possible 4 in rows that each player can still make and substract that from each other.

For example, both players start with a score of 7*4 (horizontal) + 4*7 (vertical) + 4*4 (diagonal up) + 4*4 (diagonal down). If red puts one in the left bottom corner, then yellow loses a score of 1 + 1 + 1 + 0 = 3. But if red puts one in the middle instead, yellow loses a score of 4 + 1 + 1 + 1 = 7.

Of course, if any player wins, then the score of the other player is -infinity, regardless of the system above.

Answer 2

you have the base cases ironed out: my win = 100 pts, my loss = -100, tie = 0. The "unsure" case you can kill, it does not reflect the "goodness" of the board. So now you need to fill in the gaps. Cases you want to consider and assign values to:

• I have X in a row (If i have 3 in a row, that's better than only two in a row - your function should favor adding to longer rows over shorter ones)
  
• My opponent has X in a row (Likewise, the more he/she has in a row, the worse off we are)
  
• Count how many rows you are filling in (Placing a piece and forming 2 rows of 3 is better than placing a piece and only forming one row of 3)
• Count how many rows you are blocking (similarly, if you can drop a piece and block two opponents rows of 3, that's better than blocking a single row of 2)