GNOME.org
 

[four-in-a-row] Make negamax method static.

commit 28a8b459b90597ed1f4b1a5287556e9026fcff5a
Author: Arnaud Bonatti <arnaud bonatti gmail com>
Date:   Wed Dec 25 15:09:18 2019 +0100

    Make negamax method static.

 src/ai.vala            | 77 ++++++++++++++++++--------------------------
 src/four-in-a-row.vala |  6 ++--
 src/test-ai.vala       | 86 ++++++++++++++++++++++++--------------------------
 3 files changed, 76 insertions(+), 93 deletions(-)
---
diff --git a/src/ai.vala b/src/ai.vala
index a0e4057..3736c53 100644
--- a/src/ai.vala
+++ b/src/ai.vala
@@ -18,16 +18,10 @@
    with GNOME Four-in-a-row.  If not, see <https://www.gnu.org/licenses/>.
 */
 
-private enum Difficulty { EASY, MEDIUM, HARD; }
-
-private uint8 playgame (string moves_until_now)
+namespace AI
 {
-    DecisionTree t = new DecisionTree ();
-    return t.playgame (moves_until_now);
-}
+    private enum Difficulty { EASY, MEDIUM, HARD; }
 
-private class DecisionTree
-{
     /* Here NEGATIVE_INFINITY is supposed to be the lowest possible value.
        Do not forget int16.MIN ≠ - int16.MAX. */
     private const int16 POSITIVE_INFINITY           =  32000;
@@ -40,28 +34,16 @@ private class DecisionTree
     /* Use plies [level]; EASY/MEDIUM/HARD */
     private const uint8 [] plies = { 4, 7, 7 };
 
-    /* to mantain the status of the board, to be used by the heuristic function, the top left cell is [0, 0] 
*/
-    private Player [,] board;
-    /* next_move_in_column - stores the column number in which next move is to be made */
-    private uint8 next_move_in_column;
-    /* stores the difficulty level of the game */
-    private Difficulty level;
-
-    /* Initializes an empty board */
-    internal DecisionTree ()
-    {
-        // sanity init from a string without any move (and with level easy)
-        init_from_string ("a", out level, out next_move_in_column, out board);
-    }
-
     /*\
     * * internal methods
     \*/
 
     /* returns the column number in which the next move has to be made. Returns uint8.MAX if the board is 
full. */
-    internal uint8 playgame (string vstr)
+    internal static uint8 playgame (string vstr)
     {
-        init_from_string (vstr, out level, out next_move_in_column, out board);
+        Difficulty level;
+        Player [,] board;
+        init_from_string (vstr, out level, out board);
 
         /* if AI can win by making a move immediately, make that move */
         uint8 temp = immediate_win (Player.OPPONENT, ref board);
@@ -75,16 +57,19 @@ private class DecisionTree
             return temp;
 
         /* call negamax tree on the current state of the board */
-        negamax (plies [level], NEGATIVE_INFINITY, POSITIVE_INFINITY, Player.OPPONENT);
+        uint8 next_move_in_column = uint8.MAX;
+        negamax (plies [level], NEGATIVE_INFINITY, POSITIVE_INFINITY, Player.OPPONENT, level, ref board, ref 
next_move_in_column);
 
         /* return the column number in which next move should be made */
         return next_move_in_column;
     }
 
     /* utility function for testing purposes */
-    internal uint8 playandcheck (string vstr)
+    internal static uint8 playandcheck (string vstr)
     {
-        init_from_string (vstr, out level, out next_move_in_column, out board);
+        Difficulty level;
+        Player [,] board;
+        init_from_string (vstr, out level, out board);
 
         uint8 temp = immediate_win (Player.OPPONENT, ref board);
         if (temp < BOARD_COLUMNS)
@@ -94,23 +79,13 @@ private class DecisionTree
         if (temp < BOARD_COLUMNS)
             return temp;
 
-        negamax (plies [level], NEGATIVE_INFINITY, POSITIVE_INFINITY, Player.OPPONENT);
+        /* call negamax tree on the current state of the board */
+        uint8 next_move_in_column = uint8.MAX;
+        negamax (plies [level], NEGATIVE_INFINITY, POSITIVE_INFINITY, Player.OPPONENT, level, ref board, ref 
next_move_in_column);
 
         return next_move_in_column;
     }
 
-    /* utility function for debugging purposes, prints a snapshot of current status of the board */
-    internal void print_board ()
-    {
-        for (uint8 i = 0; i < BOARD_ROWS; i++)
-        {
-            for (uint8 j = 0; j < BOARD_COLUMNS; j++)
-                stdout.printf ("%d\t", board [i, j]);
-            stdout.printf ("\n");
-        }
-        stdout.printf ("\n");
-    }
-
     /*\
     * * setting defaults
     \*/
@@ -118,11 +93,9 @@ private class DecisionTree
     /* vstr is the sequence of moves made until now;  */
     private static void init_from_string (string        vstr,
                                       out Difficulty    level,
-                                      out uint8         next_move_in_column,
                                       out Player [,]    board)
     {
         set_level (vstr, out level);
-        next_move_in_column = uint8.MAX;
 
         /* empty board */
         board = new Player [BOARD_ROWS, BOARD_COLUMNS];
@@ -173,7 +146,7 @@ private class DecisionTree
 
     /* Recursively implements a negamax tree in memory with alpha-beta pruning. The function is first called 
for the root node.
        It returns the value of the current node. For nodes at height == 0, the value is determined by a 
heuristic function. */
-    private int16 negamax (uint8 height, int16 alpha, int16 beta, Player player)
+    private static int16 negamax (uint8 height, int16 alpha, int16 beta, Player player, Difficulty level, 
ref Player [,] board, ref uint8 next_move_in_column)
     {
         /* base case of recursive function, returns if we have reached the lowest depth of DecisionTree or 
the board if full */
         if (height == 0 || board_full (ref board))
@@ -192,7 +165,7 @@ private class DecisionTree
         int16 max = LESS_THAN_NEGATIVE_INFINITY;
 
         /* Local variable that stores the column number in which next move is to be made.
-           Initialized with -1 because we do not know the column number yet. */
+           Initialized with uint8.MAX because we do not know the column number yet. */
         uint8 next = uint8.MAX;
 
         for (uint8 column = 0; column < BOARD_COLUMNS; column++)
@@ -204,7 +177,7 @@ private class DecisionTree
                If so, multiply MAX_HEURIST_VALUE by a height factor to avoid closer threats first.
                Or, we need to go further down the negamax tree. */
             int16 temp = victory (player, column, ref board) ? MAX_HEURIST_VALUE * height
-                                                             : -1 * negamax (height - 1, -1 * beta, -1 * 
alpha, player == Player.OPPONENT ? Player.HUMAN : Player.OPPONENT);
+                                                             : -1 * negamax (height - 1, -1 * beta, -1 * 
alpha, player == Player.OPPONENT ? Player.HUMAN : Player.OPPONENT, level, ref board, ref next_move_in_column);
 
             unmove (column, ref board);
 
@@ -221,7 +194,7 @@ private class DecisionTree
                 break;
         }
 
-        /* If it's the root node, asign the value of next to next_move_in_column */
+        /* hackish: if it's the root node, return the value of the column where to play */
         if (height == plies [level])
             next_move_in_column = next;
 
@@ -350,6 +323,18 @@ private class DecisionTree
         return uint8.MAX;
     }
 
+    /* utility function for debugging purposes, prints a snapshot of current status of the board */
+//    private static void print_board (ref Player [,] board)
+//    {
+//        for (uint8 i = 0; i < BOARD_ROWS; i++)
+//        {
+//            for (uint8 j = 0; j < BOARD_COLUMNS; j++)
+//                stdout.printf ("%d\t", board [i, j]);
+//            stdout.printf ("\n");
+//        }
+//        stdout.printf ("\n");
+//    }
+
     /*\
     * * heuristics
     \*/
diff --git a/src/four-in-a-row.vala b/src/four-in-a-row.vala
index eda16bf..a25e05e 100644
--- a/src/four-in-a-row.vala
+++ b/src/four-in-a-row.vala
@@ -355,7 +355,7 @@ private class FourInARow : Gtk.Application
         {
             vstr [0] = vlevel [ai_level];
             playgame_timeout = Timeout.add (COMPUTER_INITIAL_DELAY, () => {
-                    uint8 c = playgame ((string) vstr);
+                    uint8 c = AI.playgame ((string) vstr);
                     if (c >= BOARD_COLUMNS) // c could be uint8.MAX if board is full
                         return Source.REMOVE;
                     process_move ((uint8) c);
@@ -518,7 +518,7 @@ private class FourInARow : Gtk.Application
             {
                 playgame_timeout = Timeout.add (COMPUTER_MOVE_DELAY, () => {
                         vstr [0] = vlevel [ai_level];
-                        uint8 col = playgame ((string) vstr);
+                        uint8 col = AI.playgame ((string) vstr);
                         if (col >= BOARD_COLUMNS)   // c could be uint8.MAX if the board is full
                             set_gameover (true);
                         var nm = new NextMove ((uint8) col, this);
@@ -780,7 +780,7 @@ private class FourInARow : Gtk.Application
         set_status_message (_("I’m Thinking…"));
 
         vstr [0] = vlevel [/* strong */ 3];
-        uint8 c = playgame ((string) vstr);
+        uint8 c = AI.playgame ((string) vstr);
         if (c >= BOARD_COLUMNS)
             assert_not_reached ();  // c could be uint8.MAX if the board if full
 
diff --git a/src/test-ai.vala b/src/test-ai.vala
index b87a65e..33f13d7 100644
--- a/src/test-ai.vala
+++ b/src/test-ai.vala
@@ -52,99 +52,99 @@ private int main (string [] args)
 private static inline void test_horizontal_win ()
 {
     /*In the first statement below, the AI has made moves into the 1st, 2nd and 3rd columns. To win, AI must 
move in the 4th column.*/
-    assert_true (playgame ("a1727370") == 3);
-    assert_true (playgame ("a7315651311324420") == 5);
-    assert_true (playgame ("a232225657223561611133440") == 3);
-    assert_true (playgame ("a242215322574255543341746677453337710") == 0);
+    assert_true (AI.playgame ("a1727370") == 3);
+    assert_true (AI.playgame ("a7315651311324420") == 5);
+    assert_true (AI.playgame ("a232225657223561611133440") == 3);
+    assert_true (AI.playgame ("a242215322574255543341746677453337710") == 0);
 }
 
 /* Tests if the AI makes moves so as to take up immediate vertical wins.*/
 private static inline void test_vertical_win ()
 {
-    assert_true (playgame ("a1213140") == 0);
-    assert_true (playgame ("a14456535526613130") == 0);
-    assert_true (playgame ("a432334277752576710") == 6);
-    assert_true (playgame ("a547477454544323321712116260") == 1);
+    assert_true (AI.playgame ("a1213140") == 0);
+    assert_true (AI.playgame ("a14456535526613130") == 0);
+    assert_true (AI.playgame ("a432334277752576710") == 6);
+    assert_true (AI.playgame ("a547477454544323321712116260") == 1);
 }
 
 /* Tests if the AI makes moves so as to take up immediate forward diagonal wins.*/
 private static inline void test_forward_diagonal_win ()
 {
-    assert_true (playgame ("a54221164712446211622157570") == 6);
-    assert_true (playgame ("a4256424426621271412117175776343330") == 2);
-    assert_true (playgame ("a132565522322662666775443351131113540") == 3);
-    assert_true (playgame ("a4571311334541225544112245262577767733360") == 5);
+    assert_true (AI.playgame ("a54221164712446211622157570") == 6);
+    assert_true (AI.playgame ("a4256424426621271412117175776343330") == 2);
+    assert_true (AI.playgame ("a132565522322662666775443351131113540") == 3);
+    assert_true (AI.playgame ("a4571311334541225544112245262577767733360") == 5);
 }
 
 /* Tests if the AI makes moves so as to take up immediate backward diagonal wins.*/
 private static inline void test_backward_diagonal_win ()
 {
-    assert_true (playgame ("a5422327343142110") == 0);
-    assert_true (playgame ("a1415113315143220") == 1);
-    assert_true (playgame ("a547323452213345110") == 0);
-    assert_true (playgame ("a4256424426621271412117175776343330") == 2);
+    assert_true (AI.playgame ("a5422327343142110") == 0);
+    assert_true (AI.playgame ("a1415113315143220") == 1);
+    assert_true (AI.playgame ("a547323452213345110") == 0);
+    assert_true (AI.playgame ("a4256424426621271412117175776343330") == 2);
 }
 
 /* Tests if the AI makes moves which prevents HUMAN from taking immediate vertical victories. Consider that 
a HUMAN has 3 balls in the
    first column. The AI's next move should be in the 1st column or else, HUMAN will claim victory on his 
next turn.*/
 private static inline void test_avoid_vertical_loss ()
 {
-    assert_true (playgame ("a42563117273430") == 2);
-    assert_true (playgame ("a3642571541322340") == 3);
-    assert_true (playgame ("a144566264475171137750") == 4);
-    assert_true (playgame ("a54747745454432332171210") == 0);
+    assert_true (AI.playgame ("a42563117273430") == 2);
+    assert_true (AI.playgame ("a3642571541322340") == 3);
+    assert_true (AI.playgame ("a144566264475171137750") == 4);
+    assert_true (AI.playgame ("a54747745454432332171210") == 0);
 }
 
 /* Tests if the AI makes moves which prevents HUMAN from taking immediate forward diagonal victories*/
 private static inline void test_avoid_forward_diagonal_loss ()
 {
-    assert_true (playgame ("a34256477331566570") == 6);
-    assert_true (playgame ("a1445662644751711370") == 6);
-    assert_true (playgame ("a43442235372115113340") == 3);
-    assert_true (playgame ("a4143525567766443543125411170") == 6);
+    assert_true (AI.playgame ("a34256477331566570") == 6);
+    assert_true (AI.playgame ("a1445662644751711370") == 6);
+    assert_true (AI.playgame ("a43442235372115113340") == 3);
+    assert_true (AI.playgame ("a4143525567766443543125411170") == 6);
 }
 
 /* Tests if the AI makes moves which prevents HUMAN from taking immediate backward diagonal victories*/
 private static inline void test_avoid_backward_diagonal_loss ()
 {
-    assert_true (playgame ("a47465234222530") == 2);
-    assert_true (playgame ("a4344223537211510") == 0);
-    assert_true (playgame ("a4141311525513520") == 1);
-    assert_true (playgame ("a1445662644751711377553330") == 2);
+    assert_true (AI.playgame ("a47465234222530") == 2);
+    assert_true (AI.playgame ("a4344223537211510") == 0);
+    assert_true (AI.playgame ("a4141311525513520") == 1);
+    assert_true (AI.playgame ("a1445662644751711377553330") == 2);
 
 }
 
 /* Tests if the AI makes moves which prevents HUMAN from taking immediate horizontal victories*/
 private static inline void test_avoid_horizontal_loss ()
 {
-    assert_true (playgame ("a445360") == 6);
-    assert_true (playgame ("a745534131117114777720") == 1);
-    assert_true (playgame ("a243466431217112323350") == 4);
-    assert_true (playgame ("a24147356465355111336631615240") == 3);
+    assert_true (AI.playgame ("a445360") == 6);
+    assert_true (AI.playgame ("a745534131117114777720") == 1);
+    assert_true (AI.playgame ("a243466431217112323350") == 4);
+    assert_true (AI.playgame ("a24147356465355111336631615240") == 3);
 }
 
 /* Tests if AI can detect full boards, and thus draw games. */
 private static inline void test_draw ()
 {
-    assert_true (playgame ("a1311313113652226667224247766737374455445550") == uint8.MAX);
-    assert_true (playgame ("a6121151135432322433425566474425617635677770") == uint8.MAX);
-    assert_true (playgame ("a4226111412113275256335534443264375577676670") == uint8.MAX);
-    assert_true (playgame ("a4212116575717754775221133434432366655342660") == uint8.MAX);
+    assert_true (AI.playgame ("a1311313113652226667224247766737374455445550") == uint8.MAX);
+    assert_true (AI.playgame ("a6121151135432322433425566474425617635677770") == uint8.MAX);
+    assert_true (AI.playgame ("a4226111412113275256335534443264375577676670") == uint8.MAX);
+    assert_true (AI.playgame ("a4212116575717754775221133434432366655342660") == uint8.MAX);
 }
 
 /* Tests if AI makes valid moves, i.e., between column 1 and column 7. */
 private static inline void test_random ()
 {
-    uint8 x = playgame ("a443256214350");
+    uint8 x = AI.playgame ("a443256214350");
     assert_true (x <= 6);
 
-    x = playgame ("a241473564653551113366316150");
+    x = AI.playgame ("a241473564653551113366316150");
     assert_true (x <= 6);
 
-    x = playgame ("a24357315461711177416622623350");
+    x = AI.playgame ("a24357315461711177416622623350");
     assert_true (x <= 6);
 
-    x = playgame ("a1445662644751711377553333665775446110");
+    x = AI.playgame ("a1445662644751711377553333665775446110");
     assert_true (x <= 6);
 }
 
@@ -165,8 +165,7 @@ private static inline uint8 test_ai_vs_ai (string easier, string harder)
 
         while (true)
         {
-            DecisionTree t = new DecisionTree ();
-            uint8 move = t.playandcheck (e.str);
+            uint8 move = AI.playandcheck (e.str);
             if (move == uint8.MAX)
             {
                 draw++;
@@ -182,8 +181,7 @@ private static inline uint8 test_ai_vs_ai (string easier, string harder)
             e.insert (e.str.length - 1, (move + 1).to_string ());
             m.insert (m.str.length - 1, (move + 1).to_string ());
 
-            DecisionTree d = new DecisionTree ();
-            move = d.playandcheck (m.str);
+            move = AI.playandcheck (m.str);
 
             if (move == uint8.MAX)
             {
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]