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

51–58 of 58 posts

Re: How to build a chess engine

#51

Post by krsrhe »

Jaruzel wrote: post #35

One day I'd like to write a rubbish Chess Engine purely for personal use, so that I can play chess against the computer and actually have a good probability of winning, instead of getting thrashed even on the 'easy' setting. The way my brain works, the act of writing the engine would probably also level up my chess playing skills as a side benefit.

Rubbish chess engines aren’t fun. MacOS has one built in.

Try CrazyBishop / TheChess / Chess Lvl.100

Or chess.com leveled bots, or play with handicap, Or play humans online! Infinite supply of beatable opponents.

Re: How to build a chess engine

#52

Post by iamevn »

infogulch wrote: post #17

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

Heres a few naive options to get a ballpark idea:

A) fixed list of piece coordinates: 32 pieces × (3 bits for row + 3 bits for column + 1 bit for whether it's alive) = 224 bits

B) list of live pieces: (3 bit row + 3 bit column + 1 bit for color + 3 bits for which piece) × up to 32 pieces = up to 320 bits

C) 8x8 array of the board: 64 squares × (1 bit for color + 3 bits for which piece) = 256 bits

Then there's the gamestate that isn't directly visible on the board:

- whose turn it is: 1 bit.

- castling rights: A needs 2 bits. B and C can pack it in with the 3 bits for pieces. there's 6 pieces so there's room for two more, one of which is a rook that's eligible to castle with.

- en passant: A needs a flag for each pawn so 16 bits. B and C can also pack in with the other spare piece being a pawn that just advanced two spaces.

- promotion: B and C get it free. A needs another 3 bits per pawn to indicate if and what it's promoted to (so 48 bits max)

- 50 moves without capture/pawn move optional stalemate: 6 bit counter from 0 to 50.

- 75 moves without capture/pawn move forced stalemate: make that 7 bits

- repitition stalemates: don't see a way around needing to know the previous board states. you need a copy of everything except the 50 move counter for previous turns. you can prune states that are impossible to return to.

A: 301 + (294 × #repeatable_states) bits

B: 328 + (321 × #repeatable_states) bits

C: 264 + (257 × #repeatable_states) bits

I'm sure there's savings to be made further compressing any of these with variable length encodings though (see links in other replies). I especially like the idea of encoding information as illegal states.

edit: originally said 4 bits for row and column but it's 3.

Re: How to build a chess engine

#53

Post by iamevn »

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…

> The position accounts for almost all of the state.

I would argue that a complete game state depends on previous game states for the sake of repitition stalemates. The current state must include a set of previous positions that can possibly reoccur.

Re: How to build a chess engine

#54

Post by agalunar »

mtlmtlmtlmtl wrote: post #13
agalunar wrote: post #12

Earlier quoted context omitted.

True, although I'd say transposition tables are much, much easier in a crucial aspect – you deal with hash collisions by simply overwriting the current entry or nop'ing. There's no linear probing, no cuckoo hashing, &c; when you want to update an entry, you check whether you'd rather store the new thing or keep the old, and that's it.

That's true in theory, but in the actual Stockfish implementation, a sort of mixed strategy is employed where entries are kept in clusters of 3. So there's a type of limited linear probing there too. Additionally, there's a lot of cleverness employed in how a position's hash is mapped to an individual cluster, and how collisions are avoided without storing a copy of the position or the full key(see the first_entry me…

That's not linear probing, though; that's having a 3-way associative cache.

Maybe that's how I should have phrased my comment: a transposition table is a cache, not a hash map,* because entries can be lost (overwritten). Furthermore, insertions may not succeed.

I know you know this; I mentioned it because I didn't want anyone to read Stockfish's source expecting an implementation of a hash map and then get confused.

Stockfish's source is well-written and incidentally didactic, so I'd definitely second the recommendation to read it.

*Or hash table, or dictionary; these are all synonyms, I just prefer "map" myself.

Re: How to build a chess engine

#55

Post by rurban »

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…

Then they should really try https://github.com/greg7mdp/parallel-hashmap, the current state of the art.

Re: How to build a chess engine

#56

Post by sapiogram »

rurban wrote: post #55
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…

Then they should really try https://github.com/greg7mdp/parallel-hashmap , the current state of the art.

Stockfish is the state of the art for its particular use case. General-purpose hash table are completely irrelevant, they'll never be able to compete on performance. Specific things Stockfish can assume:

* The table doesn't need to dynamically grow.

* Entries are allowed to be lost, but inserts can also simply fail

* Key collisions are considered acceptable, and because of this, Stockfish doesn't store the key in the table, only its hash. Even artificially high collision rates have been shown to not significantly impact playing strength.

* Bogus data due to race conditions is considered acceptable, same as above.

Re: How to build a chess engine

#57

Post by rurban »

sapiogram wrote: post #56
rurban wrote: post #55

Earlier quoted context omitted.

Then they should really try https://github.com/greg7mdp/parallel-hashmap , the current state of the art.

Stockfish is the state of the art for its particular use case. General-purpose hash table are completely irrelevant, they'll never be able to compete on performance. Specific things Stockfish can assume: * The table doesn't need to dynamically grow. * Entries are allowed to be lost, but inserts can also simply fail * Key collisions are considered acceptable, and because of this, Stockfish doesn't store the key in the…

doubt that, will test. read the descr of my link. extremely optimized for simd, and parallel access in bigger clusters than stockfish.

Re: How to build a chess engine

#58

Post by kcartlidge »

GuB-42 wrote: post #41
kcartlidge wrote: post #34

Earlier quoted context omitted.

Yes it does.

It works but it completely breaks standard behavior. Arrow keys can work normally, or select paragraph, or do nothing, or behave erratically. Page-up/down make work or may not work, and may have some weird interaction with the arrow keys. The scrollbar is nonstandard on Chrome. It is not completely broken but the mouse pointer is wrong. Mouse-based scrolling works, it is the only thing that seems to work as expected.…

Fair enough.

> Mouse-based scrolling works, it is the only thing that seems to work as expected.

TBH that's the only option I used, hence the different experience.

Post reply on HN