GML Memory leak in recursive Chess minmax routines

Selek

Member
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!

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;
}
And here are excerpts from one of the two Minmax functions, in this case Minimize.

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;
 

Nidoking

Member
var possibleMoves = ds_list_create();
var listSize = (ds_list_size(possibleMoves)) - 4;
What were you expecting the size of an empty list to be?

possibleMoves = possibleMoves_scr(boardState, moversSeat, moversColor, true, true);
possibleMoves = avoidCheck_scr(possibleMoves, moversColor, moversSeat, boardState);
If you've posted the code for the possibleMoves_scr or avoidCheck_scr here, you haven't made that clear, but possibleMoves_scr appears to be defined to return a list index, which you're immediately overwriting with the return value of avoidCheck_scr. If avoidCheck_scr is destroying the list and returning a new one, then wow, that's bad design. If avoidCheck_scr is returning the same index you passed in, then why? However, if avoidCheck_scr is returning a new list index, then you're losing the old index and never destroying it. There's your leak.

EDIT: I missed that this is all one script, and you're actually creating a list and then immediately overwriting the index variable. You're leaking AT LEAST one list every time you get to the maximum depth, regardless of what those scripts are doing.
 

FrostyCat

Redemption Seeker
I suggest that you work with an array instead of a list to avoid having to destroy manually. You are not doing any insertions in the middle or gapless deletes anyways.

On top of that, I suggest that you start playing with the GML 2020 additions in GMS 2.3 beta now. Tree search algorithms and other data-driven code are much more intuitive in the new system, and I have first-hand experience implementing MCTS and Minimax with it. There's NO WAY I'd touch the old way ever again.
 

Ido-f

Member
I agree with Nidoking that there might be a leak in possibleMoves_scr or in avoidCheck_scr.

