Heuristic function for a board game AI

Question

I am trying to figure out a better heuristic function for a board game whose rules I will specify after the code. My evaluation function is this:

def evaluate(self, board):
        score = 0
        for i in range(board.LENGTH):
            for j in range(board.WIDTH):
                if board.board[i][j].token == "G":
                    score += 100 * (i+1) + 50 * (j + 1)
                if board.board[i][j].token == "R":
                    score -= 100 * (i+1) + 50 * (j + 1)
return score

The initial board holds green and red tokens as shown. The AI moves first, playing the color opposite yours, attacking your tokens. On the black cells, a token can move either orthogonally (left, right, up, down) or diagonally. If it's on a white cell, you could move orthogonally only.

When you move your token next to the opponent's token, you remove all the opponent's token in that direction. E.g If i move the green token from C4 to C5, I will kill all R tokens on C-6 to C-9. This is called a forward attack. Similarly, if you have a token adjacent to an opponent's token you can move away from it, removing all the tokens in that line.

Obviously, the tokens on the black cells have more possible moves.

What would be a good heuristic function for the AI? What should I change in my current function?

I don't think that can be all of the rules: you haven't given the criteria for victory. — Prune
The criteria for victory is when all the opponents tokens are done. And there's a draw if there are 5 consecutive unsuccessful moves from each side. — Bob
If you move in a line from one opposing token to another, do you remove tokens on both ends of the move? — Prune
No only the ones where i moved from, not the ones where I moved to. — Bob

Prune Prune · Accepted Answer · 2017-11-22T01:29:55

The function you have is, indeed, quite poor: it values the lower-right corner and quantity of pieces. A single piece at D8 is worth more than three in the center.

I suggest that you employ current techniques in AI: instead of asking us to do your research for you, develop a program to explore the space. Develop a wide-based evaluation function and perform a genetic search to optimize the parameters of that function.

For instance, iterate through all of the pieces, but instead of row & col numbers use features of

occupy black square
adjacent enemy pieces
adjacent friendly pieces
on or near edge / corner
available moves

Now, make your evaluation function a linear combination of these features. Pick, say, 100 sets of parameters. Run those programs against one another, in a round-robin tourney.

Keep the top 20 finishers. Make another 80 set of parameters by mutation and cross-overs. Repeat the tourney.

Continue these repetitions until the program strength converges, or at least reaches a level of play that satisfies you.

Heuristic function for a board game AI

1 Answers