▲ 230 points

Show HN: Sameshi – a ~1200 Elo chess engine that fits within 2KB

github.com

by datavorous_·6mo ago·69 comments·view on hn ↗

I made a chess engine today, and made it fit within 2KB. I used a variant of MinMax called Negamax, with alpha beta pruning. For the board representation I have used a 120-cell "mailbox". I managed to squeeze in checkmate/stalemate in there, after trimming out some edge cases.

I am a great fan of demoscene (computer art subculture) since middle school, and hence it was a ritual i had to perform.

For estimating the Elo, I measured 240 automated games against Stockfish Elo levels (1320 to 1600) under fixed depth-5 and some constrained rules, using equal color distribution.

Then converted pooled win/draw/loss scores to Elo through some standard logistic formula with binomial 95% confidence interval.

69 comments

This is very cool and having stalemate is nice, however how much space would it take to implement the full ruleset?

As you write: not implemented: castling, en passant, promotion, repetition, 50-move rule - those are all required to call the game being played modern chess.

I could see an argument for skipping repetition and 50-move rule for tiny engines, but you do need castling, en pessant and promotion for pretty much any serious play.

https://en.wikipedia.org/wiki/Video_Chess fit in 4k and supported fuller ruleset in 1980 did it not?

So I would ask what is the smallest fully UCI (https://www.chessprogramming.org/UCI) compliant engine available currently?

This would be a fun goal to beat - make something tiny that supports full ruleset.

PS my first chess computer in early 1980s was this: https://www.ismenio.com/chess_fidelity_cc3.html - it also supported castling, en pessant, not sure about 50 move rule.

ToledoChess [0] has a few implementations of this in different languages. Some highlights:

2KB of JavaScript with castling, en passant, promotion, search and even a GUI

326 bytes of assembly, without the special rules

I don't think the author has a UCI-compliant one, but it should be easier than the GUI. There are forks of the JS one that might do it.

[0] https://nanochess.org/chess6.html

Cool project. You could also use the front-end of GNU chess to save some lines, and implement only a back-end.

Bug report:

    a b c d e f g h
  8 r n b q k b n r 8
  7 . . p p p p p p 7
  6 . p . . . . . . 6
  5 p . . . . . . . 5
  4 P . . P P . . . 4
  3 . . . . . . . . 3
  2 . P P . . P P P 2
  1 R N B Q K B N R 1
    a b c d e f g h
  move: b2b3
  ai: b6b4

The pawn is not permitted to move two fields after it has already beeen moved once before: b6b4 isn't a valid move after b7b6. (First moving two fields, and then one would have been okay, in contrast.)

Thanks for pointing it out! I will try to patch it.

Appreciate you taking the time to test it.

If anyone is curious, the most common tool I've seen for ELO estimation among engine developers is cutechess [1], which uses SPRT [2]. Or ordo [3], haven't used this myself though

[1] https://cutechess.com/

[2] https://www.chessprogramming.org/Sequential_Probability_Rati...

[3] https://github.com/michiguel/Ordo

Do you think it would be possible to achieve 1:1 ELO:bytes? Even smaller, but can be less smart.

That's an awesome code golf challenge

maybe for very low ratings it's plausible? 1 elo per byte might happen in a tiny range but at a useful strength it would break fast, that's what i think

What's the snallest possible program that accepts a chess board state and prints any legal move? True randomness may only have a couple hundred ELO, but then, that's pretty big for golf

Cool! I just recently implemented a chess engine in ~400 (readable) lines, with all rules, first in Java and then ported to my own programming language "Bau" [1]. This is including a terminal UI. I'll measure the ELO, but I was never able to beat it :-) The castling moves are specially tricky to implement I think. I enjoyed the challenge as well.

[1] https://github.com/thomasmueller/bau-lang/blob/main/src/test...

How come there's no unsigned numeric types in Bau?

I tried to describe this in [1]: "Unsigned integer are intentionally not supported to simplify learning and using the language, to avoid surprising behavior and edge cases, and to reduce security issues and error-handling pitfalls. When needed, unsigned behavior is available through explicit operations. This design does not affect performance or memory usage."

I understand this may not sound very convincing yet... it is hard to describe... basically, unsigned types sound simple, but they are not.

[1] https://thomasmueller.github.io/bau-lang/features.html

https://www.chessprogramming.org/Toledo is a family a moderately strong tiny chess programs.

How many games did you have to throw away because stockfish wanted to castle? Or did you force stockfish to not castle? Castling seems like such a frequent move it is hard to draw any conclusions about the strength of an engine that does not support it.

zero games were thrown away for castling, because i forced stockfish not to castle (and not to play en passant/promotion) by filtering legal moves and only giving those filtered moves via root_moves

so every game stayed in the same no castling variant

and you're right, this rating is for that constrained variant, not full chess.

Wouldn't stockfish's position evaluation be incorrect in that case? (If it evaluated the position based on a formula that assumed normal rules)

Wouldn't that just stop it from considering castling, en passant, and promotion on the first move of the position you are analyzing? It's still going to consider those in the tree search, and the static evaluation neural net was trained on positions where they are allowed.

For castling you should be able to fix this by specifying that castling rights have been lost in the positions you give it.

For the others I think you would need to filter not just when giving it the list of allowed first moves. You'd also have to make it not consider en passant and promotion in the search, by modifying its move generation.

The static evaluation would still be off a bit, but that probably would not have much effect most of the time.

From what I've read it is feasible to train a new neural net on a decent home computer in maybe around a week, but that's probably overkill for your use of figuring out how strong your engine is at no castling/no promotion/no en passant chess.

This is not chess, but something that allows to move chess pieces.

> Not implemented: castling, en passant, promotion, repetition, 50-move rule.

I have been into computer chess for many years and I was fully expecting those concessionary statements. I have seen enough programs in this lucrative genre where a lot of attention can be gained by fraudulently claiming you implemented chess in a seemingly impossibly small size. When confronted, the charlatans will often claim senselessly that those omissions were in fact superfluous. This is a behaviour I have unfortunately also observed in other areas of computing.

If anyone reading this is interested in small and efficient chess programs that are still reasonably strong, there was a x86 assembly port of Stockfish called asmFish from a couple of years ago (the Win64 release binary was about 130KiB). Also see OliThink (~1000 LOC) and Xiphos which has some of the simplest C code for an engine of its strength that I have seen. I have not investigated the supposedly 4K sized engines that participated in TCEC too closely but from what I have seen so far it would seem that there are a few asterisks to be attached to those claims.

Cool that you could keep it under 2k but it would nice to have a readable version of the source code.

Do you work with it like this or do you have some sort of script you apply to get it down to a single line, single letter variable names?

a readable version seems to have just been added! https://github.com/datavorous/sameshi/tree/master/readable

What you’re describing is the typical output / function of a minifier

The real fun would be reverse-engineering the minified code (there are loads of tools to do this for chrome extensions)

How did you handle games where Stockfish would castle or promote?

i forced stockfish to play only non castling, non en passant, non promotion moves by filtering legal moves and passing only those as root_moves

also removed castling/EP rights from FEN

Very cool! I’ve added this to the HN Arcade https://hnarcade.com/games/games/sameshi

Nice initiative! Was hoping the "play" button/link would go to a playable version though

Good job! I love how you obfuscated your code, really in a spirit of FOSS!

Oh well, the file initially looked like https://github.com/datavorous/sameshi/blob/7ab4e47144f96becd...

It is hideous now!

Coworker: “hey if you have a second, I have a one-liner PR open”

The PR:

You might have misunderstood the purpose of this.

it’s minification, not obfuscation. the whole point of the engine is its small footprint

So small it fits on a gameboy https://github.com/odrevet/sameshi-gbdk

need to start measuring these things in the size of compiled functions so we can stop looking at oneliners (maybe wasm since it has an easy to read text representation)

This is amazing! Thanks for sharing. What would be the elo gain for 4KB engine?

P.S. I assume 1200 elo in chess com scale (not lichess / fide elo) and bullet chess variant?

There is a TCEC category for 4k engines. The top ones are ~3000 Elo.

Oh my god the source is so tiny! It's really hard to parse because of it being minified but I love it to bits.

I wonder how big 1300, 1400, ..., 2200 Elo chess engines are.

If you ever spent much time at a chess club, you've seen why 2kB is a really disturbing number.

I have not. Can you please tell me why?

Codex or Claude Code?

none.

scribbling long enough on a piece of paper is more enjoyable than prompting.

Isn't it bad enough they beat us at chess, do you have to make it even worse? ;p