[iagno/gnome-3-10] Improve computer player behavior

[Michael Catanzaro <mcatanzaro src gnome org>]

commit 75eb88a9fa96d3803e8397af92e3a9028d09046b
Author: Dave Paul <hi my name is dave gmail com>
Date:   Tue Sep 17 21:21:01 2013 -0600

    Improve computer player behavior
    
    This change actually makes use of the around () and eval_heuristic ()
    methods to improve the play of the AI player. At level 1, the behavior
    is the same as before.
    
    For testing I ran matches against the old computer player which was
    playing LIGHT (both sides were at level 2). I ran a full game for each
    of the 244 potentially unique openings of 8 pieces (before 8 pieces are
    on the board, the computer just plays randomly).
    
    When dark was played by the old code, its record was 100 - 141 - 3.
    When dark was played by the new code, its record was 191 - 47- 6.
    
    This is a significant improvement, and may turn out to be too difficult
    of an opponent, especially at level 3. We could try reducing the search
    depth to compensate... I'm not sure how to judge absolute difficulty of
    the AI.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=708179

 src/computer-player.vala |   38 ++++++++++++++++++++++----------------
 1 files changed, 22 insertions(+), 16 deletions(-)
---
diff --git a/src/computer-player.vala b/src/computer-player.vala
index b3b27c6..04c9813 100644
--- a/src/computer-player.vala
+++ b/src/computer-player.vala
@@ -67,8 +67,10 @@ public class ComputerPlayer
          * At the end of the game try and maximise the number of tokens.
          * Near the end try and push for a win.
          * For the rest of the game try and maximise everything.
+         * Note, for level 1 we default to the "PERFECT" strategy, which is not as
+         * good as the "BEST" strategy, so as not to make the AI too difficult.
          */
-        var strategy = Strategy.BEST;
+        var strategy = (level == 1) ? Strategy.PERFECT : Strategy.BEST;
         if (tiles_remaining <= depth + 10)
             strategy = Strategy.PERFECT;
         else if (tiles_remaining <= depth + 12)
@@ -173,6 +175,10 @@ public class ComputerPlayer
         return b.n_tiles - a.n_tiles;
     }
 
+    /* Perhaps surprisingly, the *lower* the return value from this method,
+     * the "better" the position. So callers want to minimize the result here
+     * to find the best move.
+     */
     private int calculate_heuristic (Game g, Strategy strategy)
     {
         var tile_difference = g.n_dark_tiles - g.n_light_tiles;
@@ -191,11 +197,11 @@ public class ComputerPlayer
 
         /* Try to maximise a number of values */
         default:
-            return tile_difference + around () + eval_heuristic ();
+            return tile_difference - around (g) - eval_heuristic (g);
         }
     }
 
-    private int eval_heuristic ()
+    private static int eval_heuristic (Game g)
     {
         var count = 0;
         for (var x = 0; x < 8; x++)
@@ -203,7 +209,7 @@ public class ComputerPlayer
             for (var y = 0; y < 8; y++)
             {
                 var h = heuristic[y * 8 + x];
-                if (game.get_owner (x, y) != game.current_color)
+                if (g.get_owner (x, y) != g.current_color)
                     h = -h;
                 count += h;
             }
@@ -212,7 +218,7 @@ public class ComputerPlayer
         return count;
     }
 
-    private int around ()
+    private static int around (Game g)
     {
         var count = 0;
         for (var x = 0; x < 8; x++)
@@ -220,20 +226,20 @@ public class ComputerPlayer
             for (var y = 0; y < 8; y++)
             {
                 var a = 0;
-                a += is_empty (x + 1, y);
-                a += is_empty (x + 1, y + 1);
-                a += is_empty (x, y + 1);
-                a += is_empty (x - 1, y + 1);
-                a += is_empty (x - 1, y);
-                a += is_empty (x - 1, y - 1);
-                a += is_empty (x, y - 1);
-                a += is_empty (x + 1, y - 1);
+                a += is_empty (g, x + 1, y);
+                a += is_empty (g, x + 1, y + 1);
+                a += is_empty (g, x, y + 1);
+                a += is_empty (g, x - 1, y + 1);
+                a += is_empty (g, x - 1, y);
+                a += is_empty (g, x - 1, y - 1);
+                a += is_empty (g, x, y - 1);
+                a += is_empty (g, x + 1, y - 1);
 
                 /* Two points for completely surrounded tiles */
                 if (a == 0)
                     a = 2;
 
-                if (game.get_owner (x, y) != game.current_color)
+                if (g.get_owner (x, y) != g.current_color)
                     a = -a;
                 count += a;
             }
@@ -242,9 +248,9 @@ public class ComputerPlayer
         return count;
     }
 
-    private int is_empty (int x, int y)
+    private static int is_empty (Game g, int x, int y)
     {
-        if (x < 0 || x >= 8 || y < 0 || y >= 8 || game.get_owner (x, y) != Player.NONE)
+        if (x < 0 || x >= 8 || y < 0 || y >= 8 || g.get_owner (x, y) != Player.NONE)
             return 0;
 
         return 1;