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

How to build a chess engine

chessengines.org

Post reply on HN
Print view View original

21–30 of 58 posts

Re: How to build a chess engine

#21

Post by dmurray »

infogulch wrote: post #17

What is the most compact representation for a complete chess game state? Can it be as low as 64 bits?

I don't agree with the reasoning in either of the other two answers you've been given, but Shannon (1950) gave the number of chess positions as somewhere around 10^43, so 150+ bits. The position accounts for almost all of the state.

You could do better with variable-length encodings and perhaps represent all "interesting" "plausible" positions in 64 bits, but as others said, compactness is really not a top priority in representations for chess engines, it's much more important to be able to query and update the representation.

Re: How to build a chess engine

#22

Post by tr1ll10nb1ll »

franciscop wrote: post #2

By "chess engine" the author refers to the AI/Machine Player, not the base of how to position the pieces, valid moves, turn taking, etc. which is what I thought "engine" would mean here (my thought was similar to a game engine vs AI/characters). For the "game engine" they're importing Chess.js. Totally fine, just a heads up since I did expect to see a truly from-0 since it says "how to build a Chess engine from scrat…

They are not hijacking anything, imo. They are simply using Notion.so to power the website. It's a note-taking app and this is the regular behavior of Notion. Nothing out of the ordinary.

Down key makes you navigate "blocks". Space key doesn't do anything since you're not typing in Notion.

There's a way for the OP to get around this behavior and make their website act more like a blog.

That would require SSR on Notion pages instead of a cloudflare worker script on their public Notion site which they appear to be doing currently.

Re: How to build a chess engine

#23

Post by Jabbles »

mtlmtlmtlmtl wrote: post #11

I recommend anyone who's interested in this topic, or in data structures and optimisation, to pick apart Stockfish' transposition table implementation[0,1]. It's essentially a highly customised hash table. It has to handle multiple threads reading and replacing entries, with no locking. It can't grow dynamically, and so it has to "age out" entries. Think of it like hash table implementation with the difficulty set to…

> It has to handle multiple threads reading and replacing entries, with no locking.

Is this undefined behavior or does the memory model of C++ guarantee anything given the reads/writes are presumably whole words?

I realise that the implementation doesn't actually have to be deterministic, but does the language guarantee anything in these cases?

Re: How to build a chess engine

#24

Post by shmageggy »

infogulch wrote: post #17

What is the most compact representation for a complete chess game state? Can it be as low as 64 bits?

Having nerded out on this question in the past, I found that Wikipedia had one of the better discussions, with a Huffman encoding scheme that seemed like it should be near optimal. Someone has since deleted it but it can be found in the history

https://en.m.wikipedia.org/wiki/Special:Diff/916225714

Re: How to build a chess engine

#25

Post by megapoliss »

bmacho wrote: post #20
franciscop wrote: post #2

By "chess engine" the author refers to the AI/Machine Player, not the base of how to position the pieces, valid moves, turn taking, etc. which is what I thought "engine" would mean here (my thought was similar to a game engine vs AI/characters). For the "game engine" they're importing Chess.js. Totally fine, just a heads up since I did expect to see a truly from-0 since it says "how to build a Chess engine from scrat…

