Proper implementation of microscope puzzle.

svn-id: r42634

4 files changed, 773 insertions, 132 deletions

diff --git a/engines/groovie/cell.cpp b/engines/groovie/cell.cpp
index 3bc8650aa6..e6d8d48759 100644
--- a/engines/groovie/cell.cpp
+++ b/engines/groovie/cell.cpp
@@ -27,156 +27,772 @@
 
 namespace Groovie {
 
-CellGame::CellGame(byte *board) :
-	_board(board) {
+CellGame::CellGame() {
 	_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;
-	uint8 oppColor = 3 - color;
+	_stack_index = _boardStackPtr = 0;
+	_flag4 = false;
+	_flag2 = false;
+	_coeff3 = 0;
 
-	bestStartX = bestStartY = bestEndX = bestEndY = 255;
-	newboard = (byte*) malloc(boardmemsize);
-	memcpy(newboard, origboard, boardmemsize);
+	_moveCount = 0;
+}
 
-	if (0 == depth) {
+byte CellGame::getStartX() {
+	if (_startX > BOARDSIZE) {
+		warning ("CellGame::getStartX: not calculated yet (%d)!", _startX);
 		return 0;
+	} else {
+		return _startX;
+	}
+}
+
+byte CellGame::getStartY() {
+	if (_startY > BOARDSIZE) {
+		warning ("CellGame::getStartY: not calculated yet (%d)!", _startY);
+		return 6;
+	} else {
+		return _startY;
+	}
+}
+
+byte CellGame::getEndX() {
+	if (_endX > BOARDSIZE) {
+		warning ("CellGame::getEndX: not calculated yet (%d)!", _endX);
+		return 1;
+	} else {
+		return _endX;
+	}
+}
+
+byte CellGame::getEndY() {
+	if (_endY > BOARDSIZE) {
+		warning ("CellGame::getEndY: not calculated yet (%d)!", _endY);
+		return 6;
+	} else {
+		return _endY;
+	}
+}
+
+CellGame::~CellGame() {
+}
+
+const int8 possibleMoves[][9] = {
+	{ 1, 7, 8, -1 },
+	{ 0, 2, 7, 8, 9, -1 },
+	{ 1, 3, 8, 9, 10, -1 },
+	{ 2, 4, 9, 10, 11, -1 },
+	{ 3, 5, 10, 11, 12, -1 },
+	{ 4, 6, 11, 12, 13, -1 }, // 5
+	{ 5, 12, 13, -1 },
+	{ 0, 1, 8, 14, 15, -1 },
+	{ 0, 1, 2, 7, 9, 14, 15, 16, -1 },
+	{ 1, 2, 3, 8, 10, 15, 16, 17, -1 },
+	{ 2, 3, 4, 9, 11, 16, 17, 18, -1 }, // 10
+	{ 3, 4, 5, 10, 12, 17, 18, 19, -1 },
+	{ 4, 5, 6, 11, 13, 18, 19, 20, -1 },
+	{ 5, 6, 12, 19, 20, -1 },
+	{ 7, 8, 15, 21, 22, -1 },
+	{ 7, 8, 9, 14, 16, 21, 22, 23, -1 }, // 15
+	{ 8, 9, 10, 15, 17, 22, 23, 24, -1 },
+	{ 9, 10, 11, 16, 18, 23, 24, 25, -1 },
+	{ 10, 11, 12, 17, 19, 24, 25, 26, -1 },
+	{ 11, 12, 13, 18, 20, 25, 26, 27, -1 },
+	{ 12, 13, 19, 26, 27, -1 }, // 20
+	{ 14, 15, 22, 28, 29, -1 },
+	{ 14, 15, 16, 21, 23, 28, 29, 30, -1 },
+	{ 15, 16, 17, 22, 24, 29, 30, 31, -1 },
+	{ 16, 17, 18, 23, 25, 30, 31, 32, -1 },
+	{ 17, 18, 19, 24, 26, 31, 32, 33, -1 }, // 25
+	{ 18, 19, 20, 25, 27, 32, 33, 34, -1 },
+	{ 19, 20, 26, 33, 34, -1 },
+	{ 21, 22, 29, 35, 36, -1 },
+	{ 21, 22, 23, 28, 30, 35, 36, 37, -1 },
+	{ 22, 23, 24, 29, 31, 36, 37, 38, -1 }, // 30
+	{ 23, 24, 25, 30, 32, 37, 38, 39, -1 },
+	{ 24, 25, 26, 31, 33, 38, 39, 40, -1 },
+	{ 25, 26, 27, 32, 34, 39, 40, 41, -1 },
+	{ 26, 27, 33, 40, 41, -1 },
+	{ 28, 29, 36, 42, 43, -1 }, // 35
+	{ 28, 29, 30, 35, 37, 42, 43, 44, -1 },
+	{ 29, 30, 31, 36, 38, 43, 44, 45, -1 },
+	{ 30, 31, 32, 37, 39, 44, 45, 46, -1 },
+	{ 31, 32, 33, 38, 40, 45, 46, 47, -1 },
+	{ 32, 33, 34, 39, 41, 46, 47, 48, -1 }, // 40
+	{ 33, 34, 40, 47, 48, -1 },
+	{ 35, 36, 43, -1 },
+	{ 35, 36, 37, 42, 44, -1 },
+	{ 36, 37, 38, 43, 45, -1 },
+	{ 37, 38, 39, 44, 46, -1 }, // 45
+	{ 38, 39, 40, 45, 47, -1 },
+	{ 39, 40, 41, 46, 48, -1 },
+	{ 40, 41, 47, -1 }
+};
+
+
+const int8 strategy2[][17] = {
+	{ 2, 9, 14, 15, 16, -1 },
+	{ 3, 10, 14, 15, 16, 17, -1 },
+	{ 0, 4, 7, 11, 14, 15, 16, 17, 18, -1 },
+	{ 1, 5, 8, 12, 15, 16, 17, 18, 19, -1 },
+	{ 2, 6, 9, 13, 16, 17, 18, 19, 20, -1 },
+	{ 3, 10, 17, 18, 19, 20, -1 }, // 5
+	{ 4, 11, 18, 19, 20, -1 },
+	{ 2, 9, 16, 21, 22, 23, -1 },
+	{ 3, 10, 17, 21, 22, 23, 24, -1 },
+	{ 0, 4, 7, 11, 14, 18, 21, 22, 23, 24, 25, -1 },
+	{ 1, 5, 8, 12, 15, 19, 22, 23, 24, 25, 26, -1 }, // 10
+	{ 2, 6, 9, 13, 16, 20, 23, 24, 25, 26, 27, -1 },
+	{ 3, 10, 17, 24, 25, 26, 27, -1 },
+	{ 4, 11, 18, 25, 26, 27, -1 },
+	{ 0, 1, 2, 9, 16, 23, 28, 29, 30, -1 },
+	{ 0, 1, 2, 3, 10, 17, 24, 28, 29, 30, 31, -1 }, // 15
+	{ 0, 1, 2, 3, 4, 7, 11, 14, 18, 21, 25, 28, 29, 30, 31, 32, -1 },
+	{ 1, 2, 3, 4, 5, 8, 12, 15, 19, 22, 26, 29, 30, 31, 32, 33, -1 },
+	{ 2, 3, 4, 5, 6, 9, 13, 16, 20, 23, 27, 30, 31, 32, 33, 34, -1 },
+	{ 3, 4, 5, 6, 10, 17, 24, 31, 32, 33, 34, -1 },
+	{ 4, 5, 6, 11, 18, 25, 32, 33, 34, -1 }, // 20
+	{ 7, 8, 9, 16, 23, 30, 35, 36, 37, -1 },
+	{ 7, 8, 9, 10, 17, 24, 31, 35, 36, 37, 38, -1 },
+	{ 7, 8, 9, 10, 11, 14, 18, 21, 25, 28, 32, 35, 36, 37, 38, 39, -1 },
+	{ 8, 9, 10, 11, 12, 15, 19, 22, 26, 29, 33, 36, 37, 38, 39, 40, -1 },
+	{ 9, 10, 11, 12, 13, 16, 20, 23, 27, 30, 34, 37, 38, 39, 40, 41, -1 }, // 25
+	{ 10, 11, 12, 13, 17, 24, 31, 38, 39, 40, 41, -1 },
+	{ 11, 12, 13, 18, 25, 32, 39, 40, 41, -1 },
+	{ 14, 15, 16, 23, 30, 37, 42, 43, 44, -1 },
+	{ 14, 15, 16, 17, 24, 31, 38, 42, 43, 44, 45, -1 },
+	{ 14, 15, 16, 17, 18, 21, 25, 28, 32, 35, 39, 42, 43, 44, 45, 46, -1 }, // 30
+	{ 15, 16, 17, 18, 19, 22, 26, 29, 33, 36, 40, 43, 44, 45, 46, 47, -1 },
+	{ 16, 17, 18, 19, 20, 23, 27, 30, 34, 37, 41, 44, 45, 46, 47, 48, -1 },
+	{ 17, 18, 19, 20, 24, 31, 38, 45, 46, 47, 48, -1 },
+	{ 18, 19, 20, 25, 32, 39, 46, 47, 48, -1 },
+	{ 21, 22, 23, 30, 37, 44, -1 }, // 35
+	{ 21, 22, 23, 24, 31, 38, 45, -1 },
+	{ 21, 22, 23, 24, 25, 28, 32, 35, 39, 42, 46, -1 },
+	{ 22, 23, 24, 25, 26, 29, 33, 36, 40, 43, 47, -1 },
+	{ 23, 24, 25, 26, 27, 30, 34, 37, 41, 44, 48, -1 },
+	{ 24, 25, 26, 27, 31, 38, 45, -1 }, // 40
+	{ 25, 26, 27, 32, 39, 46, -1 },
+	{ 28, 29, 30, 37, 44, -1 },
+	{ 28, 29, 30, 31, 38, 45, -1 },
+	{ 28, 29, 30, 31, 32, 35, 39, 42, 46, -1 },
+	{ 29, 30, 31, 32, 33, 36, 40, 43, 47, -1 }, // 45
+	{ 30, 31, 32, 33, 34, 37, 41, 44, 48, -1 },
+	{ 31, 32, 33, 34, 38, 45, -1 },
+	{ 32, 33, 34, 39, 46, -1 }
+};
+
+void CellGame::copyToTempBoard() {
+	for (int i = 0; i < 53; ++i) {
+		_tempBoard[i] = _board[i];
+	}
+}
+
+void CellGame::copyFromTempBoard() {
+	for (int i = 0; i < 53; ++i) {
+		_board[i] = _tempBoard[i];
 	}
+}
+
+void CellGame::copyToShadowBoard() {
+	_board[53] = 0;
+	_board[55] = 1;
+	_board[56] = 0;
+
+	for (int i = 0; i < 49; ++i) {
+		_shadowBoard[i] = _board[i];
+	}
+}
+
+void CellGame::pushBoard() {
+	assert(_boardStackPtr < 57 * 9);
 
-	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++) {				// 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)) {
-								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);
-							}
-						}
+	for (int i = 0; i < 57; ++i)
+		_boardStack[_boardStackPtr + i] = _board[i];
+	_boardStackPtr += 57;
+}
+
+void CellGame::popBoard() {
+	assert(_boardStackPtr > 0);
+
+	_boardStackPtr -= 57;
+	for (int i = 0; i < 57; ++i) {
+		_board[i] = _boardStack[_boardStackPtr + i];
+	}
+}
+
+void CellGame::pushShadowBoard() {
+	assert(_boardStackPtr < 57 * 9);
+
+	for (int i = 0; i < 57; ++i)
+		_boardStack[_boardStackPtr + i] = _shadowBoard[i];
+
+	_boardStackPtr += 57;
+}
+
+void CellGame::popShadowBoard() {
+	assert(_boardStackPtr > 0);
+
+	_boardStackPtr -= 57;
+
+	for (int i = 0; i < 57; ++i) {
+		_shadowBoard[i] = _boardStack[_boardStackPtr + i];
+	}
+}
+
+void CellGame::clearMoves() {
+	_stack_startXY[0] = _board[53];
+	_stack_endXY[0] = _board[54];
+	_stack_pass[0] = _board[55];
+
+	_stack_index = 1;
+}
+
+void CellGame::pushMove() {
+	_stack_startXY[_stack_index] = _board[53];
+	_stack_endXY[_stack_index] = _board[54];
+	_stack_pass[_stack_index] = _board[55];
+
+	_stack_index++;
+}
+
+void CellGame::resetMove() {
+	_board[53] = 0;
+	_board[54] = 0;
+	_board[55] = 0;
+}
+
+void CellGame::takeCells(uint16 whereTo, int8 color) {
+	int cellN;
+	const int8 *str;	
+
+	str = possibleMoves[whereTo];
+	while (1) {
+		cellN = *str++;
+		if (cellN < 0)
+			break;
+		if (_tempBoard[cellN] > 0) {
+			--_tempBoard[_tempBoard[cellN] + 48];
+			_tempBoard[cellN] = color;
+			++_tempBoard[color + 48];
+		}
+	}
+}
+
+void CellGame::countAllCells() {
+	_board[49] = 0;
+	_board[50] = 0;
+	_board[51] = 0;
+	_board[52] = 0;
+
+	for (int i = 0; i < 49; i++) {
+		switch (_board[i]) {
+		case 1:	// CELL_BLUE
+			_board[49]++;
+			break;
+		case 2:	// CELL_GREEN
+			_board[50]++;
+			break;
+		case 3:
+			_board[51]++;
+			break;
+		case 4:
+			_board[52]++;
+			break;
+		}
+	}
+}
+
+int CellGame::countCellsOnTempBoard(int8 color) {
+	const int8 *str;	
+	int res = 0;
+	int i;
+
+	for (i = 0; i < 49; i++)
+		_boardSum[i] = 0;
+
+	for (i = 0; i < 49; i++) {
+		if (_tempBoard[i] == color) {
+			for (str = possibleMoves[i]; *str > 0; str++) {
+				if (!_tempBoard[*str])
+					++_boardSum[*str];
+			}
+		}
+	}
+
+	for (i = 0; i < 49; i++)
+		res += _boardSum[i];
+
+	return res;
+}
+
+bool CellGame::canMoveFunc1(int8 color) {
+	const int8 *str;
+
+	if (_board[55] == 1) {
+		for (; _board[53] < 49; _board[53]++) {
+			if (_shadowBoard[_board[53]] == color) {
+				str = &possibleMoves[_board[53]][_board[56]];
+				for (;_board[56] < 8; _board[56]++) {
+					_board[54] = *str++;
+					if (_board[54] < 0)
+						break;
+					if (!_shadowBoard[_board[54]]) {
+						_shadowBoard[_board[54]] = -1;
+						++_board[56];
+						return true;
 					}
 				}
+				_board[56] = 0;
+			}
+		}
+		_board[53] = 0;
+		_board[55] = 2;
+		_board[56] = 0;
+	}
+	if (_board[55] == 2) {
+		for (; _board[53] < 49; _board[53]++) {
+			if (_shadowBoard[_board[53]] == color) {
+				str = &strategy2[_board[53]][_board[56]];
+				for (;_board[56] < 16; _board[56]++) {
+					_board[54] = *str++;
+					if (_board[54] < 0)
+						break;
+					if (!_board[_board[54]]) {
+						++_board[56];
+						return true;
+					}
+				}
+				_board[56] = 0;
 			}
 		}
 	}
 
-	_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);
-	debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Freed newboard");
-	return bestDiff;
+	return false;
 }
 
