I made a chess game on Roblox with React frontend, roblox-ts, and a bot made in Luau.
Specs:
~8,108,679 NPS in Perft testing (singlethreaded, native luau) ~525,000 PPS, Depth 6-10 and 11 plys can be achieved in ~500ms singlethreaded.
The bot is a minimax algorithm with:
alpha-beta-pruning
transpositions
bitboards (dedicated lo & hi variabled)
late move reductions
aspiration windows
futility pruning
null move pruning
quiescence search
iterative deepening
magic bitboards (dedicated trainer in C++ for 32bit keys)
parallel luau (analyze multiple branches at once)
incremental PST evaluation
encoding of boards into buffers to pass across threads.
incremental attack generation
incremental 32bit Zobrist Hashing (much faster than using 64bit ints in this case)
tons of int-packing, example: castle status, move information are all represented as a single integer.
The bitboards allow for tricks such as computing all the knight attacks all with a couple bit operations, and even computing sliding piece movements without loops.
Game:
NOTE: Both of these are not the latest version.
This will be opensourced soon, alongside documentation explaining all of the optimizations.
In depth 5, the latest version of this engine can generate 1,131,344 nodes in a single thread .
This is with a couple of insane optimizations such as counting how many checkers the king has, and if it is >= 2 then no need to bother adding moves which can have pieces block checks.
The perft data is from a single-threaded test with --profile in Luau CLI, with --code-gen on.
In the Roblox Game the performance (with Parallel Luau) is:
Depth 3: 6ms
Depth 4: 44ms
Depth 5: 544ms
Insane considering Depth 4 used to take ~100ms, and before that ~300ms. Depth 5 used to have moves taking 1-3 seconds.
64bit integers represented as lo & hi halves, not using a library. This allows for bit32 calls to become inlined by Native Luau.
support for Magic Bitboards, but since 64bit int multiplication is expensive this uses a optimization, this also means that off-the-shelf magic numbers cannot be used anymore since collisions are so much more likely. I created a dedicated C++ magic number trainer for this.
Arrays of bitboards used to be {[number]: number, all: number}, with a dedicated index for all this can all be represented as a single integer array rather than a dictionary (using hash functions).
Incremental hashing & evaluation that doesnt hash/eval on leaf nodes but rather make small changes every node.
Once the perft values are perfected, this will be opensourced. In minimax many search optimizations have been added so it can reach a depth of 6-7 and 10-15 plys.
With many, many fixes the perft node count is now perfect up to depth 6. (Every possible position from 6 moves are value), cross compared with: Perft Results - Chessprogramming wiki.
I am currently running depth 7 which will check 3 billion positions.
Holy, that’s fast. I’ll really be looking forward to reading the code, as though I don’t play chess, I love to see clever usages of roblox! Also, documentation = chefs kiss.
I should really try messing around with parallel luau more, I think it’ll help with my projects a lot.
Originally I was thinking full game, but I have gotten busy. Maybe once I open source it I can consider a closed source version with a full elo system and everything.
.