How to build a chess engine

230 点作者 fredrickd将近 3 年前

14 条评论

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 brutal. You can't grow dynamically(too many entries). You can't store the key, since it'll almost double the size of each entry. You can't use locks. Lookup times need to be practically constant time.[0]: <a href="https://github.com/official-stockfish/Stockfish/blob/master/src/tt.h" rel="nofollow">https://github.com/official-stockfish/Stockfish/blob/master/...</a>[1]: <a href="https://github.com/official-stockfish/Stockfish/blob/master/src/tt.cpp" rel="nofollow">https://github.com/official-stockfish/Stockfish/blob/master/...</a>

评论 #31965531 未加载

评论 #31965696 未加载

评论 #31966169 未加载

评论 #31993426 未加载

mixedmath将近 3 年前

Several years ago I built a chess engine in C, based on various ideas gleaned from the chessprogramming wiki [1]. I haven't looked at in a while, but that wiki was an extraordinarily useful resource.I didn't write a better stockfish or anything, but I was surprised that it didn't take too long to write a chess engine that could routinely beat me at chess.I'll also note that chess protocals are very standardized, and it was straightforward to attach the engine to one of the many chess GUIs out there (I used Chess Arena and scid). This was a great project and I highly recommend it.[1]: <a href="https://www.chessprogramming.org/Main_Page" rel="nofollow">https://www.chessprogramming.org/Main_Page</a>

评论 #31965260 未加载

thom将近 3 年前

I think chess engines are an amazing thing to study. So much fundamental computer science is covered, from extremely low level CPU instructions to high level data structures and algorithms. There's no surprise to me that many of the greats have turned their eye to representing and solving chess, from Turing to Knuth. I strongly suspect you could teach an entire CS degree never stepping outside of chess.Even now there are so many rich directions you could go in. For example, many people are working on explainability in machine learning, but I think in many applications you want to go even further and actually optimise a model to _teach humans_ not just explain its predictions. This is especially relevant to engines when making strategic moves rather than calculating short term tactics.I also think engines as tools for match preparation could be much better. What if you could more easily set an engine to find forced draws in certain lines, or tailor an engine to find tricky lines that a particular opponent is less likely to follow correctly, or find and optimise for certain endgame structures an opponent is weak at? Doing this in ChessBase (a truly awful but necessary piece of software) is quite painful.

dmeybohm将近 3 年前

This is a wonderful article and I really enjoyed the graphs and the clear explanations.I wrote a simple chess engine in C and then ported it to C++ [1]. It doesn't use transposition tables or quiescence search. Instead of that, I simply search only to depth=1 and then even depths (2, 4, 6...) after that, which tends to limit the horizon effect. It's not that sophisticated, but I usually lose against it. Even so, it's fun when I pull off a win.I even tried porting it to web assembly [2]. It mostly works, but the display code still has a bug where the interface disappears sometimes, and I'm still trying to figure out why. Also it doesn't work on mobile browsers I've tried.[1] <a href="https://github.com/dmeybohm/wisdom-chess" rel="nofollow">https://github.com/dmeybohm/wisdom-chess</a>[2] <a href="https://wisdom-chess.netlify.app/" rel="nofollow">https://wisdom-chess.netlify.app/</a>

tikej将近 3 年前

Chess programming is fascinating but it seems for me that it has somewhat stalled in creativity in terms of classical (non DNN) engines. They all seem to use improved versions of min-max/alpha-beta. Which results in computer players that are extremely powerful but also quite dull. This is because they assume that the opponent will play perfect game and will do it at the full strength of the engine.Basically there is no point playing against the engines at full strength as a human, since it will beat almost any human beyond grandmaster level. And that’s for weaker engines – the medium tier ones will regularly beat grandmasters and the top ones around the stockfish tier will probably not loose 1 game in 100 plays.That considered I’ve wondered what’s possible dropping the assumptions about perfect play of the opponent. Some probabilistic models of opponent or different way of rating whole tree of moves in the context, instead of position only. For example considering the alternative moves and how difficult it would be to play perfect game for the opponent, it might be better to play combination with a lot of traps with possibility of loosing some position if the opponent plays perfectly. Current engines wouldn’t play such kind of move because they’d assume (via min-max/alpha-beta) that opponent will have perfect answer. Of course, if the opponent is an engine it will, but against humans it would make things much more interesting.

评论 #31967094 未加载

评论 #31967022 未加载

nphard85将近 3 年前

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 increasingly resource intensive (tuning params, running experiments to verify strength gain all takes a lot of compute).Chess programming is also extremely addictive. On forums like talkchess.com, you see folks hanging out who have been doing it for decades (most of them are also super helpful to newbies).

评论 #31966290 未加载

Jaruzel将近 3 年前

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.

评论 #31968526 未加载

评论 #31971134 未加载

tony_codes将近 3 年前

Great article. Buidling a chess engine is an awesome way to level up as a software developer! <a href="https://blog.devgenius.io/level-up-as-a-software-engineer-by-writing-a-chess-engine-896b7f8eb443" rel="nofollow">https://blog.devgenius.io/level-up-as-a-software-engineer-by...</a>

paradite将近 3 年前

I'm also building an AI engine for games, where you can try different algorithms (heuristics, Monte Carlo tree search, expectimax, deep ML).For starter I made it for 2048. You can check it out here: <a href="https://ai-simulator.com/" rel="nofollow">https://ai-simulator.com/</a>

jeremysalwen将近 3 年前

Can highly recommend this article. I wrote a small chess engine for fun, mostly during a long plane flight back in 2018 when I had no internet access.My process for writing the engine followed almost exactly the series of steps laid out in this article. The key improvement that I made was to add quiescence search with null move pruning. After I added that, it became quite tricky to beat (for my ~1450 lichess rated self). It definitely results in an engine that is extremely greedy, and almost anti-positional, but very tricky to prove wrong.You can check it out at <a href="https://github.com/jeremysalwen/grubchess" rel="nofollow">https://github.com/jeremysalwen/grubchess</a>.

russianGuy83829将近 3 年前

horrible website, scrolling doesn’t work

评论 #31966492 未加载

ape4将近 3 年前

This seems wrong:<pre><code> // call this function again in 5 secs window.setTimeout(makeRandomMove, 500)</code></pre>

infogulch将近 3 年前

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

评论 #31965837 未加载

评论 #31966079 未加载

评论 #31966182 未加载

评论 #31971554 未加载

评论 #31966424 未加载

评论 #31965818 未加载

franciscop将近 3 年前

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 scratch" and was confused when they imported a fully working "engine".Maybe "How to build a Chess Automaton/AI Player" would be a better title? Unless in the Chess industry the "chess engine" refers to the machine player, which I do not know.PS, this website also hijacks the "down key" and the "space key", making keyboard navigation harsh...

评论 #31966051 未加载

评论 #31965127 未加载

评论 #31965373 未加载

评论 #31966207 未加载

评论 #31965095 未加载

评论 #31966145 未加载