-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
+bool CellGame::canMoveFunc3(int8 color) {
+	const int8 *str;
+
+	if (_board[55] == 1) {
+		for (; _board[53] < 49; _board[53]++) {
+			if (_shadowBoard[_board[53]] == color) {
+				str = &possibleMoves[_board[53]][_board[56]];
+				for (;_board[56] < 8; _board[56]++) {
+					_board[54] = *str++;
+					if (_board[54] < 0)
+						break;
+					if (!_shadowBoard[_board[54]]) {
+						_shadowBoard[_board[54]] = -1;
+						++_board[56];
+						return true;
+					}
+				}
+				_board[56] = 0;
+			}
+		}
 
-	if (abs(endX - startX) == 2 || abs(endY - startY) == 2) {
-		*(board + startX + BOARDSIZE * startY) = 0;
+		_board[53] = 0;
+		_board[55] = 2;
+		_board[56] = 0;
+		for (int i = 0; i < 49; ++i)
+			_shadowBoard[i] = _board[i];
+	}
+	if (_board[55] == 2) {
+		for (; _board[53] < 49; _board[53]++) {
+			if (_shadowBoard[_board[53]] == color) {
+				str = &strategy2[_board[53]][_board[56]];
+				for (;_board[56] < 16; _board[56]++) {
+					_board[54] = *str++;
+					if (_board[54] < 0)
+						break;
+					if (!_shadowBoard[_board[54]]) {
+						_shadowBoard[_board[54]] = -1;
+						++_board[56];
+						return true;
+					}
+				}
+				_board[56] = 0;
+			}
+		}
 	}
 
-	*(board + endX + BOARDSIZE * endY) = color;
+	return false;
+}
+
+bool CellGame::canMoveFunc2(int8 color) {
+	const int8 *str;
 
-	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;
+	while (1) {
+		while (_board[_board[54]]) {
+			++_board[54];
+			if (_board[54] >= 49)
+				return false;
+		}
+		if (!_board[55]) {
+			str = possibleMoves[_board[54]];
+			while (1) {
+				_board[53] = *str++;
+				if (_board[53] < 0)
+					break;
+				if (_board[_board[53]] == color) {
+					_board[55] = 1;
+					return true;
+				}
+			}
+			_board[55] = 1;
+		}
+		if (_board[55] == 1) {
+			_board[55] = 2;
+			_board[56] = 0;
+		}
+		if (_board[55] == 2) {
+			str = &strategy2[_board[54]][_board[56]];
+			for (; _board[56] < 16; _board[56]++) {
+				_board[53] = *str++;
+				if (_board[53] < 0)
+					break;
+				if (_board[_board[53]] == color) {
+					++_board[56];
+					return true;
 				}
 			}
+			++_board[54];
+			_board[55] = 0;
+			if (_board[54] >= 49)
+				break;
 		}
 	}
+	return false;
 }
 
-bool CellGame::validMove(byte *board, uint8 color, int8 endX, int8 endY) {
-	if (0 > endX || 0 > endY || BOARDSIZE <= endX || BOARDSIZE <= endY) {		// Move is out of bounds
-		return false;
+void CellGame::makeMove(int8 color) {
+	copyToTempBoard();
+	_tempBoard[_board[54]] = color;
+	++_tempBoard[color + 48];
+	if (_board[55] == 2) {
+		_tempBoard[_board[53]] = 0;
+		--_tempBoard[color + 48];
 	}
-	if (0 == *(board + endX + (BOARDSIZE * endY))) {
-		return true;
+	takeCells(_board[54], color);
+}
+
+int CellGame::getBoardWeight(int8 color1, int8 color2) {
+	int8 celln;
+	const int8 *str;
+	byte cellCnt[8];
+
+	str = possibleMoves[_board[54]];
+	cellCnt[1] = _board[49];
+	cellCnt[2] = _board[50];
+	cellCnt[3] = _board[51];
+	cellCnt[4] = _board[52];
+	if (_board[55] != 2)
+		++cellCnt[color2];
+	celln = *str++;
+
+	celln = _board[celln];
+	if (celln > 0) {
+		--cellCnt[celln];
+		++cellCnt[color2];
 	}
-	return false;
+	celln = *str++;
+
+	celln = _board[celln];
+	if (celln > 0) {
+		--cellCnt[celln];
+		++cellCnt[color2];
+	}
+	celln = *str++;
+
+	celln = _board[celln];
+	if (celln > 0) {
+		--cellCnt[celln];
+		++cellCnt[color2];
+	}
+	while (1) {
+		celln = *str++;
+		if (celln < 0)
+			break;
+		celln = _board[celln];
+		if (celln > 0) {
+			--cellCnt[celln];
+			++cellCnt[color2];
+		}
+	}
+	return _coeff3 + 2 * (2 * cellCnt[color1] - cellCnt[1] - cellCnt[2] - cellCnt[3] - cellCnt[4]);
 }
 
-uint8 CellGame::countBoard(byte *board, uint8 color) {
-	uint8 total = 0;
-	for (uint8 i = 0; BOARDSIZE > i; i++) {
-		for (uint8 j = 0; BOARDSIZE > j; j++) {
-			if (color == *(board + i + (BOARDSIZE * j))) {
-				total++;
+void CellGame::chooseBestMove(int8 color) {
+	int moveIndex = 0;
+	int curWeight;
+	int bestWeight;
+
+	if (_flag2) {
+		bestWeight = 32767;
+		for (int i = 0; i < _stack_index; ++i) {
+			_board[53] = _stack_startXY[i];
+			_board[54] = _stack_endXY[i];
+			_board[55] = _stack_pass[i];
+			makeMove(color);
+			curWeight = countCellsOnTempBoard(color);
+			if (curWeight <= bestWeight) {
+				if (curWeight < bestWeight)
+					moveIndex = 0;
+				bestWeight = curWeight;
+				_stack_startXY[moveIndex] = _board[53];
+				_stack_endXY[moveIndex] = _board[54];
+				_stack_pass[moveIndex++] = _board[55];
 			}
 		}
+		_stack_index = moveIndex;
 	}
-	return total;
+
+	_startX = _stack_startXY[0] % 7;
+	_startY = _stack_startXY[0] / 7;
+	_endX = _stack_endXY[0] % 7;
+	_endY = _stack_endXY[0] / 7;
 }
 
-byte CellGame::getStartX() {
-	if (_startX > BOARDSIZE) {
-		warning ("CellGame::getStartX: not calculated yet!");
-		return 0;
+int8 CellGame::calcBestWeight(int8 color1, int8 color2, uint16 depth, int bestWeight) {
+	int8 res;
+	int8 curColor;
+	bool canMove;
+	int type;
+	uint16 i;
+	int8 currBoardWeight;
+	int8 weight;
+
+	pushBoard();
+	copyFromTempBoard();
+	curColor = color2;
+	for (i = 0;; ++i) {
+		if (i >= 4) {
+			res = _coeff3 + 2 * (2 * _board[color1 + 48] - _board[49] - _board[50] - _board[51] - _board[52]);
+			popBoard();
+			return res;
+		}
+		++curColor;
+		if (curColor > 4)
+			curColor = 1;
+
+		if (_board[curColor + 48]) {
+			if (_board[curColor + 48] >= 49 - _board[49] - _board[50] - _board[51] - _board[52]) {
+				resetMove();
+				canMove = canMoveFunc2(curColor);
+				type = 1;
+			} else {
+				copyToShadowBoard();
+				if (depth == 1) {
+					canMove = canMoveFunc3(curColor);
+					type = 3;
+				} else {
+					canMove = canMoveFunc1(curColor);
+					type = 2;
+				}
+			}
+			if (canMove)
+				break;
+		}
+	}
+	if (_flag1) {
+		popBoard();
+		return bestWeight + 1;
+	}
+
+	depth -= 1;
+	if (depth) {
+		makeMove(curColor);
+		if (type == 1) {
+			res = calcBestWeight(color1, curColor, depth, bestWeight);
+		} else {
+			pushShadowBoard();
+			res = calcBestWeight(color1, curColor, depth, bestWeight);
+			popShadowBoard();
+		}
 	} else {
-		return _startX;
+		res = getBoardWeight(color1, curColor);
+	}
+	if (res < bestWeight && color1 != curColor || _flag4) {
+		popBoard();
+		return res;
+	}
+
+	currBoardWeight = _coeff3 + 2 * (2 * _board[color1 + 48] - _board[49] - _board[50] - _board[51] - _board[52]);
+	while (1) {
+		if (type == 1) {
+			canMove = canMoveFunc2(curColor);
+		} else if (type == 2) {
+			canMove = canMoveFunc1(curColor);
+		} else {
+			canMove = canMoveFunc3(curColor);
+		}
+		
+		if (!canMove)
+			break;
+		if (_flag1) {
+			popBoard();
+			return bestWeight + 1;
+		}
+		if (_board[55] == 2) {
+			if (getBoardWeight(color1, curColor) == currBoardWeight)
+				continue;
+		}
+		if (!depth) {
+			weight = getBoardWeight(color1, curColor);
+			if (type == 1) {
+				if (_board[55] == 2)
+					_board[56] = 16;
+			}
+		} else {
+			makeMove(curColor);
+			if (type != 1) {
+				pushShadowBoard();
+				weight = calcBestWeight(color1, curColor, depth, bestWeight);
+				popShadowBoard();
+			} else {
+				weight = calcBestWeight(color1, curColor, depth, bestWeight);
+			}
+		}
+		if ((weight < res && color1 != curColor) || (weight > res && color1 == curColor))
+			res = weight;
+
+		if ((res < bestWeight && color1 != curColor) || _flag4)
+			break;
 	}
+	popBoard();
+
+	return res;
 }
 
-byte CellGame::getStartY() {
-	if (_startY > BOARDSIZE) {
-		warning ("CellGame::getStartY: not calculated yet!");
-		return 6;
+int16 CellGame::doGame(int8 color, int depth) {
+	bool canMove;
+	int type;
+	int8 currBoardWeight;
+	int8 w1;
+	int8 w2;
+
+	countAllCells();
+	if (_board[color + 48] >= 49 - _board[49] - _board[50] - _board[51] - _board[52]) {
+		resetMove();
+		canMove = canMoveFunc2(color);
+		type = true;
 	} else {
-		return _startY;
+		copyToShadowBoard();
+		canMove = canMoveFunc1(color);
+		type = false;
 	}
-}
 
-byte CellGame::getEndX() {
-	if (_endX > BOARDSIZE) {
-		warning ("CellGame::getEndX: not calculated yet!");
+	if (canMove) {
+		if (_board[color + 48] - _board[49] - _board[50] - _board[51] - _board[52] == 0)
+			depth = 0;
+		_coeff3 = 0;
+		if (_board[55] == 1)
+			_coeff3 = 1;
+		clearMoves();
+		if (depth) {
+			makeMove(color);
+			_flag4 = false;
+			if (type) {
+				w2 = calcBestWeight(color, color, depth, -127);
+			} else {
+				pushShadowBoard();
+				w2 = calcBestWeight(color, color, depth, -127);
+				popShadowBoard();
+			}
+		} else {
+			w2 = getBoardWeight(color, color);
+		}
+		currBoardWeight = 2 * (2 * _board[color + 48] - _board[49] - _board[50] - _board[51] - _board[52]);
+		while (1) {
+			if (type)
+				canMove = canMoveFunc2(color);
+			else
+				canMove = canMoveFunc1(color);
+
+			if (!canMove)
+				break;
+			if (_flag1)
+				break;
+			_coeff3 = 0;
+			if (_board[55] == 2) {
+				if (getBoardWeight(color, color) == currBoardWeight)
+					continue;
+			}
+			if (_board[55] == 1)
+				_coeff3 = 1;
+			if (depth) {
+				makeMove(color);
+				_flag4 = false;
+				if (type) {
+					w1 = calcBestWeight(color, color, depth, w2);
+				} else {
+					pushShadowBoard();
+					w1 = calcBestWeight(color, color, depth, w2);
+					popShadowBoard();
+				}
+			} else {
+				w1 = getBoardWeight(color, color);
+			}
+			if (w1 == w2)
+				pushMove();
+
+			if (w1 > w2) {
+				clearMoves();
+				w2 = w1;
+			}
+		}
+		chooseBestMove(color);
 		return 1;
-	} else {
-		return _endX;
 	}
+
+	return 0;
 }
 
-byte CellGame::getEndY() {
-	if (_endY > BOARDSIZE) {
-		warning ("CellGame::getEndY: not calculated yet!");
-		return 6;
+const int8 depths[] = { 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 3, 3 };
+
+int16 CellGame::calcMove(int8 color, uint16 depth) {
+	int result;
+
+	_flag1 = false;
+	++_moveCount;
+	if (depth) {
+		if (depth == 1) {
+			_flag2 = true;
+			result = doGame(color, 0);
+		} else {
+			int newDepth;
+
+			newDepth = depths[3 * (depth - 2) + _moveCount % 3];
+			_flag2 = true;
+			if (newDepth >= 20) {
+				assert(0); // This branch is not implemented
+			} else {
+				result = doGame(color, newDepth);
+			}
+		}
 	} else {
-		return _endY;
+		_flag2 = false;
+		result = doGame(color, depth);
 	}
+	return result;
 }
 
-CellGame::~CellGame() {
+int CellGame::playStauf(byte color, uint16 depth, byte *scriptBoard) {
+	int i;
+
+	for (i = 0; i < 49; i++, scriptBoard++) {
+		_board[i] = 0;
+		if (*scriptBoard == 50)
+			_board[i] = 1;
+		if (*scriptBoard == 66)
+			_board[i] = 2;
+	}
+	for (i = 49; i < 57; i++)
+		_board[i] = 0;
+
+	return calcMove(color, depth);
 }
 
+
 } // End of Groovie namespace
diff --git a/engines/groovie/cell.h b/engines/groovie/cell.h
index 70e135b62d..39ee529beb 100644
--- a/engines/groovie/cell.h
+++ b/engines/groovie/cell.h
@@ -29,6 +29,7 @@
 #include "common/file.h"
 #include "common/util.h"
 
+#include "groovie/cell.h"
 #include "groovie/groovie.h"
 
 #define BOARDSIZE 7
@@ -43,24 +44,59 @@ class Script;
 
 class CellGame {
 public:
-	CellGame(byte *board);
+	CellGame();
 	~CellGame();
-	int8 calcMove(byte *origboard, uint8 color, uint8 depth);
 	byte getStartX();
 	byte getStartY();
 	byte getEndX();
 	byte getEndY();
+	int playStauf(byte color, uint16 depth, byte *scriptBoard);
 
 private:
-	bool validMove(byte *board, uint8 color, int8 endX, int8 endY);
-	void execMove(byte *board, uint8 color, int8 startX, int8 startY, int8 endX, int8 endY);
-	uint8 countBoard(byte* board, uint8 color);
-	byte *_board;
+	void copyToTempBoard();
+	void copyFromTempBoard();
+	void copyToShadowBoard();
+	void pushBoard();
+	void popBoard();
+	void pushShadowBoard();
+	void popShadowBoard();
+	void clearMoves();
+	void pushMove();
+	void resetMove();
+	bool canMoveFunc1(int8 color);
+	bool canMoveFunc2(int8 color);
+	bool canMoveFunc3(int8 color);
+	void takeCells(uint16 whereTo, int8 color);
+	void countAllCells();
+	int countCellsOnTempBoard(int8 color);
+	void makeMove(int8 color);
+	int getBoardWeight(int8 color1, int8 color2);
+	void chooseBestMove(int8 color);
+	int8 calcBestWeight(int8 color1, int8 color2, uint16 depth, int bestWeight);
+	int16 doGame(int8 color, int depth);
+	int16 calcMove(int8 color, uint16 depth);
 
 	byte _startX;
 	byte _startY;
 	byte _endX;
 	byte _endY;
+
+	int8 _board[57];
+	int8 _tempBoard[58];
+	int8 _shadowBoard[64];
+	int8 _boardStack[570];
+	int _boardStackPtr;
+
+	int8 _boardSum[58];
+
+	int8 _stack_startXY[128];
+	int8 _stack_endXY[128];
+	int8 _stack_pass[128];
+	int _stack_index;
+
+	int _coeff3;
+	bool _flag1, _flag2, _flag4;
+	int _moveCount;
 };
 
 } // End of Groovie namespace
diff --git a/engines/groovie/script.cpp b/engines/groovie/script.cpp
index eb53842b91..6c4f38c270 100644
--- a/engines/groovie/script.cpp
+++ b/engines/groovie/script.cpp
@@ -61,7 +61,7 @@ static void debugScript(int level, bool nl, const char *s, ...) {
 Script::Script(GroovieEngine *vm, EngineVersion version) :
 	_code(NULL), _savedCode(NULL), _stacktop(0),
 	_debugger(NULL), _vm(vm),
-	_videoFile(NULL), _videoRef(0), _font(NULL) {
+	_videoFile(NULL), _videoRef(0), _font(NULL), _staufsMove(NULL) {
 	// Initialize the opcode set depending on the engine version
 	switch (version) {
 	case kGroovieT7G:
@@ -1376,33 +1376,21 @@ void Script::o_sub() {
 }
 
 void Script::o_cellmove() {
-	uint16 arg = readScript8bits();
+	uint16 depth = readScript8bits();
 	byte *scriptBoard = &_variables[0x19];
-	byte *board = (byte*) malloc (BOARDSIZE * BOARDSIZE * sizeof(byte));
 	byte startX, startY, endX, endY;
 
-	debugScript(1, true, "CELL MOVE var[0x%02X]", arg);
-
-	// Arguments used by the original implementation: (2, arg, scriptBoard)
-	for (int y = 0; y < 7; y++) {
-		for (int x = 0; x < 7; x++) {
-			uint8 offset = x + BOARDSIZE * y;
-			*(board + offset) = 0;
-			if (*scriptBoard == 0x32) *(board + offset) = CELL_BLUE;
-			if (*scriptBoard == 0x42) *(board + offset) = CELL_GREEN;
-			scriptBoard++;
-			debugScript(1, false, "%d", *(board + offset));
-		}
-		debugScript(1, false, "\n");
-	}
+	debugScript(1, true, "CELL MOVE var[0x%02X]", depth);
 
-	CellGame staufsMove((byte*) board);
-	staufsMove.calcMove((byte*) board, CELL_GREEN, 2);
-	startX = staufsMove.getStartX();
-	startY = staufsMove.getStartY();
-	endX = staufsMove.getEndX();
-	endY = staufsMove.getEndY();
+	if (!_staufsMove)
+		_staufsMove = new CellGame;
 
+	_staufsMove->playStauf(2, depth, scriptBoard);
+
+	startX = _staufsMove->getStartX();
+	startY = _staufsMove->getStartY();
+	endX = _staufsMove->getEndX();
+	endY = _staufsMove->getEndY();
 
 	// Set the movement origin
 	setVariable(0, startY); // y
@@ -1410,8 +1398,6 @@ void Script::o_cellmove() {
 	// Set the movement destination
 	setVariable(2, endY);
 	setVariable(3, endX);
-
-	free (board);
 }
 
 void Script::o_returnscript() {
diff --git a/engines/groovie/script.h b/engines/groovie/script.h
index 664cac82d8..71c26835aa 100644
--- a/engines/groovie/script.h
+++ b/engines/groovie/script.h
@@ -40,6 +40,7 @@ enum EngineVersion {
 };
 
 class GroovieEngine;
+class CellGame;
 
 class Script {
 	friend class Debugger;
@@ -120,6 +121,8 @@ private:
 	Common::String _debugString;
 	uint16 _oldInstruction;
 
+	CellGame *_staufsMove;
+
 	// Helper functions
 	uint8 getCodeByte(uint16 address);
 	uint8 readScript8bits();