I am writing a program for the game of Chomp. You can read the description of the game on Wikipedia, however I'll describe it briefly anyway.
We play on a chocolate bar of dimension n x m, i.e. the bar is divided in n x m squares. At each turn the current player chooses a square and eats everything below and right of the chosen square. So, for example, the following is a valid first move:
The objective is to force your opponent to eat the last piece of chocolate (it is poisoned).
Concerning the AI part, I used a minimax algorithm with depth-truncation. However I can't come up with a suitable position evaluation function. The result is that, with my evaluation function, it is quite easy for a human player to win against my program.
Can anyone:
- suggest a good position evaluation function or
- provide some useful reference or
- suggest an alternative algorithm?