Search code examples
javaheuristicsevaluation-function

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

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.

Solution

  • 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.