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

[datavorous_]

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.

[sireat]

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.

[dmurray]

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

[jll29]

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.)

[datavorous_]

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

Appreciate you taking the time to test it.

[l674]

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

[lekevicius]

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

[esafak]

That's an awesome code golf challenge

[datavorous_]

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

[thomasmg]

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...

[ycombinatrix]

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

[tromp]

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

[dfc]

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.

[datavorous_]

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.

[galkk]

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

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

[Mr_Minderbinder]

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.

[chvid]

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?

[mackeye]

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

[noutella]

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

[alansaber]

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

[GeertB]

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

[datavorous_]

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

[yuppiepuppie]

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

[Aachen]

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

[burstw0w]

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

[datavorous_]

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

It is hideous now!

[y-curious]

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

The PR:

[recursive]

You might have misunderstood the purpose of this.

[bstsb]

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

[drev]

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

[kachapopopow]

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)

[haute_cuisine]

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?

[grumpopotamus]

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

[falsaberN1]

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.

[dxxvi]

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

[oh_my_goodness]

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

[jqr-]

I have not. Can you please tell me why?

[newzino]

The mailbox board representation is a good call for size-constrained engines. Bitboards give faster move generation but the manipulation code (shifts, masks, magic numbers for sliding pieces) eats a lot of bytes. With mailbox you just need offset tables and a sentinel check for board edges. Curious what your evaluation function looks like though. At 2KB you can't fit piece-square tables (that's 384 values minimum for both colors), so are you doing material-only eval or did you squeeze in some positional heuristics?

The gap between your 1200 Elo in 2KB and the TCEC 4K engines at ~3000 Elo is interesting. That extra 2KB buys a lot when it goes to better evaluation and move ordering. Even a simple captures-first sort in alpha-beta pruning costs only a few bytes of code but can roughly double your effective search depth.

[TZubiri]

Codex or Claude Code?

[datavorous_]

none.

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

[lyu07282]

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