SOLVED Help with Structuring Data for Chess and Structs Question

[Jam373]

So currently I'm storing the id's of all my chess pieces into an 8x8 ds_grid representing the chess board. Instance variables such as has_moved are referenced and changed to deal with castling and double pawn moves ect.

This worked perfectly fine until I started to work on the ai. Only after completing my first draft of a minimax algo did I realise this won't work for keeping data about future moves. How will I keep track of what has_moved should be for one future branch without affecting another branch or the current position. I could make a save/load system for it but that would surely be horribly slow and overcomplicated.

My main question is how would you recommend I structure the data instead? I was looking into using structs/constructors instead (which are new to me) but was unsure if my current thought process would work. I'd have a constructor for chess pieces storing id, colour, type of piece, has_moved, x, y ect. Then I'd create a struct for each piece and store them in an 8x8 grid as before. Ideally I wouldn't store them in variables, but would instead just reference them through the array or ds_grid into a local variable only when needed. So they would be sitting inside an array/ds_grid without a reference variable for the most part. Does this work? I'm afraid of this creating memory leaks with my minimax algorithm, creating hundreds of thousands of struct copies without references to be dumped after a few seconds.

Edit: Maybe not clear so let me explain. The reason I can't store the structs in variables is because my game is endless chess where new pieces can spawn. Also I guess minimax means i will have thousands of struct copies of a single piece.

 

[tadashibashi]

So currently I'm storing the id's of all my chess pieces into an 8x8 ds_grid representing the chess board. Instance variables such as has_moved are referenced and changed to deal with castling and double pawn moves ect.

This worked perfectly fine until I started to work on the ai. Only after completing my first draft of a minimax algo did I realise this won't work for keeping data about future moves. How will I keep track of what has_moved should be for one future branch without affecting another branch or the current position. I could make a save/load system for it but that would surely be horribly slow and overcomplicated.

My main question is how would you recommend I structure the data instead? I was looking into using structs/constructors instead (which are new to me) but was unsure if my current thought process would work. I'd have a constructor for chess pieces storing id, colour, type of piece, has_moved, x, y ect. Then I'd create a struct for each piece and store them in an 8x8 grid as before. Ideally I wouldn't store them in variables, but would instead just reference them through the array or ds_grid into a local variable only when needed. So they would be sitting inside an array/ds_grid without a reference variable for the most part. Does this work? I'm afraid of this creating memory leaks with my minimax algorithm, creating hundreds of thousands of struct copies without references to be dumped after a few seconds.

Edit: Maybe not clear so let me explain. The reason I can't store the structs in variables is because my game is endless chess where new pieces can spawn. Also I guess minimax means i will have thousands of struct copies of a single piece.

Hello,
Structs sound like it fits better for what you're doing since they're lighter weight than game objects. There's no need to worry about memory leaks with these (unless there's unfreed ds inside them) since there's a garbage collector that will automatically handle deletion. Also structs sitting in a data structure are still referenced and won't be garbage collected. Will you be dereferencing these lists often?

Struct object pooling might be a good way to avoid a memory performance hit from too many creations and deletions. Using this pattern, when an object is no longer needed it isn't discarded but rather put back into the pool, and then you can request "revived" ones when you need new ones.

I wish I were more knowledgeable in AI, and looked up the general definition of the minimax algorithm to avoid worst case scenario. Whatever you're doing sounds really cool

 

[Jam373]

Hello,
Structs sound like it fits better for what you're doing since they're lighter weight than game objects. There's no need to worry about memory leaks with these (unless there's unfreed ds inside them) since there's a garbage collector that will automatically handle deletion. Also structs sitting in a data structure are still referenced and won't be garbage collected. Will you be dereferencing these lists often?

Struct object pooling might be a good way to avoid a memory performance hit from too many creations and deletions. Using this pattern, when an object is no longer needed it isn't discarded but rather put back into the pool, and then you can request "revived" ones when you need new ones.

I wish I were more knowledgeable in AI, and looked up the general definition of the minimax algorithm to avoid worst case scenario. Whatever you're doing sounds really cool

Thanks, just the info I need!

Will you be dereferencing these lists often?

Do you mean my ds_grids? They will always be referenced when in use and destroyed when both they and the structs aren't needed.

I hadn't considered the performance hit of creating and deleting actually so I'll definitely look into object pooling, but I also don't know how many structs will be in use at any one time and it could be millions. Would having millions active all the time be better for performance? Do I store them all in a giant ds_stack and pop one whenever I need it?

 

