[four-in-a-row] Replaced Velena based old AI with a new AI.
- From: Mario Wenzel <mariowenzel src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [four-in-a-row] Replaced Velena based old AI with a new AI.
- Date: Wed, 11 Jun 2014 16:54:12 +0000 (UTC)
commit 14b0b68a98c26ca25858f57e06b300a813d5e6ff
Author: Nikhar Agrawal <nikharagrawal2006 gmail com>
Date: Wed Jun 11 16:19:58 2014 +0530
Replaced Velena based old AI with a new AI.
This AI scales according to the difficulty
levels and is beatable. Much more appropriate
for our target audience.
configure.ac | 7 +-
src/Makefile.am | 58 ++-
src/adjmtrx.c | 284 ------------
src/ai.vala | 540 ++++++++++++++++++++++
src/bintree.c | 158 -------
src/con4vals.h | 37 --
src/connect4.c | 403 ----------------
src/connect4.h | 195 --------
src/evaluate.c | 1340 ------------------------------------------------------
src/heurist.c | 611 -------------------------
src/heurist.h | 25 -
src/ia_main.c | 1174 -----------------------------------------------
src/main.c | 15 +-
src/pbsolver.c | 318 -------------
src/playgame.c | 103 -----
src/pnsearch.h | 89 ----
src/proto.h | 59 ---
src/test-ai.vala | 219 +++++++++
18 files changed, 814 insertions(+), 4821 deletions(-)
---
diff --git a/configure.ac b/configure.ac
index 5afee38..4427c0b 100644
--- a/configure.ac
+++ b/configure.ac
@@ -7,6 +7,7 @@ AM_MAINTAINER_MODE
GNOME_MAINTAINER_MODE_DEFINES
AC_CONFIG_HEADERS([config.h])
+AM_PROG_VALAC([0.22])
AM_PROG_CC_C_O
GLIB_GSETTINGS
@@ -23,12 +24,16 @@ PKG_CHECK_MODULES(FOUR_IN_A_ROW, [
gtk+-3.0 >= $GTK_REQUIRED
librsvg-2.0 >= $RSVG_REQUIRED
libcanberra-gtk3 >= $CANBERRA_GTK_REQUIRED
- zlib
])
AC_PATH_PROG([APPDATA_VALIDATE], [appdata-validate], [/bin/true])
AC_PATH_PROG([DESKTOP_FILE_VALIDATE], [desktop-file-validate], [/bin/true])
+AC_PATH_PROG([GTESTER], [gtester])
+if ! test -x "${GTESTER}" ; then
+ AC_MSG_ERROR([Please install gtester])
+fi
+
dnl ###########################################################################
dnl Internationalization
dnl ###########################################################################
diff --git a/src/Makefile.am b/src/Makefile.am
index 2cd8ff9..4b25d91 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1,5 +1,7 @@
bin_PROGRAMS = four-in-a-row
+check_PROGRAMS = ai-test
+
four_in_a_row_SOURCES = main.h \
main.c \
gfx.h \
@@ -8,30 +10,18 @@ four_in_a_row_SOURCES = main.h \
prefs.c \
theme.c \
theme.h \
- adjmtrx.c \
- bintree.c \
- con4vals.h \
- connect4.h \
- connect4.c \
- evaluate.c \
games-controls.c \
games-controls.h \
games-gridframe.c \
games-gridframe.h \
games-stock.c \
games-stock.h \
- heurist.h \
- heurist.c \
- ia_main.c \
- pbsolver.c \
- playgame.c \
- pnsearch.h \
- proto.h \
- rules.h
+ rules.h \
+ $(ai_C) \
+ $(ai_HEADER)
four_in_a_row_CPPFLAGS = \
- -I$(top_srcdir) \
- $(AM_CPPFLAGS)
+ -I$(top_srcdir)
four_in_a_row_CFLAGS = \
-DDATA_DIRECTORY=\"$(datadir)/four-in-a-row\" \
@@ -42,6 +32,40 @@ four_in_a_row_CFLAGS = \
four_in_a_row_LDADD = \
$(FOUR_IN_A_ROW_LIBS)
- -lz
+
+ai_VALA = ai.vala
+
+ai_HEADER = ai.h
+
+ai_C = $(ai_VALA:.vala=.c)
+
+$(ai_HEADER): $(ai_VALA)
+ $(V_VALAC) $(VALAC) -C --basedir=$(srcdir) --directory=$(builddir) --header=ai.h \
+ --pkg glib-2.0 --pkg gio-2.0 --pkg posix --use-header $(VALAFLAGS) $^
+
+$(ai_C) : $(ai_HEADER)
+
+ai_test_SOURCES = \
+ ai.vala \
+ test-ai.vala
+
+ai_test_CPPFLAGS = \
+ $(FOUR_IN_A_ROW_CFLAGS)
+
+ai_test_LDADD = \
+ $(FOUR_IN_A_ROW_LIBS)
+
+check-local: $(check_PROGRAMS)
+ $(GTESTER) --keep-going --verbose $(check_PROGRAMS)
+
+BUILT_SOURCES = \
+ $(ai_C) \
+ $(ai_HEADER)
+
+EXTRA_DIST = $(BUILT_SOURCES)
+
+MAINTAINERCLEANFILES = \
+ $(BUILT_SOURCES) \
+ four_in_a_row_vala.stamp
-include $(top_srcdir)/git.mk
diff --git a/src/ai.vala b/src/ai.vala
new file mode 100644
index 0000000..247f474
--- /dev/null
+++ b/src/ai.vala
@@ -0,0 +1,540 @@
+/* -*- Mode: vala; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ *
+ * Copyright © 2014 Nikhar Agrawal
+ *
+ * This file is part of Four-in-a-row.
+ *
+ * Four-in-a-row is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * Four-in-a-row is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Four-in-a-row. If not, see <http://www.gnu.org/licenses/>.*/
+
+
+/*Here NEG_INF is supposed to be the lowest possible int value. int.MIN
+MAX_HEURIST_VALUE is the maximum value that the heuristic functions can return.
+It is returned when AI wins. -1*MAX_HEURIST_VALUE is returned when Human wins
+MAX_HEURIST_VALUE < NEG_INF/plies */
+const int NEG_INF = -100000;
+const int MAX_HEURIST_VALUE = 10000;
+const int BOARD_ROWS = 6;
+const int BOARD_COLUMNS = 7;
+enum Player { NONE, HUMAN, AI;}
+enum Difficulty {EASY, MEDIUM, HARD;}
+
+int playgame (string moves_until_now)
+{
+ var t = new DecisionTree();
+ return t.playgame (moves_until_now);
+}
+
+public class DecisionTree
+{
+ /* to mantain the status of the board, to be used by the heuristic function, the top left cell is 0,0
*/
+ private Player[,] board = new Player [BOARD_ROWS, BOARD_COLUMNS];
+ /* plies - depth of the DecisionTree*/
+ private int plies = 8;
+ /* last_moving_player - The player who made the last move, set to Player.NONE if no one has made a
move yet*/
+ private Player last_moving_player = Player.NONE;
+ /* next_move_in_column - stores the column number in which next move is to be made*/
+ private int next_move_in_column = -1;
+ /* stores the difficulty level of the game*/
+ private Difficulty level;
+
+ /* Initializes an empty board*/
+ public DecisionTree ()
+ {
+ for (int i=0; i < BOARD_ROWS; i++)
+ {
+ for (int j=0; j < BOARD_COLUMNS; j++)
+ {
+ board[i,j] = Player.NONE;
+ }
+ }
+ }
+
+ /* utility function for debugging purposes, prints a snapshot of current status of the board*/
+ public void print_board ()
+ {
+ for (int i=0; i< BOARD_ROWS; i++)
+ {
+ for (int j = 0; j < BOARD_COLUMNS; j++)
+ {
+ stdout.printf("%d\t",board[i,j]);
+ }
+ stdout.printf("\n");
+ }
+ stdout.printf("\n");
+ }
+
+ /* 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 int negamax (int height, int alpha, int beta)
+ {
+
+ /* 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())
+ {
+ if (last_moving_player == Player.HUMAN)
+ return heurist();
+ else if (last_moving_player == Player.AI)
+ return -1 * heurist();
+ else
+ return 0;
+ }
+
+ /* Local variable that stores the maximum value returned by the node's children so far.
+ None of the children have returned anything so far. Hence, it is initialized with NEG_INF*/
+ int max = NEG_INF;
+
+ /* 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.*/
+ int next = -1;
+
+ for (int i=0; i < BOARD_COLUMNS; i++)
+ {
+ /* make a move into the i'th column*/
+ if (move(i))
+ {
+ int temp;
+
+ /* victory() checks if making a move in the i'th column results in a victory
for someone. */
+ /* Multiply by a height factor to avoid closer threats first */
+ if (last_moving_player == Player.HUMAN)
+ temp = -1 * victory(i) * height;
+ else
+ temp = victory(i) * height;
+
+ /* if making a move in this column resulted in a victory for someone,
temp!=0, we do not need to go
+ further down the negamax tree*/
+ if (temp == 0)
+ temp = -1 * negamax(height - 1, -1 * beta, -1 * alpha);
+
+ unmove(i);
+
+ if (temp > max)
+ {
+ next = i;
+ max = temp;
+ }
+
+
+ if (temp > alpha)
+ {
+ alpha = temp;
+ }
+
+
+ if (alpha >= beta)
+ {
+ break;
+ }
+
+ }
+ }
+
+ /* If it's the root node, asign the value of next to next_move_in_column */
+ if (height == plies)
+ next_move_in_column = next;
+
+
+ return max;
+ }
+
+ /* returns MAX_HEURIST_VALUE if AI has won as a result of the last move made, NEG_INF if HUMAN has
won, 0 if no one has won
+ the game yet. The argument i is the column in which the last move was made. */
+ private int victory (int i)
+ {
+ int cell;
+
+ /* board[cell,i] would now be the cell on which the last move was made */
+ for (cell = 0; cell < BOARD_ROWS && board[cell,i] == Player.NONE; cell++);
+
+ int temp = 0;
+
+ temp = vertical_win(cell,i);
+ if (temp != 0) return temp;
+
+ temp = horizontal_win(cell,i);
+ if (temp != 0) return temp;
+
+ temp = backward_diagonal_win(cell,i);
+ if (temp != 0) return temp;
+
+ temp = forward_diagonal_win(cell,i);
+ return temp;
+
+ }
+
+ /* all the win functions that follow return 0 is no one wins, MAX_HEURIST_VALUE if AI wins, -1 *
MAX_HEURIST_VALUE if human wins */
+ private int forward_diagonal_win (int i, int j)
+ {
+ int count = 0;
+
+ for (int k = i, l = j; k >= 0 && l < BOARD_COLUMNS && board[k,l] == last_moving_player; k--,
l++, count++);
+ for (int k = i + 1, l = j - 1; k < BOARD_ROWS && l >= 0 && board[k,l] == last_moving_player;
k++, l--, count++);
+
+ if (count >= 4)
+ {
+ if (last_moving_player == Player.HUMAN)
+ return -1 * MAX_HEURIST_VALUE;
+ else
+ return MAX_HEURIST_VALUE;
+ }
+
+ return 0;
+ }
+
+ private int backward_diagonal_win (int i, int j)
+ {
+ int count = 0;
+
+ for (int k = i, l = j; k >= 0 && l >= 0 && board[k,l] == last_moving_player; k--, l--,
count++);
+ for (int k = i + 1, l = j + 1; k < BOARD_ROWS && l < BOARD_COLUMNS && board[k,l] ==
last_moving_player; k++, l++, count++);
+
+ if (count >= 4)
+ {
+ if (last_moving_player == Player.HUMAN)
+ return -1 * MAX_HEURIST_VALUE;
+ else
+ return MAX_HEURIST_VALUE;
+ }
+
+ return 0;
+ }
+
+ private int horizontal_win (int i, int j)
+ {
+ int count = 0;
+
+ for (int k = j; k >= 0 && board[i,k] == last_moving_player; k--, count++);
+ for (int k = j+1; k < BOARD_COLUMNS && board[i,k] == last_moving_player; k++, count++);
+
+ if (count >= 4)
+ {
+ if (last_moving_player == Player.HUMAN)
+ return -1 * MAX_HEURIST_VALUE;
+ else
+ return MAX_HEURIST_VALUE;
+ }
+
+ return 0;
+ }
+
+ private int vertical_win (int i, int j)
+ {
+ int count = 0;
+
+ for (int k = i; k < BOARD_ROWS && board[k,j] == last_moving_player; k++ , count++);
+
+ if (count >= 4)
+ {
+ if (last_moving_player == Player.HUMAN)
+ return -1 * MAX_HEURIST_VALUE;
+ else
+ return MAX_HEURIST_VALUE;
+ }
+
+ return 0;
+ }
+
+ /*returns true if the board is full, false if not*/
+ private bool board_full ()
+ {
+ bool empty = false;
+ for (int i = 0 ; i < BOARD_COLUMNS ; i++)
+ {
+ if (board[0,i] == Player.NONE)
+ {
+ empty = true;
+ break;
+ }
+ }
+ return !empty;
+ }
+
+ /* makes a move into the i'th column. Returns true if the move was succesful, false if it wasn't*/
+ private bool move (int i)
+ {
+ int cell;
+
+ for(cell = BOARD_ROWS - 1; cell >= 0 && board[cell,i] != Player.NONE; cell -= 1);
+
+ if(cell < 0)
+ return false;
+
+ /*if it is AI's first move or the last move was made by human */
+ if (last_moving_player == Player.NONE || last_moving_player == Player.HUMAN)
+ {
+ board[cell,i] = Player.AI;
+ last_moving_player = Player.AI;
+ }
+ else
+ {
+ board[cell,i] = Player.HUMAN;
+ last_moving_player = Player.HUMAN;
+ }
+
+ return true;
+ }
+
+ /* unmove the last move made in the i'th column.*/
+ private void unmove (int i)
+ {
+ int cell;
+
+ for (cell = BOARD_ROWS - 1; cell >= 0 && board[cell,i] != Player.NONE; cell -= 1);
+
+ board[cell + 1,i] = Player.NONE;
+
+ if (last_moving_player == Player.AI)
+ last_moving_player = Player.HUMAN;
+ else if (last_moving_player == Player.HUMAN)
+ last_moving_player = Player.AI;
+
+ }
+
+ /* vstr is the sequence of moves made until now. We update DecisionTree::board to reflect these
sequence of moves.*/
+ public void update_board (string vstr)
+ {
+ next_move_in_column = -1;
+
+ /* AI will make the first move, nothing to add to the board*/
+ if (vstr.length == 2) return;
+
+ Player move;
+
+ if (vstr.length % 2 == 0)
+ move = Player.AI;
+ else
+ move = Player.HUMAN;
+
+ for (int i = 1; i < vstr.length - 1; i++)
+ {
+ int column = int.parse(vstr[i].to_string()) -1;
+
+ int cell;
+
+ for (cell = BOARD_ROWS - 1; cell >= 0 && board[cell,column] != Player.NONE; cell -=
1);
+
+ board[cell, column] = move;
+
+ if (move == Player.HUMAN)
+ move = Player.AI;
+ else
+ move = Player.HUMAN;
+ }
+
+ last_moving_player = Player.HUMAN;
+ }
+
+ /* check for immediate win of AI/HUMAN. It checks the current state of the board. Returns -1 if no
immediate win for Player P.
+ Otherwise returns the column number in which Player P should move to win.*/
+ private int immediate_win (Player p)
+ {
+ Player old_last_moving_player = last_moving_player;
+
+ if (p == Player.AI)
+ last_moving_player = Player.HUMAN;
+ else
+ last_moving_player = Player.AI;
+
+ for (int i = 0; i < BOARD_COLUMNS; i++)
+ {
+ if (move(i))
+ {
+ if (victory(i) != 0)
+ {
+ unmove(i);
+ last_moving_player = old_last_moving_player;
+ return i;
+ }
+
+ unmove(i);
+ }
+ }
+
+ last_moving_player = old_last_moving_player;
+
+ /* returns -1 if no immediate win for Player p*/
+ return -1;
+ }
+
+ /* returns the column number in which the next move has to be made. Returns -1 if the board is full.
*/
+ public int playgame (string vstr)
+ {
+ /* set the Difficulty level */
+ set_level(vstr);
+
+ /* update DecisionTree::board to reflect the moves made until now*/
+ update_board(vstr);
+
+ /* check if AI can win by making a move immediately*/
+ int temp = immediate_win (Player.AI);
+
+ /* if the AI can win, then make that move. main.c has indexing beginning from 1 instead of 0,
hence, we add 1.*/
+ if (temp != -1)
+ return temp + 1;
+
+ /*check if HUMAN can win by making a move immediately*/
+ temp = immediate_win (Player.HUMAN);
+
+ /* if the HUMAN can win, we make AI move in that column so as avoid loss.*/
+ if (temp != -1)
+ return temp + 1;
+
+ /*call negamax tree on the current state of the board.*/
+ negamax(plies, NEG_INF, -1 * NEG_INF);
+
+ /* return the column number in which next move should be made.*/
+ return next_move_in_column + 1;
+
+ }
+
+ /* The evaluation function to be called when we have reached the maximum depth in the DecisionTree*/
+ private int heurist ()
+ {
+ if (level == Difficulty.EASY)
+ return heurist_easy();
+
+ else if (level == Difficulty.MEDIUM)
+ return heurist_medium();
+
+ else
+ return heurist_hard();
+
+ }
+
+ private int heurist_easy ()
+ {
+ return -1 * heurist_hard();
+ }
+
+ private int heurist_medium ()
+ {
+ return Random.int_range(1,49);
+ }
+
+ private int heurist_hard ()
+ {
+ int count = 0;
+
+ count = count_3_in_a_row(Player.AI);
+
+ count -= count_3_in_a_row(Player.HUMAN);
+
+ count = count*100;
+
+ if (count == 0)
+ count = Random.int_range(1,49);
+
+ return count;
+ }
+
+ /* Count the number of threes in a row for Player P. It counts all those 3 which have an empty cell
in the vicinity to make it
+ four in a row*/
+ private int count_3_in_a_row (Player p)
+ {
+ int count = 0;
+
+ Player old_last_moving_player = last_moving_player;
+
+ last_moving_player = p;
+
+ for (int j = 0; j < BOARD_COLUMNS; j++)
+ {
+ for (int i = 0; i < BOARD_ROWS; i++)
+ {
+ if (board[i,j] != Player.NONE)
+ break;
+
+ if (all_adjacent_empty(i,j))
+ continue;
+
+ board[i,j] = p;
+
+ if (victory(j) != 0)
+ count++;
+
+ board[i,j] = Player.NONE;
+
+ }
+ }
+ last_moving_player = old_last_moving_player;
+ return count;
+ }
+
+ /* checks if all adjacent cells to board[i,j] are empty*/
+ private bool all_adjacent_empty (int i, int j)
+ {
+ for (int k = -1 ; k <= 1; k++)
+ {
+ for (int l = -1; l <=1; l++)
+ {
+ if (k == 0 && l == 0)
+ continue;
+ if ((i+k) >= 0 && (i+k) < BOARD_ROWS && (j+l) >= 0 && (j+l) < BOARD_COLUMNS)
+ {
+ if(board[i+k,j+l] != Player.NONE)
+ return false;
+ }
+ }
+ }
+
+ return true;
+ }
+
+ /* set the number of plies and the difficulty level*/
+ private void set_level (string vstr)
+ {
+
+ if (vstr[0] == 'a')
+ {
+ level = Difficulty.EASY;
+ plies = 4;
+ }
+ else if (vstr[0] == 'b')
+ {
+ level = Difficulty.MEDIUM;
+ plies = 8;
+ }
+ else
+ {
+ level = Difficulty.HARD;
+ plies = 8;
+ }
+ }
+
+ /* utility function for testing purposes*/
+ public int playandcheck (string vstr)
+ {
+ set_level(vstr);
+
+ update_board(vstr);
+
+ int temp = immediate_win (Player.AI);
+
+ if (temp != -1)
+ {
+ return 1000;
+ }
+
+ temp = immediate_win (Player.HUMAN);
+
+ if (temp != -1)
+ return temp + 1;
+
+ negamax(plies, NEG_INF, -1 * NEG_INF);
+
+ return next_move_in_column + 1;
+
+ }
+}
+
diff --git a/src/main.c b/src/main.c
index ddc6234..ff171f7 100644
--- a/src/main.c
+++ b/src/main.c
@@ -29,7 +29,7 @@
#include <gtk/gtk.h>
#include <canberra-gtk.h>
-#include "connect4.h"
+#include "ai.h"
#include "main.h"
#include "theme.h"
#include "prefs.h"
@@ -100,6 +100,9 @@ static void process_move2 (gint c);
static void process_move3 (gint c);
+
+
+
static void
clear_board (void)
{
@@ -370,7 +373,6 @@ static void
game_init (void)
{
g_random_set_seed ((guint) time (NULL));
- vboard = veleng_init ();
anim = ANIM_NONE;
gameover = TRUE;
@@ -420,7 +422,7 @@ game_reset (void)
} else {
vstr[0] = vlevel[p.level[PLAYER2]];
}
- game_process_move (playgame (vstr, vboard) - 1);
+ game_process_move (playgame (vstr) - 1);
}
}
@@ -429,7 +431,6 @@ game_reset (void)
static void
game_free (void)
{
- veleng_free (vboard);
gfx_free ();
}
@@ -632,7 +633,7 @@ on_game_hint (GSimpleAction *action, GVariant *parameter, gpointer data)
set_status_message (_("I’m Thinking…"));
vstr[0] = vlevel[LEVEL_STRONG];
- c = playgame (vstr, vboard) - 1;
+ c = playgame (vstr) - 1;
column_moveto = c;
while (timeout)
@@ -1077,7 +1078,7 @@ process_move3 (gint c)
} else {
vstr[0] = vlevel[p.level[PLAYER2]];
}
- c = playgame (vstr, vboard) - 1;
+ c = playgame (vstr) - 1;
if (c < 0)
gameover = TRUE;
g_timeout_add (SPEED_DROP,
@@ -1311,7 +1312,7 @@ main (int argc, char *argv[])
g_error_free (error);
exit (1);
}
-
+
settings = g_settings_new ("org.gnome.four-in-a-row");
g_set_application_name (_(APPNAME_LONG));
diff --git a/src/test-ai.vala b/src/test-ai.vala
new file mode 100644
index 0000000..2b50b89
--- /dev/null
+++ b/src/test-ai.vala
@@ -0,0 +1,219 @@
+/* -*- Mode: vala; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ *
+ * Copyright © 2014 Michael Catanzaro
+ * Copyright © 2014 Nikhar Agrawal
+ *
+ * This file is part of Four-in-a-row.
+ *
+ * Four-in-a-row is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * Four-in-a-row is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Four-in-a-row. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+const int NUMBER_GAMES = 5;
+
+/* Tests if the AI makes moves so as to take up immediate horizontal wins. The argument to playgame function
is the sequence of moves
+ made until now. The return value of playgame function is the column number in which the AI should move.*/
+private 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 (playgame ("a1727370") == 4);
+ assert (playgame ("a7315651311324420") == 6);
+ assert (playgame ("a232225657223561611133440") == 4);
+ assert (playgame ("a242215322574255543341746677453337710") == 1);
+}
+
+/* Tests if the AI makes moves so as to take up immediate vertical wins.*/
+private void test_vertical_win ()
+{
+ assert (playgame ("a1213140") == 1);
+ assert (playgame ("a14456535526613130") == 1);
+ assert (playgame ("a432334277752576710") == 7);
+ assert (playgame ("a547477454544323321712116260") == 2);
+}
+
+/* Tests if the AI makes moves so as to take up immediate forward diagonal wins.*/
+private void test_forward_diagonal_win ()
+{
+ assert (playgame ("a54221164712446211622157570") == 7);
+ assert (playgame ("a4256424426621271412117175776343330") == 3);
+ assert (playgame ("a132565522322662666775443351131113540") == 4);
+ assert (playgame ("a4571311334541225544112245262577767733360") == 6);
+}
+
+/* Tests if the AI makes moves so as to take up immediate backward diagonal wins.*/
+private void test_backward_diagonal_win ()
+{
+ assert (playgame ("5422327343142110") == 1);
+ assert (playgame ("a1415113315143220") == 2);
+ assert (playgame ("a547323452213345110") == 1);
+ assert (playgame ("a4256424426621271412117175776343330") == 3);
+}
+
+/* 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 void test_avoid_vertical_loss ()
+{
+ assert (playgame ("a42563117273430") == 3);
+ assert (playgame ("a3642571541322340") == 4);
+ assert (playgame ("a144566264475171137750") == 5);
+ assert (playgame ("a54747745454432332171210") == 1);
+}
+
+/* Tests if the AI makes moves which prevents HUMAN from taking immediate forward diagonal victories*/
+private void test_avoid_forward_diagonal_loss ()
+{
+ assert (playgame ("a34256477331566570") == 7);
+ assert (playgame ("a1445662644751711370") == 7);
+ assert (playgame ("a43442235372115113340") == 4);
+ assert (playgame ("a4143525567766443543125411170") == 7);
+}
+
+/* Tests if the AI makes moves which prevents HUMAN from taking immediate backward diagonal victories*/
+private void test_avoid_backward_diagonal_loss ()
+{
+ assert (playgame ("a47465234222530") == 3);
+ assert (playgame ("a4344223537211510") == 1);
+ assert (playgame ("a4141311525513520") == 2);
+ assert (playgame ("a1445662644751711377553330") == 3);
+
+}
+
+/* Tests if the AI makes moves which prevents HUMAN from taking immediate horizontal victories*/
+private void test_avoid_horizontal_loss ()
+{
+ assert (playgame ("a445360") == 7);
+ assert (playgame ("a745534131117114777720") == 2);
+ assert (playgame ("a243466431217112323350") == 5);
+ assert (playgame ("a24147356465355111336631615240") == 4);
+}
+
+/* Tests if AI can detect full boards, and thus draw games.*/
+private void test_draw ()
+{
+ assert (playgame ("a1311313113652226667224247766737374455445550") == 0);
+ assert (playgame ("a6121151135432322433425566474425617635677770") == 0);
+ assert (playgame ("a4226111412113275256335534443264375577676670") == 0);
+ assert (playgame ("a4212116575717754775221133434432366655342660") == 0);
+}
+
+/* Tests if AI makes valid moves, i.e., between column 1 and column 7*/
+private void test_random ()
+{
+ int x = playgame ("a443256214350");
+ assert (x >= 1 && x <= 7);
+
+ x = playgame ("a241473564653551113366316150");
+ assert (x >= 1 && x <= 7);
+
+ x = playgame ("a24357315461711177416622623350");
+ assert (x >= 1 && x <= 7);
+
+ x = playgame ("a1445662644751711377553333665775446110");
+ assert (x >= 1 && x <= 7);
+}
+
+/* Pits two AI's of varying difficulty levels against each other and returns the number of games won by
easier AI.*/
+private int test_ai_vs_ai (string easier, string harder)
+{
+ int easier_wins = 0;
+ int draw = 0;
+ int harder_wins = 0;
+
+ for (int i = 0; i < NUMBER_GAMES;i++)
+ {
+ var e = new StringBuilder();
+ e.append(easier);
+
+ var m = new StringBuilder();
+ m.append(harder);
+
+ while (true)
+ {
+ int move;
+ DecisionTree t = new DecisionTree();
+ move = t.playandcheck(e.str);
+ if (move == 0)
+ {
+ draw++;
+ break;
+ }
+
+ if (move == 1000)
+ {
+ easier_wins++;
+ break;
+ }
+
+ e.insert(e.str.length - 1, move.to_string());
+ m.insert(m.str.length - 1, move.to_string());
+
+ DecisionTree d = new DecisionTree();
+ move = d.playandcheck(m.str);
+
+ if (move == 0)
+ {
+ draw++;
+ break;
+ }
+
+ if (move == 1000)
+ {
+ harder_wins++;
+ break;
+ }
+ e.insert(e.str.length - 1, move.to_string());
+ m.insert(m.str.length - 1, move.to_string());
+ }
+ }
+ return easier_wins;
+}
+
+private void test_easy_vs_medium ()
+{
+ int easy_wins = test_ai_vs_ai ("a0","b0");
+
+ assert (easy_wins <= NUMBER_GAMES/2);
+}
+
+private void test_easy_vs_hard ()
+{
+ int easy_wins = test_ai_vs_ai ("a0","c0");
+
+ assert (easy_wins <= NUMBER_GAMES/2);
+}
+
+private void test_medium_vs_hard ()
+{
+ int medium_wins = test_ai_vs_ai ("b0","c0");
+
+ assert (medium_wins <= NUMBER_GAMES/2);
+}
+
+public int main (string[] args)
+{
+ Test.init (ref args);
+ Test.add_func ("/AI/Take Win/Horizontal Win", test_horizontal_win);
+ Test.add_func ("/AI/Take Win/Vertical Win", test_vertical_win);
+ Test.add_func ("/AI/Take Win/Forward Diagonal Win", test_forward_diagonal_win);
+ Test.add_func ("/AI/Take Win/Backward Diagonal Win", test_backward_diagonal_win);
+ Test.add_func ("/AI/Avoid Loss/Horizontal Loss", test_avoid_horizontal_loss);
+ Test.add_func ("/AI/Avoid Loss/Vertical Loss", test_avoid_vertical_loss);
+ Test.add_func ("/AI/Avoid Loss/Forward Diagonal Loss", test_avoid_forward_diagonal_loss);
+ Test.add_func ("/AI/Avoid Loss/Backward Diagonal Loss", test_avoid_backward_diagonal_loss);
+ Test.add_func ("/AI/AI vs AI/Easy vs Medium", test_easy_vs_medium);
+ Test.add_func ("/AI/AI vs AI/Easy vs Hard", test_easy_vs_hard);
+ Test.add_func ("/AI/AI vs AI/Medium vs Hard", test_medium_vs_hard);
+ Test.add_func ("/AI/Draw", test_draw);
+ Test.add_func ("/AI/Random", test_random);
+ return Test.run ();
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
