I'm relatively new to programming. Using GMS2, I made a working Tetris clone a couple weeks ago, and now I'm working on a chess engine to learn about AI.
I'm using the Minmax algorithm, with two functions (Minimize and Maximize) calling each other recursively to "look ahead" to evaluate an alternating succession of black and white moves. I have not yet implemented alpha-beta pruning to reduce the universe of nodes I have to search. I use only a couple instances of objects. I represent the game board with an 8x8 2D array of 1D arrays with two values, piece and color. I declare virtually all my variables with var, the main exception being the current board state, which is held in a board object as a regular (not global) variable. I have only one global variable, a Boolean that holds the player's choice of color. The big resource-consumer are the ds_lists I use (and destroy) to hold lists of moves; more on this in a moment.
The game runs quite well looking a couple moves ahead -- the AI proposes a move, then considers (1) human response and (2) AI reply. (This is a 2-ply search, yes?) Each AI move takes 5-10 seconds, depending on the complexity of the board. But if I push the depth to, say, a 4-ply search, each move takes a couple minutes. I know I can reduce that somewhat with alpha-beta.
But before I do that, I'm more worried about a memory leak. The game starts at about 15Mb of memory and goes up a Mb or two during every AI turn. During the human turn, memory usage is completely flat. Profiling indicates that Minimize and Maximize are (not surprisingly) taking the most time. I've also tried to use the profile to ensure that for every ds_list_create, I call a ds_list_destroy(). And I've used search/replace to check on this. I did reduce the leak by destroying a couple lists I'd forgotten to garbage-collect (e.g., a temporary list of candidate moves I hold until necessary to "break a tie" to decide on a final move). Conversely, when I put in a little stalemate-check code involving yet another new ds_list, the leak virtually doubled.
So I'm pretty sure the lists are the culprit, and I'm worried the ds_lists in Max/Min in particular are to blame. I use ds_list_destroy when each terminates, but because they call each other recursively, they hang around for hundreds or even thousands of calls while they do their thing. (As I understand recursion in GMS2, one script pauses while the other executes, then vice-versa. This is necessary for my logic because I need each script to hold the "min" or "max" score of the move the other script is processing.) In the code below, am I properly cleaning up the lists created by the Min function? (Max is virtually identical.) Should I be refactoring my code to use something other than ds_lists? Or to replace recursion with a simple down-the-line call of a Max1 calling a Min2 calling a Max3 calling a Min4 calling a Max 5 (etc), and I guess storing the max/min variables in a regular non-var variable somewhere else?
Two code snippets to share. First, my lazy-man's first go at stalemate-scoring code. I'm curious why the leak spiked so much when I stuck this inside the Max function. FYI, Hermione is the name of my AI. Even at just two-ply, she gives me a pretty good game!
And here are excerpts from one of the two Minmax functions, in this case Minimize.
I'm using the Minmax algorithm, with two functions (Minimize and Maximize) calling each other recursively to "look ahead" to evaluate an alternating succession of black and white moves. I have not yet implemented alpha-beta pruning to reduce the universe of nodes I have to search. I use only a couple instances of objects. I represent the game board with an 8x8 2D array of 1D arrays with two values, piece and color. I declare virtually all my variables with var, the main exception being the current board state, which is held in a board object as a regular (not global) variable. I have only one global variable, a Boolean that holds the player's choice of color. The big resource-consumer are the ds_lists I use (and destroy) to hold lists of moves; more on this in a moment.
The game runs quite well looking a couple moves ahead -- the AI proposes a move, then considers (1) human response and (2) AI reply. (This is a 2-ply search, yes?) Each AI move takes 5-10 seconds, depending on the complexity of the board. But if I push the depth to, say, a 4-ply search, each move takes a couple minutes. I know I can reduce that somewhat with alpha-beta.
But before I do that, I'm more worried about a memory leak. The game starts at about 15Mb of memory and goes up a Mb or two during every AI turn. During the human turn, memory usage is completely flat. Profiling indicates that Minimize and Maximize are (not surprisingly) taking the most time. I've also tried to use the profile to ensure that for every ds_list_create, I call a ds_list_destroy(). And I've used search/replace to check on this. I did reduce the leak by destroying a couple lists I'd forgotten to garbage-collect (e.g., a temporary list of candidate moves I hold until necessary to "break a tie" to decide on a final move). Conversely, when I put in a little stalemate-check code involving yet another new ds_list, the leak virtually doubled.
So I'm pretty sure the lists are the culprit, and I'm worried the ds_lists in Max/Min in particular are to blame. I use ds_list_destroy when each terminates, but because they call each other recursively, they hang around for hundreds or even thousands of calls while they do their thing. (As I understand recursion in GMS2, one script pauses while the other executes, then vice-versa. This is necessary for my logic because I need each script to hold the "min" or "max" score of the move the other script is processing.) In the code below, am I properly cleaning up the lists created by the Min function? (Max is virtually identical.) Should I be refactoring my code to use something other than ds_lists? Or to replace recursion with a simple down-the-line call of a Max1 calling a Min2 calling a Max3 calling a Min4 calling a Max 5 (etc), and I guess storing the max/min variables in a regular non-var variable somewhere else?
Two code snippets to share. First, my lazy-man's first go at stalemate-scoring code. I'm curious why the leak spiked so much when I stuck this inside the Max function. FYI, Hermione is the name of my AI. Even at just two-ply, she gives me a pretty good game!
GML:
var stalemateCheck = ds_list_create();
stalemateCheck = possibleMoves_scr(boardState, NORTH, HermioneColor, true, true);
if ds_list_size(stalemateCheck) == 0
{
ds_list_destroy(possibleMoves);
ds_list_destroy(stalemateCheck);
return 0;
}
GML:
var boardState = argument0; // Someone (top-node or Maximize) has sent us ONE move on ONE board.
var moversSeat = argument1; // in any human game, this will be NORTH. We flip to south below.
var moversColor = argument2;
var searchDepth = argument3;
var HermioneColor = board_object.GrangerColor;
var possibleMoves = ds_list_create();
var listSize = (ds_list_size(possibleMoves)) - 4;
var positionScore = 0;
var minScore = infinity; // Return value. Eval will compare this to other maxscores from other sent moves.
var listIndex = 0;
var piece = [0 , 0];
var selectedPiece = [0 , 0];
// I've edited out some side- and color-checking code that's here. Main body follows:
if (searchDepth > 1) // Reached bottom of tree. Report best score to "evaluate", our root node.
{
for (var xx = 0; xx < 8; xx += 1;)
{
for (var yy = 0; yy < 8; yy += 1;)
{
var piece = boardState[xx, yy];
if piece[1] == HermioneColor
{
switch (piece[0])
{
case PAWN:
{
positionScore += (VPAWN + board_object.AIpawnTable[xx, yy]);
break;
}
// ... editing out most scoring ...
case KING:
{
positionScore -= (VKING + board_object.HumanKingTable[xx, yy]);
break;
}
}
}
}
}
// show_debug_message("MIN scores a final leaf: " + string(positionScore));
ds_list_destroy(possibleMoves);
return positionScore;
}
// *** GENERATE POSSIBLE MOVES, one at a time, from INCOMING BOARD
possibleMoves = possibleMoves_scr(boardState, moversSeat, moversColor, true, true);
possibleMoves = avoidCheck_scr(possibleMoves, moversColor, moversSeat, boardState);
listSize = (ds_list_size(possibleMoves)) - 4;
for (listIndex = 0; listIndex <= listSize; listIndex += 4)
{
var oldX = ds_list_find_value(possibleMoves,listIndex);
var oldY = ds_list_find_value(possibleMoves,listIndex + 1);
var newX = ds_list_find_value(possibleMoves,listIndex + 2);
var newY = ds_list_find_value(possibleMoves,listIndex + 3);
boardState = argument0; // always reset board before "making" next move
selectedPiece = boardState[oldX, oldY]; // "move" responding piece to new location
boardState[newX, newY] = selectedPiece;
boardState[oldX, oldY] = [0 , 0];
var maximizedScore = Maximize(boardState, moversSeat, moversColor, searchDepth + 1);
if (maximizedScore < minScore) minScore = maximizedScore;
// note the recursive call to Maximize here. Max does the same, calling Min.
}
searchDepth += 1;
ds_list_destroy(possibleMoves);
return minScore;