ArduChess - Play chess on the Arduboy

Github. There are probably some bugs as I haven’t tested it that thoroughly.

arduchess.hex

ScreenRecording

17 Likes

WOW man this is such a great thing, I’ve been working on my own small chess engine that I wanted to run on Arduboy and other devices, but you were faster here.

This is an amazing job considering this has such details as the 50 move rule, especially the AI is very impressive when it has opening books etc. The graphics is great too.

Please tell me, did you write the AI yourself?

One feature I was planning was chess puzzles generated by AI, i.e. generate random position, let the AI compute the best move and then the player’s goal is to find the move. Just if you wanted to improve this further.

AI looks pretty advanced with the square tables etc., I just can’t see any pruning – are you doing at least alpha-beta? I guess so as you even do move ordering.

5 Likes

Thanks for the nice comment. I did write the engine myself, with the Arduboy’s limitations in mind. Threefold repetition detection was definitely the hardest rule to implement both efficiently (so AI could know about it within search) and within RAM limitations – it requires storing up to the last 100 positions (due to 50 move rule).

You’re right – alpha-beta is the only pruning currently. I have a framework in place for measuring the ELO impact of changes to the engine by setting competitions of >10k games with previous versions. However, I haven’t been able to get any pruning or reductions/extensions to make significant ELO increases. I suspect it’s difficult to apply pruning effectively at the shallow depths the engine searches, but I plan to continue investigating ways to improve search.

I had originally wanted to include puzzles, too, though probably hardcoded in a book of a few hundred pre-made puzzles instead of dynamically generated. But I ran out of program space – right now there’s only a hundred or so bytes left – so size optimization will be another area of improvement.

2 Likes

I think it would be great if you abstracted your AI from Arduboy/Arduino and made it a general small engine supporting XBoard or UCI so that you can play automated tournaments and measure the ELO against existing engines – that’s what I am doing with my engine, I want it to be a tiny engine that can run anywhere.

Your engine is definitely more advanced than mine, I don’t implement the 50 move rule or threefold repetition (at least at the moment), but I do have en-passant etc. I don’t even order the moves, but I still do alpha-beta as it’s pretty simple and reduces the number of searched positions to about a half (will be better with move ordering). Also my evaluation function is much simpler. And my AI always promotes to queen as there are only rare cases of underpromotion being better. I want my engine to be super KISS.

Pruning won’t increase ELO, it will just speed it up, right? The issue I am facing now with my engine is the horizon problem – I need to implement extensions so that the AI searches deeper in certain situations, e.g. when trading pieces. Do you have anything like that?

Also, do you play chess yourself? :slight_smile:

2 Likes

These are good thoughts. A UCI frontend would be good to do eventually. Right now the engine part is abstracted enough to compile separately (to x86/x64) for self play competitions in my own framework. I chose to do it that way because the search settings are low to match those used on the Arduboy that it’s much faster to have two versions of the engine in the same executable playing each other (which allows each game to finish in much less than a second) instead of the overhead of two executables arbitrated by a protocol.

You’re right that pruning wouldn’t affect ELO in a depth limited search but the difficulty levels in ArduChess represent node/eval limits rather than depth limits (I wanted the thinking time to be more or less consistent), so search optimizations could allow deeper search.

ArduChess performs a quiescence search at leaf nodes to try to evaluate only quiet positions and avoid horizon problems. Right now only captures are explored – I tried adding checks and check evasions but was unable to improve ELO (given the node-limited search).

I do play chess at a very casual level, but not too often nowadays – no idea what my rating might be but probably not that great.

1 Like

Thanks for that info, I’ll have to implement detection of quiet positions too.

It’s pretty impressive you even have your own testing framework, it’s definitely a bit faster as a single executable but the protocols would allow you to work within established tools and infer a kind of objective ELO, i.e. you could say this beats stockfish x times out of 1000 games, now you only know if you’ve improved against older versions. I’d like to know how strong this really is. Anyway, letting engines play against each other is a lot of fun.

I’ll be looking forward to your potential work on this in the future!

BTW here is an interesting video about weird chess algorithms, just for fun, if anyone is interested :slight_smile:

1 Like

Chess is one of the few games my dad and I played together. It’s been a while since I’ve touched it, so this is really hitting the spot. Good work!

3 Likes

This is amazing! I love chess but the problem is that everyone I know is always busy and cannot play, great job!

3 Likes

Great job on this one. It may be my favourite :slight_smile:

It wasn’t working on my SH1106 screen due to the custom half-screen rendering, but I was determined to get this going and managed to figure it out.

Happy to post a forked repo if it helps anyone else.

2 Likes

@brow1067 Have you considered using the new FX functionality for the puzzles? You could save them all on the flash storage, assuming you’re able to free up enough bytes to add the UI logic.

Kind of how the author of Lode Runner FX is able to store all the levels there and just fetch them when needed.

Perhaps even the opening book could be stored there either fully or as an expansion if there were a way to only retrieve the applicable lines (though I’m really not too sure how they work so perhaps that makes no sense).

1 Like

@brow1067 if you want to add this functionality, I can help with FX integration. Its really actually quite easy!

2 Likes

@clintonium-119 Thanks for the nice words. Puzzles on the flash chip is a really good idea! I don’t have an FX but that will probably convince me to order one. A size optimization pass is long overdue anyway to make room for a puzzle UI… I’m sure there’s something to improve. There’s also the fancy title screen eating up a bunch that could be substituted for something simpler.

@filmote Thanks! Is this repo a good reference to get started? I guess the process for packaging prog+FX content together and then uploading is probably different too…

1 Like

That is defintely the place to start. However, I can give you a hand to get started and allow you to bypass the learning process.

I am assuming that the data will be pretty straight forward and a regular size (64 bytes for the board and a couple of extra bytes to describe who’s turn it is and so forth. This will make the integration super easy.

No problem, you can develop and test your game using the online ProjetABE instance. Just drag your hex and the bin file (your new levels) onto it and get going!

It’s a cool title screen. You could probably find a way to offload that to the FX chip as well and only pull it down while needed. If both that, and the opening book (since they will never both be needed at the same time) were stored on the flash memory, I’d think that you’d free up enough space to add the UI logic for the puzzles, and keep the big, beautiful image.

I’m excited to see what sort of things people come up with for the FX. It will open up a bunch of cool possibilities. I’d like to take a stab at a game myself at some point this year (once I get a few other projects behind me), and this really has my wheels turning.