Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

21–30 of 78 posts

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

#21

Post by vunderba »

sigmoid10 wrote: post #16
grumpopotamus wrote: post #14

Earlier quoted context omitted.

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

It's wild to think that 4096 bytes are sufficient to play chess on a level beyond anything humans ever achieved. Makes you think what other difficult tasks are out there that take even highly gifted humans years or decades to master, but a superior algorithm would more or less fit into one of those big QR code formats. These things always make me think back to Westworld season 2, where the finale revealed that human…

Well, one of the most fundamental algorithms for building a chess AI is minimax [1] (or variants like negamax), and that’s been around for close to a century. The key difference is that as compute power and available RAM have grown, it’s become possible to search much deeper and evaluate far more plies.

So while 4k is still very impressive for the code base, it comes with a significantly larger runtime footprint.

[1] - https://en.wikipedia.org/wiki/Minimax

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

#22

Post by sigmoid10 »

kevmo314 wrote: post #18
sigmoid10 wrote: post #16

Earlier quoted context omitted.

It's wild to think that 4096 bytes are sufficient to play chess on a level beyond anything humans ever achieved. Makes you think what other difficult tasks are out there that take even highly gifted humans years or decades to master, but a superior algorithm would more or less fit into one of those big QR code formats. These things always make me think back to Westworld season 2, where the finale revealed that human…

The core search algorithm is very simple though. 4KB engines may not run that fast if they do exhaustive search, but they’ll be quite accurate. According to TCEC the time control is 30 mins + 3 sec, that’s a lot of compute!

If you look at the current winner [1], it does a lot more than just brute force tree search. The space state for chess is simply too big to cover without good heuristics. Deep Blue may have been a pure brute force approach to beat Kasparov after Deep Thought failed using the same core algorithm, but modern chess engines search far deeper on the tree with far fewer nodes than Deep Blue ever could thanks to better heuristics.

[1] https://github.com/MinusKelvin/ice4

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

#26

Post by iterance »

datavorous_ wrote: post #10
lekevicius wrote: post #6

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

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

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

#27

Post by kevmo314 »

sigmoid10 wrote: post #22
kevmo314 wrote: post #18

Earlier quoted context omitted.

The core search algorithm is very simple though. 4KB engines may not run that fast if they do exhaustive search, but they’ll be quite accurate. According to TCEC the time control is 30 mins + 3 sec, that’s a lot of compute!

If you look at the current winner [1], it does a lot more than just brute force tree search. The space state for chess is simply too big to cover without good heuristics. Deep Blue may have been a pure brute force approach to beat Kasparov after Deep Thought failed using the same core algorithm, but modern chess engines search far deeper on the tree with far fewer nodes than Deep Blue ever could thanks to better heur…

I'm not suggesting that it's only brute force tree search, just that it's not very complicated to develop a theoretically perfect chess engine in direct response to the parent

> It's wild to think that 4096 bytes are sufficient to play chess on a level beyond anything humans ever achieved.

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

#29

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

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

#30

Post by datavorous_ »

jll29 wrote: post #29

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 be…

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

Appreciate you taking the time to test it.

Post reply on HN