> Unless in the Chess industry the "chess engine" refers to the machine player, which I do not know. "Chess engine" definitely means[0] what is the article about (I won't even repeat your words for it). chess.js[1], ffish.js[2] or such are called chess libraries. There is no ambiguity or confusion in these terms. If you happen to have one, pls update your terms, and don't bring it up again (so it can stay this way).…

Rough, Chess engine = Interface protocol (like UCI) + Move Generator + Evaluation Function. Article talks about evaluation function only (since it reuse move generator and interface).

Re: How to build a chess engine

#26

Post by qwery »

franciscop wrote: post #2

By "chess engine" the author refers to the AI/Machine Player, not the base of how to position the pieces, valid moves, turn taking, etc. which is what I thought "engine" would mean here (my thought was similar to a game engine vs AI/characters). For the "game engine" they're importing Chess.js. Totally fine, just a heads up since I did expect to see a truly from-0 since it says "how to build a Chess engine from scrat…

FWIW I think that without having encountered the term ('chess engine') before, connecting chess ~ game and so chess engine ~> chess game engine is a pretty reasonable path to take in interpreting unfamiliar jargon.

Re: How to build a chess engine

#27

Post by mtlmtlmtlmtl »

Jabbles wrote: post #23
mtlmtlmtlmtl wrote: post #11

I recommend anyone who's interested in this topic, or in data structures and optimisation, to pick apart Stockfish' transposition table implementation[0,1]. It's essentially a highly customised hash table. It has to handle multiple threads reading and replacing entries, with no locking. It can't grow dynamically, and so it has to "age out" entries. Think of it like hash table implementation with the difficulty set to…

> It has to handle multiple threads reading and replacing entries, with no locking. Is this undefined behavior or does the memory model of C++ guarantee anything given the reads/writes are presumably whole words? I realise that the implementation doesn't actually have to be deterministic, but does the language guarantee anything in these cases?

This implementation isn't actually race free per-se. It can happen that reads and writes overlap resulting in bad entries, but they are generally rare, since Stockfish utilises various heuristics to ensure that different threads are searching non-overlapping parts of the search tree most of the time. Erroneous information at a single node doesn't usually have a huge effect since ultimately the best move is chosen through a vote between the different threads. So it sort of cheats by avoiding most races and collisions, and then having ways of spotting bad entries, ignoring and overwriting them.

This is all a bit hand-wavey, but there you have it. You could do this with atomics by shaving down the size of an entry to 64 bits(Stockfish uses 10 bytes), I suppose.

Re: How to build a chess engine

#28

Post by Sesse__ »

dmurray wrote: post #21
infogulch wrote: post #17

What is the most compact representation for a complete chess game state? Can it be as low as 64 bits?

I don't agree with the reasoning in either of the other two answers you've been given, but Shannon (1950) gave the number of chess positions as somewhere around 10^43, so 150+ bits. The position accounts for almost all of the state. You could do better with variable-length encodings and perhaps represent all "interesting" "plausible" positions in 64 bits, but as others said, compactness is really not a top priority i…

Shannon's estimate was based on very primitive methods; by generating random positions and using fairly advanced methods to see whether they are legal or not (ie., can you construct a proof game for it, or prove that it could never happen), you will get much closer. A group of people have been working on this, and their current best estimate is (4.822 +- 0.028) * 10^44, or a bit over 148 bits. (Amazingly enough, Shannon wasn't all that far off on this account! His estimated number of legal games seems much more dodgy, though.)

http://talkchess.com/forum3/viewtopic.php?f=7&t=77685&sid=e3...

Practically speaking, https://github.com/tromp/ChessPositionRanking gives a number between 0 and approx. 8.7 * 10^45 for any legal position, so it's only a couple of bits away from optimality.

Re: How to build a chess engine

#29

Post by orlp »

nphard85 wrote: post #15

chessprogramming.org is a treasure trove of knowledge on building chess engines. With its help, I wrote one in C++ a few years ago that got quite good (2100+ rating on FICS but that's nowhere close to the likes of Stockfish). In fact, writing a reasonably strong chess engine is straightforward (and incredibly fun) but at the top end of strength, there's immense depth, and after a point making improvements gets increa…

> running experiments to verify strength gain all takes a lot of compute

Fun fact, in my master thesis I proved that quantum computers can verify this using quadratically fewer iterations than on a classical computer. That is, if it takes a classical computer c*n iterations to say with 99% certainty that agent A is stronger than agent B, a quantum computer can do it in d*sqrt(n) iterations, where c and d are agent-independent constants (obviously n is not agent-independent as two closely matched agents are harder to distinguish than a steamroll).

The number of qubits needed put this into the far future of quantum computing, but it's neat nonetheless.

Re: How to build a chess engine

#30

Post by franciscop »

tr1ll10nb1ll wrote: post #22
franciscop wrote: post #2

By "chess engine" the author refers to the AI/Machine Player, not the base of how to position the pieces, valid moves, turn taking, etc. which is what I thought "engine" would mean here (my thought was similar to a game engine vs AI/characters). For the "game engine" they're importing Chess.js. Totally fine, just a heads up since I did expect to see a truly from-0 since it says "how to build a Chess engine from scrat…

They are not hijacking anything, imo. They are simply using Notion.so to power the website. It's a note-taking app and this is the regular behavior of Notion. Nothing out of the ordinary. Down key makes you navigate "blocks". Space key doesn't do anything since you're not typing in Notion. There's a way for the OP to get around this behavior and make their website act more like a blog. That would require SSR on Notio…

Well, Notion is hijacking it then, but the difference as a reader is irrelevant, the point is that I cannot press neither space nor down to scroll down (if you scroll manually then press down, it'll jump to the "highlighted" paragraph, no scroll down).
Post reply on HN