add alpha–beta pruning; fix bugs: uncorrect random move

3 files changed, 17 insertions, 8 deletions

diff --git a/ai.cpp b/ai.cpp
index dafa57a..b7386cc 100644
--- a/ai.cpp
+++ b/ai.cpp
@@ -26,8 +26,10 @@ void AI::GetBestMove(int &my, int &mx, GameField field)
 
 	// give chance to user :)
 	if(first_move) {
-		my = rand() % rows;
-		mx = rand() % cols;
+		do {
+			my = rand() % rows;
+			mx = rand() % cols;
+		} while( !field.CanMove(my, mx) );
 		first_move = false;
 		return;
 	}
@@ -39,7 +41,7 @@ void AI::GetBestMove(int &my, int &mx, GameField field)
 			if(!field.CanMove(y, x))
 				continue;
 			field.Move(y, x);
-			int result = MinMax(field, 1);
+			int result = MinMax(field, score, MAX_SCORE, 1);
 			field.UndoMove(y, x);
 			if(result > score) {
 				score = result;
@@ -62,13 +64,14 @@ int AI::score(GameField field)
 	return NONE_SCORE;
 }
 
-int AI::MinMax(GameField field, int depth)
+//								MIN_SCORE, MAX_SCORE
+int AI::MinMax(GameField field, int alpha, int beta, int depth)
 {
 	if(field.GetState() != G_NONE || depth >= max_depth) {
 		return score(field);
 	}
 
-	int score = MAX_SCORE;
+	int score = beta;
 	int rows = field.GetRows();
 	int cols = field.GetCols();
 
@@ -79,10 +82,13 @@ int AI::MinMax(GameField field, int depth)
 			if(!field.CanMove(y, x))
 				continue;
 			field.Move(y, x);
-			int result = MinMax(field, depth + 1);
+			int result = MinMax(field, alpha, score, depth + 1);
 			field.UndoMove(y, x);
 			if(result < score)
 				score = result;
+			fprintf(stderr, "alpha (%d) >= beta (%d)?\n", alpha, score);
+			if(alpha >= score)
+				return score;
 		}
 	}
 	return score;
diff --git a/ai.hpp b/ai.hpp
index ec1f56b..3edaa60 100644
--- a/ai.hpp
+++ b/ai.hpp
@@ -11,9 +11,10 @@ public:
 	AI(int p, int d);
 
 	void GetBestMove(int &my, int &mx, GameField field);
+	void FirstMove(bool m) { first_move = m; }
 private:
 	int score(GameField field);
-	int MinMax(GameField field, int depth);
+	int MinMax(GameField field, int alpha, int beta, int depth);
 };
 
 #endif /* LPG_AI_H */
diff --git a/clui.cpp b/clui.cpp
index 5eff6b2..520a758 100644
--- a/clui.cpp
+++ b/clui.cpp
@@ -113,8 +113,10 @@ void startGame()
 		delete game_field;
 	game_field = new GameField(gb_y, gb_x, gb_lwin);
 	drawGame(gb_y, gb_x);
-	if(play_with_ai && gb_symbol == SYMBOL_PLAYERTWO)
+	if(play_with_ai && gb_symbol == SYMBOL_PLAYERTWO) {
+		game_bot->FirstMove(true);
 		aiMove();
+	}
 }
 
 void changePlayer()