[Scummvm-git-logs] scummvm master -> d0cb8ef568b13544bb98cea48c5f3a8f7e35df71
Die4Ever
30947252+Die4Ever at users.noreply.github.com
Wed Oct 20 22:27:26 UTC 2021
This automated email contains information about 1 new commit which have been
pushed to the 'scummvm' repo located at https://github.com/scummvm/scummvm .
Summary:
d0cb8ef568 GROOVIE: T11H cake rewrite
Commit: d0cb8ef568b13544bb98cea48c5f3a8f7e35df71
https://github.com/scummvm/scummvm/commit/d0cb8ef568b13544bb98cea48c5f3a8f7e35df71
Author: Die4Ever (die4ever2005 at gmail.com)
Date: 2021-10-20T17:21:09-05:00
Commit Message:
GROOVIE: T11H cake rewrite
Authentic rewrite of the original connect four cake AI.
Automated tests used for verification here
https://github.com/Die4Ever/scummvm/blob/4c08e5829fc661086aa52a50221cacd9a13dd58d/engines/groovie/logic/t11hgame.cpp#L490-L577
Squashed commit of the following:
commit 346f1f1f3a6ce7382054b909022285133310cd43
Author: Die4Ever <die4ever2005 at gmail.com>
Date: Wed Oct 20 17:19:50 2021 -0500
GROOVIE: T11H cake remove tests
commit 8e5cd4a1682125914f710760f1920affff109567
Author: Die4Ever <die4ever2005 at gmail.com>
Date: Wed Oct 20 16:40:50 2021 -0500
GROOVIE: T11H cake cleanup and comments
commit 4c08e5829fc661086aa52a50221cacd9a13dd58d
Author: Die4Ever <die4ever2005 at gmail.com>
Date: Wed Oct 20 16:39:34 2021 -0500
GROOVIE: T11H cake cleanup and comments
commit b5ead0f5028534b4db106b38c0c609b2020d826d
Author: Die4Ever <die4ever2005 at gmail.com>
Date: Wed Oct 20 06:57:19 2021 -0500
GROOVIE: T11H cake rewrite rng
commit 12d6a0f9f4b8f6fa1522b69ae3cae678d03ad7f1
Author: Die4Ever <die4ever2005 at gmail.com>
Date: Wed Oct 20 06:45:28 2021 -0500
GROOVIE: T11H cake rewrite
Changed paths:
engines/groovie/logic/t11hgame.cpp
engines/groovie/logic/t11hgame.h
diff --git a/engines/groovie/logic/t11hgame.cpp b/engines/groovie/logic/t11hgame.cpp
index 56f977d097..5826e77d45 100644
--- a/engines/groovie/logic/t11hgame.cpp
+++ b/engines/groovie/logic/t11hgame.cpp
@@ -33,8 +33,8 @@
namespace Groovie {
-T11hGame::T11hGame(byte *scriptVariables) :
- _random("GroovieT11hGame"), _scriptVariables(scriptVariables) {
+T11hGame::T11hGame(byte *scriptVariables)
+ : _random("GroovieT11hGame"), _scriptVariables(scriptVariables), _cake(NULL), _beehiveHexagons() {
}
T11hGame::~T11hGame() {
@@ -154,129 +154,358 @@ void T11hGame::opMouseTrap() {
}
}
+class T11hCake {
/*
* Connect Four puzzle, the cake in the dining room
*/
-void T11hGame::opConnectFour() {
- byte &last_move = _scriptVariables[1];
- byte &winner = _scriptVariables[3];
+public:
+ Common::RandomSource &_random;
+
+ /*
+ * T11hCake() constructor
+ * - Each spot on the board is part of multiple potential victory lines
+ * - The first x and y dimensions of the loops select the origin point of the line
+ * - The z is for the distance along that line
+ * - Then we push_back the id number of the line into the array at _map.indecies[x][y]
+ * - This is used in UpdateScores()
+ * .
+ * @see UpdateScores()
+ */
+ T11hCake(Common::RandomSource &rng) : _random(rng) {
+ Restart();
+
+ _map = {};
+ int numLines = 0;
+
+ // map all the lines with slope of (1, 0)
+ for (int y = 0; y < HEIGHT; y++) {
+ for (int x = 0; x <= WIDTH - GOAL_LEN; x++) {
+ for (int z = 0; z < GOAL_LEN; z++) {
+ SetLineNum(x + z, y, numLines);
+ }
+ numLines++;
+ }
+ }
+
+ // map all the lines with slope of (0, 1)
+ for (int x = 0; x < WIDTH; x++) {
+ for (int y = 0; y <= HEIGHT - GOAL_LEN; y++) {
+ for (int z = 0; z < GOAL_LEN; z++) {
+ SetLineNum(x, y + z, numLines);
+ }
+ numLines++;
+ }
+ }
+
+ // map all the lines with slope of (1,1)
+ for (int y = 0; y <= HEIGHT - GOAL_LEN; y++) {
+ for (int x = 0; x <= WIDTH - GOAL_LEN; x++) {
+ for (int z = 0; z < GOAL_LEN; z++) {
+ SetLineNum(x + z, y + z, numLines);
+ }
+ numLines++;
+ }
+ }
- if (last_move == 8) {
- clearCake();
- return;
+ // map all the lines with slope of (1,-1)
+ for (int y = GOAL_LEN - 1; y < HEIGHT; y++) {
+ for (int x = 0; x <= WIDTH - GOAL_LEN; x++) {
+ for (int z = 0; z < GOAL_LEN; z++) {
+ SetLineNum(x + z, y - z, numLines);
+ }
+ numLines++;
+ }
+ }
}
- if (last_move == 9) {
- // samantha makes a move
- // TODO: fix graphical bug when samantha makes a move
- last_move = connectFourAI();
- return;
+ byte OpConnectFour(byte &lastMove) {
+ if (lastMove == 8) {
+ Restart();
+ return 0;
+ }
+
+ if (lastMove == 9) {
+ // samantha makes a move
+ // TODO: fix graphical bug when samantha makes a move
+ lastMove = AiGetBestMove(6);
+ _hasCheated = true;
+ return 0;
+ }
+
+ if (IsColumnFull(lastMove)) {
+ warning("player tried to place a bon bon in a full column, last_move: %d", (int)lastMove);
+ lastMove = 10;
+ return 0;
+ }
+
+ PlaceBonBon(lastMove);
+ byte winner = GetWinner();
+ if (winner) {
+ return winner;
+ }
+
+ lastMove = AiGetBestMove(4 + (_hasCheated == false));
+ PlaceBonBon(lastMove);
+ if (GameEnded())
+ return STAUF;
+
+ return 0;
}
- cakePlaceBonBon(last_move, CAKE_TEAM_PLAYER);
- winner = cakeGetWinner();
- if (winner) {
- return;
+private:
+ static const int WIDTH = 8;
+ static const int HEIGHT = 7;
+ static const int GOAL_LEN = 4;
+ static const int WIN_SCORE = 1000000;//!< the number of points added for a connect four
+ static const byte STAUF = 1;
+ static const byte PLAYER = 2;
+ static const int NUM_LINES = 107;//!< how many potential victory lines there are
+
+
+ //! ID numbers for all of the potential victory lines for each spot on the board
+ struct LinesMappings {
+ byte lengths[WIDTH][HEIGHT];
+ byte indecies[WIDTH][HEIGHT][GOAL_LEN * GOAL_LEN];
+ };
+
+ //! how many points a player has, and their progress on potential victory lines
+ struct PlayerProgress {
+ int _score;
+ int _linesCounters[NUM_LINES];//!< how many pieces are claimed in each potential victory, links to LineMappings, an entry of 4 means that's a victory
+ };
+
+ PlayerProgress _playerProgress;
+ PlayerProgress _staufProgress;
+
+ byte _boardState[WIDTH][HEIGHT];//!< (0, 0) is the bottom left of the board
+ byte _columnHeights[WIDTH];
+
+ int _moveCount;
+ bool _hasCheated;
+
+ LinesMappings _map;//!< ID numbers for all of the potential victory lines for each spot on the board
+
+ void Restart() {
+ _playerProgress = {};
+ _staufProgress = {};
+ memset(_boardState, 0, sizeof(_boardState));
+ memset(_columnHeights, 0, sizeof(_columnHeights));
+ _moveCount = 0;
+ _hasCheated = false;
+
+ _playerProgress._score = NUM_LINES;
+ _staufProgress._score = NUM_LINES;
}
- last_move = connectFourAI();
- cakePlaceBonBon(last_move, CAKE_TEAM_STAUF);
- winner = cakeGetWinner();
-}
+ void SetLineNum(uint x, uint y, uint index) {
+ assert(x < WIDTH);
+ assert(y < HEIGHT);
+ byte slot = _map.lengths[x][y]++;
+ assert(slot < GOAL_LEN * GOAL_LEN);
+ assert(index < NUM_LINES);
+ _map.indecies[x][y][slot] = index;
+ }
-byte T11hGame::connectFourAI() {
- // TODO: copy the AI from the game
- // the cakeGetLineLen function returns the length of the line which should be the scoring function
- uint slot = 0;
- do {
- slot = _random.getRandomNumber(7);
- } while (cake_board[slot][CAKE_BOARD_HEIGHT - 1]);
- return slot;
-}
+ bool IsColumnFull(byte column) {
+ return _columnHeights[column] >= HEIGHT;
+ }
-bool T11hGame::isCakeFull() {
- return NULL == memchr(cake_board, 0, sizeof(cake_board));
-}
+ PlayerProgress &GetPlayerProgress(bool stauf) {
+ if (stauf)
+ return _staufProgress;
+ else
+ return _playerProgress;
+ }
-byte T11hGame::cakeGetOpponent(byte team) {
- if (team == CAKE_TEAM_PLAYER)
- return CAKE_TEAM_STAUF;
- else if (team == CAKE_TEAM_STAUF)
- return CAKE_TEAM_PLAYER;
- return 0;
-}
+ /*
+ * UpdateScores()
+ * - Each PlayerProgress has an array of ints, _linesCounters[], where each entry maps to the ID of a line
+ * - When a bon bon is added to the board, we look up _map.lengths[x][y] and then loop through all the indecies for that point
+ * - Increment the PlayerProgress._linesCounters[id]
+ * - Calculate the scores proportional to the PlayerProgress._linesCounters[id]
+ * .
+ * .
+ */
+ void UpdateScores(byte x, bool revert=false) {
+ bool stauf = _moveCount % 2;
+ PlayerProgress &pp = GetPlayerProgress(stauf);
+
+ byte y = _columnHeights[x] - 1;
+
+ // get the number of potential victory lines that this spot exists in
+ int num_lines = _map.lengths[x][y];
+
+ for (int line = 0; line < num_lines; line++) {
+ // get the ID for this potential victory line
+ int index = _map.indecies[x][y][line];
+ int len = pp._linesCounters[index];
+
+ // add this new bon bon to the progress of this potential victory line, or remove in the case of revert
+ int mult = 1;// mult is used for multiplying the score gains, depends on revert
+ if (!revert)
+ pp._linesCounters[index]++;
+ else {
+ len = --pp._linesCounters[index];
+ mult = -1;
+ }
-// also use the cakeGetLineLen function as a scoring function for the AI
-int T11hGame::cakeGetLineLen(int start_x, int start_y, int slope_x, int slope_y, byte team) {
- byte opponent = cakeGetOpponent(team);
+ if (GOAL_LEN == len + 1) {
+ // that's a bingo
+ pp._score += WIN_SCORE * mult;
+ }
+ else {
+ PlayerProgress &pp2 = GetPlayerProgress(!stauf);
+ int len2 = pp2._linesCounters[index];
+ if (len == 0) {
+ // we started a new line, take away the points the opponent had from this line since we ruined it for them
+ pp2._score -= (1 << (len2 & 31)) * mult;
+ }
+ if (len2 == 0) {
+ // the opponent doesn't have any spots in this line, so we get points for it
+ pp._score += (1 << (len & 31)) * mult;
+ }
+ }
+ }
+ }
+
+ void PlaceBonBon(byte x) {
+ byte y = _columnHeights[x]++;
+ if (_moveCount % 2)
+ _boardState[x][y] = STAUF;
+ else
+ _boardState[x][y] = PLAYER;
+
+ UpdateScores(x);
+
+ _moveCount++;
+ }
+
+ void RevertMove(byte x) {
+ // PlaceBonBon in reverse, this is used for the AI's recursion rollback
+ _moveCount--;
+
+ UpdateScores(x, true);
+
+ byte y = --_columnHeights[x];
+ _boardState[x][y] = 0;
+ }
+
+ byte GetWinner() {
+ if (_playerProgress._score >= WIN_SCORE)
+ return PLAYER;
+
+ if (_staufProgress._score >= WIN_SCORE)
+ return STAUF;
- // return 0 for worthless lines
- if (start_x + slope_x * CAKE_GOAL_LEN > CAKE_BOARD_WIDTH)
- return 0;
- if (start_x + slope_x * CAKE_GOAL_LEN < 0)
- return 0;
- if (start_y + slope_y * CAKE_GOAL_LEN > CAKE_BOARD_HEIGHT)
- return 0;
- if (start_y + slope_y * CAKE_GOAL_LEN < 0)
return 0;
+ }
- // don't loop past CAKE_GOAL_LEN because more than 4 is useless to rules and the AI
- int x = start_x;
- int y = start_y;
- int len = 0;
- for (int i = 0; i < CAKE_GOAL_LEN; i++) {
- if (cake_board[x][y] == opponent)
- return 0; // return 0 for worthless lines
- if (cake_board[x][y] == team)
- len++;
-
- x += slope_x;
- y += slope_y;
+ bool GameEnded() {
+ if (GetWinner())
+ return true;
+
+ if (_moveCount >= WIDTH * HEIGHT)
+ return true;
+
+ return false;
+ }
+
+ int GetScoreDiff() {
+ if (_moveCount % 2)
+ return _staufProgress._score - _playerProgress._score;
+ else
+ return _playerProgress._score - _staufProgress._score;
}
- return len;
-}
-byte T11hGame::cakeGetWinner() {
- // make sure to check if all columns are maxed then Stauf wins
- if (isCakeFull())
- return CAKE_TEAM_STAUF;
-
- // search for lines of 4, we search up, right, up-right, and down-right
- for (int x = 0; x < CAKE_BOARD_WIDTH; x++) {
- for (int y = 0; y < CAKE_BOARD_HEIGHT; y++) {
- byte team = cake_board[x][y];
- // if this spot is team 0 then we can move on to the next column
- if (team == 0)
+ int AiRecurse(int search_depth, int parent_score) {
+ int best_score = 0x7fffffff;
+
+ for (byte move = 0; move < WIDTH; move++) {
+ if (IsColumnFull(move))
+ continue;
+
+ PlaceBonBon(move);
+ int score = GetScoreDiff();
+ if (search_depth > 1 && !GameEnded())
+ score = AiRecurse(search_depth - 1, best_score);
+ RevertMove(move);
+
+ if (score < best_score)
+ best_score = score;
+
+ if (-parent_score != best_score && parent_score <= -best_score)
break;
+ }
+
+ // we negate the score because from the perspective of our parent caller, this is his opponent's score
+ return -best_score;
+ }
- // if we find a line, then we return the team value stored in this spot
- int line = 0;
- line = MAX(cakeGetLineLen(x, y, 1, 0, team), line);
- line = MAX(cakeGetLineLen(x, y, 0, 1, team), line);
- line = MAX(cakeGetLineLen(x, y, 1, 1, team), line);
- line = MAX(cakeGetLineLen(x, y, 1, -1, team), line);
+ uint Rng() {
+ return _random.getRandomNumber(UINT_MAX);
+ }
- if (line >= CAKE_GOAL_LEN)
- return team;
+ byte AiGetBestMove(int search_depth) {
+ int best_move = 0xffff;
+ uint counter = 1;
+
+ for (int best_score = 0x7fffffff; best_score > 999999 && search_depth > 1; search_depth--) {
+ for (byte move = 0; move < WIDTH; move++) {
+ if (IsColumnFull(move))
+ continue;
+
+ PlaceBonBon(move);
+ if (GetWinner()) {
+ RevertMove(move);
+ return move;
+ }
+
+ int score = AiRecurse(search_depth - 1, best_score);
+ RevertMove(move);
+ if (score < best_score) {
+ counter = 1;
+ best_move = move;
+ best_score = score;
+ } else if (best_score == score) {
+ // rng is only used on moves with equal scores
+ counter++;
+ uint r = Rng() % 1000000;
+ if (r * counter < 1000000) {
+ best_move = move;
+ }
+ }
+ }
}
+
+ return best_move;
}
+};
- return 0;
-}
+void T11hGame::opConnectFour() {
+ byte &last_move = _scriptVariables[1];
+ byte &winner = _scriptVariables[3];
+ winner = 0;
+
+ if (_cake == NULL) {
+ clearAIs();
+ _cake = new T11hCake(_random);
+ }
-void T11hGame::clearCake() {
- memset(cake_board, 0, sizeof(cake_board));
+ winner = _cake->OpConnectFour(last_move);
+
+ if (winner) {
+ clearAIs();
+ }
}
-void T11hGame::cakePlaceBonBon(int x, byte team) {
- for (int y = 0; y < CAKE_BOARD_HEIGHT; y++) {
- if (cake_board[x][y] == 0) {
- cake_board[x][y] = team;
- return;
- }
+void T11hGame::clearAIs() {
+ if (_cake != NULL) {
+ delete _cake;
+ _cake = NULL;
}
}
+
/*
* Beehive puzzle
*
diff --git a/engines/groovie/logic/t11hgame.h b/engines/groovie/logic/t11hgame.h
index 294c85953a..7bb97156cc 100644
--- a/engines/groovie/logic/t11hgame.h
+++ b/engines/groovie/logic/t11hgame.h
@@ -30,6 +30,10 @@ namespace Groovie {
class GroovieEngine;
+#ifdef ENABLE_GROOVIE2
+class T11hCake;
+#endif
+
class T11hGame {
public:
#ifdef ENABLE_GROOVIE2
@@ -43,7 +47,6 @@ private:
void opMouseTrap();
void opConnectFour();
- byte connectFourAI();
void opBeehive();
void opPente();
void opGallery();
@@ -56,23 +59,11 @@ private:
void inline setScriptVar16(uint16 var, uint16 value);
uint16 inline getScriptVar16(uint16 var);
- bool isCakeFull();
- byte cakeGetWinner();
- void clearCake();
- void cakePlaceBonBon(int x, byte team);
- byte cakeGetOpponent(byte team);
- int cakeGetLineLen(int start_x, int start_y, int slope_x, int slope_y, byte team);
+ void clearAIs();
+ T11hCake *_cake;
byte *_scriptVariables;
- static const int CAKE_BOARD_WIDTH = 8;
- static const int CAKE_BOARD_HEIGHT = 7;
- // (0, 0) is the bottom left of the board
- byte cake_board[CAKE_BOARD_WIDTH][CAKE_BOARD_HEIGHT];
- static const byte CAKE_TEAM_STAUF = 1;
- static const byte CAKE_TEAM_PLAYER = 2;
- static const int CAKE_GOAL_LEN = 4;
-
int8 _beehiveHexagons[61];
static const byte kGalleryLinks[21][10];
More information about the Scummvm-git-logs
mailing list