title: Algorithm for the game of Chomp
body: <p>I am writing a program for the game of Chomp. You can read the description of the game on <a href="http://en.wikipedia.org/wiki/Chomp" rel="noreferrer">Wikipedia</a>, however I'll describe it briefly anyway.</p>
  
  <p>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:</p>
  
  <p><img src="https://i.stack.imgur.com/RYRQW.png" alt="enter image description here"></p>
  
  <p>The objective is to force your opponent to eat the last piece of chocolate (it is poisoned).</p>
  
  <p>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.</p>
  
  <p>Can anyone:</p>
  
  <ul>
  <li>suggest a good position evaluation function or</li>
  <li>provide some useful reference or</li>
  <li>suggest an alternative algorithm?</li>
  </ul>