From ba3edfbd518c93a2715cf1ada3b6b481b9a52ce9 Mon Sep 17 00:00:00 2001
From: Henry Bush
Date: Mon, 24 Nov 2008 21:22:24 +0000
Subject: T7G: AI in microscope puzzle is "complete" (ie good enough for now)

svn-id: r35164
---
 engines/groovie/cell.cpp | 70 ++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 59 insertions(+), 11 deletions(-)

(limited to 'engines/groovie/cell.cpp')

diff --git a/engines/groovie/cell.cpp b/engines/groovie/cell.cpp
index 0babbce40c..c1ddedff9d 100644
--- a/engines/groovie/cell.cpp
+++ b/engines/groovie/cell.cpp
@@ -29,17 +29,21 @@ namespace Groovie {
 
 CellGame::CellGame(byte *board) :
 	_board(board) {
-
 	_startX = _startY = _endX = _endY = 255;
 }
 
 int8 CellGame::calcMove(byte *origboard, uint8 color, uint8 depth) {
 	uint8 i, j;
 	int8 di, dj;
+	uint8 bestStartX, bestStartY, bestEndX, bestEndY;
+	int8 bestDiff = -100;
+	int8 origBoardCount = countBoard(origboard, color);
+	int8 currDiff = -100;
 	byte *newboard;
 	uint8 boardmemsize = sizeof(byte) * BOARDSIZE * BOARDSIZE;
-	int8 maxdiff = -100;
+	uint8 oppColor = 3 - color;
 
+	bestStartX = bestStartY = bestEndX = bestEndY = 255;
 	newboard = (byte*) malloc(boardmemsize);
 	memcpy(newboard, origboard, boardmemsize);
 
@@ -47,17 +51,32 @@ int8 CellGame::calcMove(byte *origboard, uint8 color, uint8 depth) {
 		return 0;
 	}
 	
-	for (i = 0; BOARDSIZE > i; i++) {
-		for (j = 0; BOARDSIZE > j; j++) {					// For every square on the board
+	for (i = 0; BOARDSIZE > i; i++) {						// For every square on the board
+		for (j = 0; BOARDSIZE > j; j++) {					//
 			if (color == *(origboard + i + (BOARDSIZE * j))) {		// If the square is the desired colour
-				for (di = -2; 2 >= di; di++) {
-					for (dj = -2; 2 >= dj; dj++) {
+				for (di = -2; 2 >= di; di++) {				// Check every square two or less in every direction
+					for (dj = -2; 2 >= dj; dj++) {			//
 						if (di != 0 || dj != 0) {		// Don't allow a move onto itself
+							debugC(7, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Testing move %d, %d-> %d, %d", depth, i, j, i+di, j+dj);
 							if (validMove(origboard, color, i+di, j+dj)) {
-								_startX = i;
-								_startY = j;
-								_endX = i+di;
-								_endY = j+dj;
+								int8 nextlevel;
+								debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Valid move %d, %d-> %d, %d", depth, i, j, i+di, j+dj);
+								execMove (newboard, color, i, j, i+di, j+dj);
+								
+								nextlevel = calcMove (newboard, oppColor, depth - 1);
+								debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Next level down returned %d", depth, nextlevel);
+								currDiff = countBoard(newboard, color) - origBoardCount - nextlevel;
+								if (currDiff > bestDiff) {
+									debugC(4, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Found new best move (diff of %d): %d, %d-> %d, %d", depth, currDiff, i, j, i+di, j+dj);
+									bestDiff = currDiff;
+									bestStartX = i;
+									bestStartY = j;
+									bestEndX = i+di;
+									bestEndY = j+dj;
+
+								}
+								// TODO: ideal would be to revert the move, rather than copy the board again. I think.
+								memcpy(newboard, origboard, boardmemsize);
 							}
 						}
 					}
@@ -66,8 +85,37 @@ int8 CellGame::calcMove(byte *origboard, uint8 color, uint8 depth) {
 		}
 	}
 	
+	_startX = bestStartX;
+	_startY = bestStartY;
+	_endX = bestEndX;
+	_endY = bestEndY;
+
+	debugC(2, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Best move is (diff of %d): %d, %d-> %d, %d", depth, bestDiff, _startX, _startY, _endX, _endY);
 	free(newboard);
-	return maxdiff;
+	debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Freed newboard");
+	return bestDiff;
+}
+
+void CellGame::execMove(byte *board, uint8 color, int8 startX, int8 startY, int8 endX, int8 endY) {
+	int8 i, j;
+	uint8 colorToEat = 3 - color;		// The opposite of the colour passed: 2 -> 1, 1 -> 2
+
+	if (abs(endX - startX) == 2 || abs(endY - startY) == 2) {
+		*(board + startX + BOARDSIZE * startY) = 0;
+	}
+
+	*(board + endX + BOARDSIZE * endY) = color;
+
+	for (i = (endX - 1); endX + 1 >= i; i++) {
+		for (j = (endY - 1); endY + 1 >= j; j++) {
+			if (BOARDSIZE > i && BOARDSIZE > j && 0 <= i && 0 <= j) {		// Don't wrap around the board edges!
+				uint8 offset = i + BOARDSIZE * j;
+				if (colorToEat == *(board + offset)) {
+					*(board + offset) = color;
+				}
+			}
+		}
+	}
 }
 
 bool CellGame::validMove(byte *board, uint8 color, int8 endX, int8 endY) {
-- 
cgit v1.2.3