Beyond that, I can only share from my own experience making a chess clone.
Do you use some sort of board re-calculation in order to determine if a move is legal?
Because I did that to check if a move puts its player's king in harm's way.
When I changed it the calculations actually improved from 20 boards per second to over a 1000! (that's without any AI depth).

The solution i used had to do with maintaining relevant data explicitly, and using that that data directly to determine if a move is legal.
It was data about which pieces are protected (and so can't be eaten by the king), what are the cells that can be blocked to "cover" the king and protect it from a check (with regard to the fact that when two pieces threaten the king at the same time there are no such cells), and what pieces are currently pinned to the king and can only move in a certain way.

If you want i can try to go into more detail about it. It's a method I wrote myself though, so you might prefer researching for a proved method online. There ought to be even more efficient ones, too.
 
Last edited:

Selek

Member
Thanks for all those awesome comments! This project is very much a learning exercise, so I am really happy to get all this feedback. I probably should have asked for more guidance before I plunged in, but I often prefer to try to solve problems on my own and then check my work against more efficient solutions developed by others. (That said, I never would have thought of the Minmax recursion on my own.)

What were you expecting the size of an empty list to be
Fair question. I handle an empty list in another bit of code, so the game properly recognizes checkmate and stalemate, although my Minmax algorithm does not score stalemate yet.

EDIT: I missed that this is all one script, and you're actually creating a list and then immediately overwriting the index variable. You're leaking AT LEAST one list every time you get to the maximum depth, regardless of what those scripts are doing.
Now that you've pointed it out, I think it's even worse than that! I'm not overwriting the index variable; I'm overwriting the list itself! PossibleMoves(scr) returns a list of possible moves, and then avoidCheck_scr takes that list as an argument and "prunes" it further by removing any illegal moves. I did try to garbage-collect the overwritten list in avoidCheck, but now that I think about it, it's a stupid way to go about it. I should just have possibleMoves_scr do all the work at once, on one list. I originally had it that way and split them apart to help me debug, which is not a good reason.

I suggest that you work with an array instead of a list to avoid having to destroy manually. You are not doing any insertions in the middle or gapless deletes anyways.
Facepalm! If I'd thought about it, I'd have realized that on any given turn, the list of possible moves can only be 108 or 110 items long or so, from the most involved possible position. (A quick Google search just told me that.) So I just declare an array that's, say, 120 moves long (maybe a 120-item 1D array of 1D arrays that contain info on move start, move finish, piece ID, and special conditions). Then if a list of moves is shorter than that, the last 80 items in the array are zero, and once I hit a "zero" move I stop looking at the array. Is that the idea?

As an aside, my ds_lists don't have enough info in them now, so I've been feeling the urge to refactor anyway. I just defined them as old cell to new cell, when I really need more info, like the identity of the moving piece (for special cases like pawn promotion) and the possibility of a double-move (for castling). My code handles those special cases now, but it's klunky.

On top of that, I suggest that you start playing with the GML 2020 additions in GMS 2.3 beta now. Tree search algorithms and other data-driven code are much more intuitive in the new system, and I have first-hand experience implementing MCTS and Minimax with it. There's NO WAY I'd touch the old way ever again.
Thanks for the suggestion. I've been following the beta with interest, and now I have a reason to download it, especially as I want to experiment with MCTS on my next project -- perhaps a card game.

Do you use some sort of board re-calculation in order to determine if a move is legal?
Because I did that to check if a move puts its player's king in harm's way.
That's what avoidCheck_scr does. As a programming newb, I was rather proud that I got this to work better than I can do myself while playing chess, heh. It catches not only whether a king's own move puts it in check, but whether any other piece moves in such a way as to expose its own king to check.

That said, your method sounds a lot more elegant than mine. In my script, every time I generate a possible move, I call my threatenedSquare script to see whether the move exposes a particular square (in this case, the king's current or expected position). This threatenedSquare script works, but it's clunky -- it methodically checks the target square from all angles, making special allowance for board and edge cases. From what you describe, you just store a handful of "dangerous" cells and check the move against that list?
 
Last edited:

Ido-f

Member
From what you describe, you just store a handful of "dangerous" cells and check the move against that list?
Not precisely. There's a bunch of stuff to do, It's quite a hassle.
I also searched it online now and found my clone fails to handle correctly two rare en-passant scenarios. This article seems to portray a fool proof way to do what I tried. But I like your approach. Trying to piece it together by yourself like that is, maybe, the point behind making a clone in the first place.
 

Selek

Member
This article seems to portray a fool proof way to do what I tried.
@Ido-f , thanks for that link; I enjoyed that article (and the couple of blog posts after it, too). I see the rare en-passant case you mentioned: exposed check by en-passant! I've never seen that in decades of playing mediocre chess, heh.

More to the point, I'm getting a better sense of what you were striving for. Does GML support low-level data structures like the bitboard he describes? That level of optimization is way beyond where I am in my newbish ways. (I actually did study Comp Sci in college for a while, but that was decades ago.) But even if not stored as individual bits, that method is plainly more efficient than mine. As we've discussed, I do like making my own mistakes, and indeed that's why I've been working on clones -- but I also like learning more efficient solutions once I've tried my own approach. :)

@FrostyCat, I went ahead and installed the new beta, and I exported (and duplicated) my existing chess code and imported it into the beta. My 2D arrays still work for now, but obviously they'd need to be changed, since the new system now uses chained 1D arrays. Is that an example of a change you think would benefit my code? Maybe also chained accessors? What other new features might help me?

The new IDE features alone tempt me to refactor my chess engine in the beta and go from there. I'm not trying to sell this thing or make Deep Blue; I'm just trying to learn. Although I do want to get going on an original turn-based game of my own design. Should I do that in the beta or the release version of GMS2?
 

chamaeleon

Member
Does GML support low-level data structures like the bitboard he describes?
Bitboards tend to rely on using 64 bits. Unfortunately, you get the following behavior, if you don't special case handle certain corner cases, due to signed values only in GMS.
GML:
var a = 1<<63;
var b = 1<<62;
var a_test = a & a;
var b_test = b & b;
show_debug_message((a_test ? "Yay":"Nay") + " -- " + (b_test ? "Yay":"Nay"));
Code:
Nay -- Yay
You'll have to be careful with your coding as a result if you want to use all 64 bits, by doing extra comparisons (I can't say what you should do for sure, as I'm not sure what operations you need to perform or what values might be participating).

Some of the issues might go away if you use something like
GML:
var test_result = (my_flags & my_checks) == my_checks;
Where my_flags contains whatever bits the current state is, and my_checks contain whatever bits (one or more) you wish to test.
 
Last edited:

Selek

Member
@chamaeleon , thanks for that very useful reply. I had been wondering whether GML might be a little tricky to use with bitboards. I imagine other languages, like C++, handle bitboards more easily? From what I can tell, most chess bitboards do indeed use all 64 bits, which makes sense given that it's an 8 x 8 chessboard.

I started another thread on how to represent my chess pieces here, and in the course of that discussion, FrostyCat suggested I represent my board with a 1D array, which seems like a good compromise for my purposes. I'm not seeking to make the fastest chess program ever; I am most interested in learning more about Minmax, alpha-beta pruning, and maybe Monte Carlo Tree Search. (In fact, I get depressed playing chess against computers, and my chess engine is almost good enough to beat me already!) But I could see experimenting with bitboards in another project, maybe even another version of a chess project.

One of my goals is to make my own turn-based strategy game, like a wargame; would bitboards be of use there?
 

chamaeleon

Member
I imagine other languages, like C++, handle bitboards more easily?
Yes, languages like C/C++ that has unsigned data types will make this easier, and perhaps less error-prone. Another oddity (at least I think it's an oddity), is that numeric values less than 0.5 (including negative) are considered false, whereas C/C++ considers all non-zero values true. Just little things to keep in mind when trying to translate or adapt any existing algorithm you may come across.

Bitboards make sense in chess because of the happy coincidence of number of squares and number of bits in a 64 bit integer. But conceptually, there's nothing stopping you from having a number of integers that provide a sufficient number of bits and have scripts that take the collection of integers as a "unit" in order to perform some operation on it. Whether it makes sense for your wargame is a different matter, it will wholly depend on your algorithms you intend to use.

Finally, @FrostyCat has made a MCTS program previously if you want to see how complex it becomes using pre-2.3 code, the code is available in their github account (not that is not complex using 2.3 data structures, I imagine...)

Edit: Less code that I remembered in the MCTS tictactoe repo. The MCTS part itself isn't too bad, I must have misremembered based on the number of auxiliary scripts written for convenience and testing.
 
Last edited:

Selek

Member
@chamaeleon, thanks for pointing me in the direction of @FrostyCat's MCTS program. I looked at many of the MCTS and Minmax scripts, partly because of interest in the substance, but also because I'm new to this and it's helpful to see the work of an expert. I was surprised how much of it I was able to follow, but then again I've spent a lot of time wrestling with the Minmax algorithm, so I'm familiar with it. The MCTS code looks plenty complex to me, but the core of it was also recognizable to me.

Above all, I was impressed how short his scripts are. I tend to produce mammoth scripts, hundreds of lines long, instead of parceling things out more. Fortunately, the beta's approach to functions is already curing me of that habit.

I'm loving working on chess, but I'm also wary about investing too much more time into it. @Ido-f linked an article with advice for anyone building a chess engine: "Don't! It's too addictive." It is addictive indeed, and the minute I solve one problem, I start thinking of better ways to solve it. But sooner or later I want to start making games of my own design...
 
Top