How to create an evaluation function for a board game(wizwoz) result

Question

The game is named wizwoz:

Two players, red (referred as r) and gold (referred as g) initially select two values n and k. An n × n board is created with k "r" and k "g" randomly placed on the board. Starting with player r, each player puts his/her letter(“r” for player r, “g” for payer g) in one of the empty squares on the board. After the board is filled, each player's score is equal to the largest connected region on the board filled with that player's color (where a connected region is one where for any two squares in the region a path exists consisting of only N/S/E/W moves). The player with the highest score wins, and is awarded the difference between his/her score and the score of the other player. Two examples of finished games are shown below, with the largest connected regions for each player outlined. Note that in the second example the two sections with 2 r each are not connected.

Im writing the alpha-beta prunning algorithm and stuck with the evaluation function.

Any help? Pseudocode is preferable.

Answer 1

Start with a really simple evaluation function. For example, just use the current size of the largest component. After you get an ai working, you can worry about tuning the evaluation heuristics.

Here's example pseduocode (not tested)

components = {k:set([k]) for k in board}
def contract(k1, k2):
    if color(k1) != color(k2):
        return
    new = components[k1]
    if k2 not in new:
        new.union_update(components[k2])
        for x in components[k2]:
            components[x] = new

for x,y:
    contract(board[x,y], board[x,y+1])
    contract(board[x,y], board[x+1,y])

return max(map(len, components))