[FrostyCat]

You should consider the points raised in this topic for how to represent a board state in a compact, GC-friendly manner. Using ds_grid and physical instances for the board's data model is old-hat and unsustainable.

 

[Jam373]

You should consider the points raised in this topic for how to represent a board state in a compact, GC-friendly manner. Using ds_grid and physical instances for the board's data model is old-hat and unsustainable.

Oh wow, that was roughly the other idea I had in my head but its gunna take a lot of code rewriting comparitively. I also have never used bitwise or enums. I understand most of what you wrote but not sure what piece & 8 actually means. I understand that physical instances are a bad idea, but what's wrong with ds_grids out of curiosity?
Anyway thanks a lot, super helpful!

 

[FrostyCat]

The biggest problem with DS data structures is their need for manual cleanup and management. Arrays and structs are automatically handled by the garbage collector.

 

[tadashibashi]

Thanks, just the info I need!

Great!

Do you mean my ds_grids? They will always be referenced when in use and destroyed when both they and the structs aren't needed.

By "list" I meant just discarding any ds/array, sorry I should've been be more specific.

Would having millions active all the time be better for performance? Do I store them all in a giant ds_stack and pop one whenever I need it?

Yes, pre-allocating these millions will be much better for performance than creating and deleting them often since there will be a lot of garbage to collect. It can be expandable too, like if you request from an empty stack you can allocate a certain amount more into it.

From what Frosty Cat has suggested, if you're storing each move as a compact board, maybe this is the struct to pool instead of each individual piece? For future moves, each board could have a next_move reference pointing to the next board, and maybe a last_move if necessary.

Or do you just need each individual piece's move for instructions? I'm not too sure of what's going on at the higher level.

 

[Neptune]

Nothing wrong with data structures (ds_grid) and manual cleanup. Don't overcomplicate a simple issue because other people say "Ooo, but it's not the newest (overly robust) method!!"
What are you going to have, one 8x8 grid? A ds_grid is literally the perfect tool for making a chess game.

Even if you forget to clean the dang thing, it's going to be like < 1 kilobyte memory leak
And I would think that grid wouldnt be popping in and out of existence a bunch, you'd create it in the beginning and dump it at the close of application... No sweat!

 

[nacho_chicken]

Nothing wrong with data structures (ds_grid) and manual cleanup. Don't overcomplicate a simple issue because other people say "Ooo, but it's not the newest (overly robust) method!!"
What are you going to have, one 8x8 grid?

Even if you forget to clean the dang thing, it's going to be like < 1 kilobyte memory leak
And I would think that grid wouldnt be popping in and out of existence a bunch, you'd create it in the beginning and dump it at the close of application... No sweat!

