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)

Answer 3

Here are two separate evaluation functions for connect 4

1. One basic evaluation function is as suggested in another answer, we can calculate the number of possible 4 in a rows the player can still make and subtract it from the opponent. You can give different weights or importance to blocks that already have three tiles compared to blocks that have only 1 tile.
2. Another stronger evaluation function can be built using the concept of threats. threat is a square that connects 4 when a tile is dropped there by the opponent. You can simply return the difference in the number of threats by each player, but we can do much better by actually filtering useless threats (like a threat just above an opponents threat, or all threats above a threat by both players) and even assigning bonus for some threats (like lowermost threat of a column or 2 consecutive threats by the same player).

The weights can be tuned by hand or self learned for a larger project.