I disagree with this. Not only are structs and the added array functionality new and robust, they are also significantly simpler to implement than data structures, and have far more apparent use cases. How many use cases can you think of that prefer region-wide setting/getting functions (ds_grid's strong point) to per-cell functionality? For most use-cases there's zero reason to go for hard data structures when newer tools do basic jobs better, especially when ds_grids come at such a heavy cost to the management of data.

 

[tadashibashi]

I disagree with this. Not only are structs and the added array functionality new and robust, they are also significantly simpler to implement than data structures, and have far more apparent use cases. How many use cases can you think of that prefer region-wide setting/getting functions (ds_grid's strong point) to per-cell functionality? For most use-cases there's zero reason to go for hard data structures when newer tools do basic jobs better, especially when ds_grids come at such a heavy cost to the management of data.

The nice thing about Game Maker data structures is the control you have over memory management, so as long as you're careful there's nothing to fear.
I agree, the convenience of structs is awesome. On the other hand if you're creating a million+ of them per second like the OP, we still need to be aware of the impact on the garbage collector.

Speaking of the OP, let's get back to helping solve the topic

 

[Neptune]

Well to each their own.
Maybe my ways are strange... When I look at other GM user's code it looks like Chinese more than half the time lol

 

[Jam373]

@Neptune @nacho_chicken @tadashibashi Very interesting convo happening here!! I was gunna make my big decision this morning but now I'm on the fence again. I actually really enjoy using ds_grids, I'd almost say I'm quite good at managing them and never have memory issues. But @Neptune I must admit because of the chess ai/engine, I'm making and deleting hundreds of thousands of them a second on the ai's turn. Now this is all done with a neat function so grid management isnt a concern convenience wise, but I have no clue how it compares performance wise to doing the same thing with arrays and structs or what @FrostyCat suggested (well frostycat's is surely better but by how much I don't know.

The problem is that frostycat's method is quite daunting as all my chess logic functions will need to be completely rewritten (finding moves, check, checkmate ect.) but chess ai might be the first project I've worked on where performance actually matters. The difference between 1 second per move and 10 seconds per move is a lot. But I can deal with 2 seconds vs 1, it doesn't have to be the most efficient engine possible. So I guess what I'd like to know before I decide is what would the performance difference be between ds_grids and structs, 2D arrays and structs, and 1D arrays with binary data?

 

[Jam373]

Or do you just need each individual piece's move for instructions? I'm not too sure of what's going on at the higher level.

yea so I store all the moves at depth 0 (present move) into a grid and with each I perform the minimax algo nested in such a way that once branch ends are reached it returns best board evaluations (for whatever colour's turn it is at that depth) all the way back till the depth 0 starting move, so no need to store prev and next move. Once that's been done for all depth 0 moves you just pick the one with the best evaluation.

Does pooling only apply to structs or should I be doing the same with arrays (if thats the direction I go)?

 

[tadashibashi]

I was gunna make my big decision this morning but now I'm on the fence again. I actually really enjoy using ds_grids, I'd almost say I'm quite good at managing them and never have memory issues.

You seem especially careful about what you're doing, I say go for what's working for you. Also if you're using arrays, you have to be careful about copying the entirety of its contents vs referencing. For example if you modify one element without the "@" accessor, it will copy the entire thing and it is no longer a reference to the former, which I can imagine could get expensive if this is done and millions of copies are being made on accident.

yea so I store all the moves at depth 0 (present move) into a grid and with each I perform the minimax algo nested in such a way that once branch ends are reached it returns best board evaluations (for whatever colour's turn it is at that depth) all the way back till the depth 0 starting move, so no need to store prev and next move. Once that's been done for all depth 0 moves you just pick the one with the best evaluation.

I think I'm understanding, so there is another grid storing all of the moves and "depth 0" is the first index of the 1st dimension of that grid?
Is a move an entire 8x8 board grid, or just something representing "piece to e4"?

Does pooling only apply to structs or should I be doing the same with arrays (if thats the direction I go)?

Yes, it would be the same with arrays since those are also automatically managed.

 

[Jam373]

You seem especially careful about what you're doing, I say go for what's working for you. Also if you're using arrays, you have to be careful about copying the entirety of its contents vs referencing. For example if you modify one element without the "@" accessor, it will copy the entire thing and it is no longer a reference to the former, which I can imagine could get expensive if this is done and millions of copies are being made on accident.

I think you're right, but never hurts to take a little extra thinking time, and give myself the weekend to finally play some spelunky 2
Thanks for the tips, I've got to be the only programmer that knows nothing about arrays lol.

I think I'm understanding, so there is another grid storing all of the moves and "depth 0" is the first index of the 1st dimension of that grid?
Is a move an entire 8x8 board grid, or just something representing "piece to e4"?

So almost, but actually only depth 0 moves are stored in that grid, columns being: piece_id, piece_x, piece_y, move_x, move_y, evaluation.
I can and probably should drop the id, which can be found easily with piece_x and piece_y. Then you loop through the moves onto a copy of the 8x8 chess grid, and with each you pass that copy grid into the minimax function. Minimax does a similar thing but instead loops through each piece (of the current colour) and stores the current piece's moves as x and y grid coords into parallel ds_stacks, so stack_x and stack_y. Then you pop from both, perform the move to a copy of the copy 8x8 grid and perform minimax on that. This keeps going, with each nested minimax being a deeper depth.

Once you reach maximum depth you just evaluate the current board position and return the evaluation "score". As each branch finishes and starts returning evaluations, you compare "scores" and return either the min or max (depending on who's turn it is at current depth, white's best moves will be highest score, black's will be lowest). By the end each depth 0 move will have worked out what the best possible score that move can give if both players play their respective best moves at every depth.

Not sure if that helped at all lol, it's a complex algo to explain in words.

 

[tadashibashi]

I think you're right, but never hurts to take a little extra thinking time, and give myself the weekend to finally play some spelunky 2
Thanks for the tips, I've got to be the only programmer that knows nothing about arrays lol.

Haha nice, that's a good reminder to take it easy.
And totally just meant being careful in a positive light. Like in a "I trust you're definitely making intentional decisions" kind of way.

So almost, but actually only depth 0 moves are stored in that grid, columns being: piece_id, piece_x, piece_y, move_x, move_y, evaluation.
I can and probably should drop the id, which can be found easily with piece_x and piece_y. Then you loop through the moves onto a copy of the 8x8 chess grid, and with each you pass that copy grid into the minimax function. Minimax does a similar thing but instead loops through each piece (of the current colour) and stores the current piece's moves as x and y grid coords into parallel ds_stacks, so stack_x and stack_y. Then you pop from both, perform the move to a copy of the copy 8x8 grid and perform minimax on that. This keeps going, with each nested minimax being a deeper depth.

Once you reach maximum depth you just evaluate the current board position and return the evaluation "score". As each branch finishes and starts returning evaluations, you compare "scores" and return either the min or max (depending on who's turn it is at current depth, white's best moves will be highest score, black's will be lowest). By the end each depth 0 move will have worked out what the best possible score that move can give if both players play their respective best moves at every depth.

Not sure if that helped at all lol, it's a complex algo to explain in words.

Thanks for the explanation, I'm kind of slow so I'd probably have to study the code to understand better, but it sounds like a lot of recursion. I'd love to see it in action once it's working.

 

[Jam373]

Okay so today I started working on this thing though I must admit I didn't get very far. I opted to try BOTH methods, for the learning experience and to compare performance. However I hit a stumbling block pretty quick. Taking @tadashibashi's advice I tried to object pool a million structs in a loading screen at the start of the game. I tried using both a ds_stack and a 1d array but gamemaker hated doing both. The 1 mill length array took a good min or 2 to create (I should have realised that wouldn't work) and the stack got progressively slower at adding the structs in 10k chunks. I'm assuming this is just me misunderstanding the optimal way of doing this. Should I instead make say 100 smaller stacks (10k structs in each) and put them in an array? Then you'd keep track of which stack was the currently half-filled one to be filled/unfilled.

Anyway this made me think my method is probably horrendous performance wise if it struggles even in the loading screen. But I think I will still want to do some object pooling with @FrostyCat's 1D array's.

So @FrostyCat, I humbly beg your forgiveness for ever doubting the tautological necessity of your advice . I have learnt/relearnt some binary and bitwise basics and think I'm ready to give it a go. I do however have some questions. Unfortunately the twists to my chess game mean that I believe I must store 2 extra bools (for now) in my piece data. So am I right in thinking each piece will be 6 bits instead? And using enums that would be:

enum ROGUE {
    TRUE = 16,
    FALSE = 0
}
enum SPAWN {
    TRUE = 32,
    FALSE = 0
}

and formed with something like SIDE.BLACK | TYPE.KING | ROGUE.FALSE | SPAWN.TRUE ?

Does this change anything else about your method?

 

[Jam373]

Thanks for the explanation, I'm kind of slow so I'd probably have to study the code to understand better, but it sounds like a lot of recursion. I'd love to see it in action once it's working.

No worries, me too and yes recursion was the word I was desperately looking for.

This really helped me visualise both the algo and the code if you're interested. I will be sure to let you know when it's ready, looking forward to hearing opinions! Still up in the air on whether it makes sense design-wise, but that's what's so exciting about prototyping!

 

[tadashibashi]

Okay so today I started working on this thing though I must admit I didn't get very far. I opted to try BOTH methods, for the learning experience and to compare performance. However I hit a stumbling block pretty quick. Taking @tadashibashi's advice I tried to object pool a million structs in a loading screen at the start of the game. I tried using both a ds_stack and a 1d array but gamemaker hated doing both. The 1 mill length array took a good min or 2 to create (I should have realised that wouldn't work) and the stack got progressively slower at adding the structs in 10k chunks. I'm assuming this is just me misunderstanding the optimal way of doing this. Should I instead make say 100 smaller stacks (10k structs in each) and put them in an array? Then you'd keep track of which stack was the currently half-filled one to be filled/unfilled.

Anyway this made me think my method is probably horrendous performance wise if it struggles even in the loading screen. But I think I will still want to do some object pooling with @FrostyCat's 1D array's.

So @FrostyCat, I humbly beg your forgiveness for ever doubting the tautological necessity of your advice . I have learnt/relearnt some binary and bitwise basics and think I'm ready to give it a go. I do however have some questions. Unfortunately the twists to my chess game mean that I believe I must store 2 extra bools (for now) in my piece data. So am I right in thinking each piece will be 6 bits instead? And using enums that would be:

enum ROGUE {
    TRUE = 16,
    FALSE = 0
}
enum SPAWN {
    TRUE = 32,
    FALSE = 0
}

and formed with something like SIDE.BLACK | TYPE.KING | ROGUE.FALSE | SPAWN.TRUE ?

Does this change anything else about your method?

Hmm, maybe stacks aren't optimized to be that big...

If you're using an array for the pool can you preallocate/initialize the array with something like:
pool = array_create(10000000);

then populate it with the arrays/ds/structs that you're using? (if you're not already)
This would prevent the array from needing to reallocate every so often, which is probably auto copying all the data and moving it elsewhere when it gets full. Maybe if there's an optimal limit for stacks you could try managing a stack of stacks? Arrays are sounding like a better option now though.

Using an array you'll probably need to use id's for the pool items to know which location it belongs to, and a singly linked list to point to the next free which is going to take some extra space. I wish I could find the blog article that shows this implementation but I'm a bit busy at the moment.

 

[Jam373]

Hmm, maybe stacks aren't optimized to be that big...

If you're using an array for the pool can you preallocate/initialize the array with something like:
pool = array_create(10000000);

So that IS what I'm doing with arrays already, but I actually misunderstood the problem. I thought the 1-2 mins were a result of array_create(1000000); but actually that's instant, it just hates creating/storing structs in the array, many seconds for each thousand. Doing the same in a ds_stack is far quicker for the first half of the process (10 thousand every few frames) but gets quite slow later (not as bad as the array though). So not sure if its a "structs in arrays" optimisation issue or what. Anyway, I'm a bit busy rn too so I'm going to do more tests tomorrow morning, thx for the repy will look into your suggestions.

 

[FrostyCat]

So @FrostyCat, I humbly beg your forgiveness for ever doubting the tautological necessity of your advice . I have learnt/relearnt some binary and bitwise basics and think I'm ready to give it a go. I do however have some questions. Unfortunately the twists to my chess game mean that I believe I must store 2 extra bools (for now) in my piece data. So am I right in thinking each piece will be 6 bits instead? And using enums that would be:

enum ROGUE {
    TRUE = 16,
    FALSE = 0
}
enum SPAWN {
    TRUE = 32,
    FALSE = 0
}

and formed with something like SIDE.BLACK | TYPE.KING | ROGUE.FALSE | SPAWN.TRUE ?

Does this change anything else about your method?

That's exactly how it's done, and since you didn't affect any of the smaller bits, the rest stays intact.

Now, to address some of the other points raised by other responders. In my opinion, they don't know what they're talking about. I know from experience actually implementing MCTS and Minimax in GMS 2.3+ that their advices don't work, in particular pooling everything aggressively and implementing Minimax recursively.

A pool of 1 million is time-wasting and needless. If you do it right, the pool for states only needs to be the size of the Minimax tree's depth, because that's the maximum number that needs to coexist at the same time. That is the amount I used in my implementation.

As for pooling the nodes, don't bother. You will waste more time running synchronous code unhitching the nodes at GML speed, than the time saved from reallocation. The GC will do the same task asynchronously in the background at native speed. The GC is lighter on the OS heap than what most people think, it allocates and deallocates to a runner-managed pool first, and only touches the OS heap as a last-resort for more memory or when the load stays light for a while.

As for implementing the Minimax algorithm straight from definition, I'll tell you it's a bad idea, at least until threading formally makes it into a future version of GM. A naive recursive implementation of Minimax in GML will block the runner, look awful, and run the risk of ANR errors. This is why I used a tick-based, iterative equivalent with an emulated call stack in my implementation of the algorithm.

 

[Jam373]

That's exactly how it's done, and since you didn't affect any of the smaller bits, the rest stays intact.

Now, to address some of the other points raised by other responders. In my opinion, they don't know what they're talking about. I know from experience actually implementing MCTS and Minimax in GMS 2.3+ that their advices don't work, in particular pooling everything aggressively and implementing Minimax recursively.

A pool of 1 million is time-wasting and needless. If you do it right, the pool for states only needs to be the size of the Minimax tree's depth, because that's the maximum number that needs to coexist at the same time. That is the amount I used in my implementation.

As for pooling the nodes, don't bother. You will waste more time running synchronous code unhitching the nodes at GML speed, than the time saved from reallocation. The GC will do the same task asynchronously in the background at native speed. The GC is lighter on the OS heap than what most people think, it allocates and deallocates to a runner-managed pool first, and only touches the OS heap as a last-resort for more memory or when the load stays light for a while.

As for implementing the Minimax algorithm straight from definition, I'll tell you it's a bad idea, at least until threading formally makes it into a future version of GM. A naive recursive implementation of Minimax in GML will block the runner, look awful, and run the risk of ANR errors. This is why I used a tick-based, iterative equivalent with an emulated call stack in my implementation of the algorithm.

This is soo helpful dude, thanks a ton! I did wonder how minimax could perform via step events instead of threading but I'm not smart enough to come up with a gamemaker alternative (my "version" had each depth 0 move branch be done in a new step, so a whopping ~30 steps lol) so I think you just saved me from abandoning my project in the future! It's insanely good of you to share your code, thanks again.

I will take some time to read through and understand your code before I implement it myself. By the way if I ever do release, how would you like me to credit you for this? I read the license but haven't had to do this before. Do I just include the file or do you want more explicit credit in the game or on the itch page or somewhere else?

 

[tadashibashi]

That's exactly how it's done, and since you didn't affect any of the smaller bits, the rest stays intact.

Now, to address some of the other points raised by other responders. In my opinion, they don't know what they're talking about. I know from experience actually implementing MCTS and Minimax in GMS 2.3+ that their advices don't work, in particular pooling everything aggressively and implementing Minimax recursively.

A pool of 1 million is time-wasting and needless. If you do it right, the pool for states only needs to be the size of the Minimax tree's depth, because that's the maximum number that needs to coexist at the same time. That is the amount I used in my implementation.

As for pooling the nodes, don't bother. You will waste more time running synchronous code unhitching the nodes at GML speed, than the time saved from reallocation. The GC will do the same task asynchronously in the background at native speed. The GC is lighter on the OS heap than what most people think, it allocates and deallocates to a runner-managed pool first, and only touches the OS heap as a last-resort for more memory or when the load stays light for a while.

As for implementing the Minimax algorithm straight from definition, I'll tell you it's a bad idea, at least until threading formally makes it into a future version of GM. A naive recursive implementation of Minimax in GML will block the runner, look awful, and run the risk of ANR errors. This is why I used a tick-based, iterative equivalent with an emulated call stack in my implementation of the algorithm.

Thanks for sharing your experience implementing this in Game Maker. It's really interesting to hear about a runner-managed pool. I admit I know nothing of this algorithm, and perhaps could be more careful offering advice, even if just addressing data structures at a surface level. Could you recommend resources to learn more about algorithms?

 

[FrostyCat]

I will take some time to read through and understand your code before I implement it myself. By the way if I ever do release, how would you like me to credit you for this? I read the license but haven't had to do this before. Do I just include the file or do you want more explicit credit in the game or on the itch page or somewhere else?

If you decide to use the Minimax engine I wrote, you can just credit me (Dickson Law) and optionally provide a link to the repository's URL.

Could you recommend resources to learn more about algorithms?

For most algorithms, the Wikipedia article for them is a good starting point, as are most of the top results for them on Google. Though algorithms are supposed to be language-independent, the code samples cited in these resources aren't, so don't expect to get by copy-and-pasting or knowing only GML. You will need to adapt the code.

For general development, data structures and algorithms in first-year computer science are the absolute minimum for proficiency, which you can now obtain from free online courses like this or this. At least half of the questions on the Q&A section have no reason to exist if the people asking them took time to acquire that background first.

 

[tadashibashi]

For most algorithms, the Wikipedia article for them is a good starting point, as are most of the top results for them on Google. Though algorithms are supposed to be language-independent, the code samples cited in these resources aren't, so don't expect to get by copy-and-pasting or knowing only GML. You will need to adapt the code.

For general development, data structures and algorithms in first-year computer science are the absolute minimum for proficiency, which you can now obtain from free online courses like this or this. At least half of the questions on the Q&A section have no reason to exist if the people asking them took time to acquire that background first.

Thank you for the recommendation and links. I'm comfortable with the C languages, having recently finished a university extension certificate in programming, so I think an algorithms deep dive would be a beneficial next step.

 

[Jam373]

@FrostyCat Hey! Quick progress update: I've rewritten all the backend and have finally got a prototype working with random ai and am now in the process of adapting your minimax engine to replace the random one.

I was wondering what you would suggest to overcome the chess issue of moves requiring both starting and ending coords as opposed to just the single coord as reversi has.
My two ideas are either have a piece variable alongside the move and weight variables and give availableMoves an extra row.
Or make the move variable an array containing both the move and piece coord. I have no idea which would be easier or more efficient so thought I'd ask first.

Second quick query regarding weight. I'm not too sure I understand why weight is set to undefined unless polarity is undefined:

var _currentMove, _currentWeight;
if (is_undefined(currentNode.polarity)) {
    _currentMove = availableMoves[currentChildNum][0];
    _currentWeight = availableMoves[currentChildNum][1];
} else {
    _currentMove = availableMoves[currentChildNum];
    _currentWeight = undefined;
}

One such example.

My game will never have polarity undefined as the player will choose their colour. Do I need to adapt anything then to make it work as intended? Why is weight ignored unless the polarity is random (I don't think I understand the purpose of weight at all, I thought it was just info for the progress bar)?

 

[FrostyCat]

I was wondering what you would suggest to overcome the chess issue of moves requiring both starting and ending coords as opposed to just the single coord as reversi has.
My two ideas are either have a piece variable alongside the move and weight variables and give availableMoves an extra row.
Or make the move variable an array containing both the move and piece coord. I have no idea which would be easier or more efficient so thought I'd ask first.

This is a non-issue if you encoded board positions in the single-number form xx+yy*8 (which would be in the range 0-63). Then two positions side by side would then just be fromPos | (toPos << 6), and the positions can be extracted by move & $3F and move >> 6 respectively.

Second quick query regarding weight. I'm not too sure I understand why weight is set to undefined unless polarity is undefined:

var _currentMove, _currentWeight;
if (is_undefined(currentNode.polarity)) {
    _currentMove = availableMoves[currentChildNum][0];
    _currentWeight = availableMoves[currentChildNum][1];
} else {
    _currentMove = availableMoves[currentChildNum];
    _currentWeight = undefined;
}

One such example.

My game will never have polarity undefined as the player will choose their colour. Do I need to adapt anything then to make it work as intended? Why is weight ignored unless the polarity is random (I don't think I understand the purpose of weight at all, I thought it was just info for the progress bar)?

The "weight" here refers to the probability weight of the node if there is randomization involved in the game, not the actual value of the node. Your game's polarity is always defined not because the player gets to choose a colour, but because there is no randomizing agent in Chess. There is no need to adapt anything here.

 

[Jam373]

This is a non-issue if you encoded board positions in the single-number form xx+yy*8 (which would be in the range 0-63). Then two positions side by side would then just be fromPos | (toPos << 6), and the positions can be extracted by move & $3F and move >> 6 respectively.

I did do that, as advised, but in my chess functions I never considered mashing the two sets of coords together like that, makes sense! Thanks! Would it be more efficient to edit my functions to only take and return that single form or should I just combine and split it within the minimax engine to feed into the functions?

The "weight" here refers to the probability weight of the node if there is randomization involved in the game, not the actual value of the node. Your game's polarity is always defined not because the player gets to choose a colour, but because there is no randomizing agent in Chess. There is no need to adapt anything here.

Again, makes total sense now you say it, thanks.

Btw, I had never played reversi before and had a lot of fun playing some games whenever I was on a break!

Edit: final question now I'm nearing the end, you mentioned using gml_pragma("forceinline") but there isn't much info on it online. How can I tell if a function would benefit from this?

 

[FrostyCat]

Would it be more efficient to edit my functions to only take and return that single form or should I just combine and split it within the minimax engine to feed into the functions?

You just have to make sure that the getMoves(), isLegal(move) and applyMove(move) methods of the main state class all work with that single-package form. However you do that is up to you. In the Reversi example, the single-package move form is regularly unpacked back into X and Y positions.

Edit: final question now I'm nearing the end, you mentioned using gml_pragma("forceinline") but there isn't much info on it online. How can I tell if a function would benefit from this?

See: Inline expansion

In GML, very short global functions that get used a lot tend to benefit the most from inlining.

 

[Jam373]

I'd love to see it in action once it's working.

Well it's finally out there: https://forum.yoyogames.com/index.php?threads/total-zugzwang.85635/