Love this article. I went through a lot of these same steps when I was tinkering with my own chess bot. Bitboard representation with bitshifting operations can dramatically speed everything up (see here https://chessprogramming.wikispaces.com/Bitboards). Another easy step is to integrate an opening book. The "Encyclopaedia of Chess Openings" provide a great set. Here is link to CSV of the openings for easy parsing:
https://github.com/notnil/opening/blob/master/csv/openings_a...
It didn't understand castling, en passant and promotions. It would also only play white.
I did once try to pit it against a modern engine. It seemed to do reasonably well until the modern engine sneakily castled, and I was unable to tell 1k Chess about this, thus forcing it to forfeit the game.
Of course, since posting that, I since found this:
Chess for the PC; 392 bytes. You put it in your boot sector. Still no castling, en passant and promotions, though, although there's an 831 byte version which has those.
> I'm having trouble beating a chess program I wrote. Not sure if I'm a bad player or the algorithm is decent
Most beginners will lose to even a chess engine that only looks one step ahead, as it will not drop pieces in obvious ways, but the beginner will.
Chess.js etc. is great btw. Last time I made some chess ai, most of the time was spent generating possible moves. En passant, promotion and stuff adds complexity.
I spent some time trying to develop a chess AI a short time ago. I had this crazy idea that if I stored all of the possible moves in memory I'd only need to calculate the nth level of depth after every move.
This kills the computer.
After deciding it was best to simply re-evaluate every time, what caught me up was en passant castling and so fourth. It's a challenging topic. I recommend it.
Interesting that it's deterministic. I can get it to play the same game again and again. Why is this not the case with more advanced chess engines?
Edit: Apparently single-threaded stockfish is deterministic. Maybe my experience with non-deterministic chess engines just has to do with the handicapping related to providing easier levels of play.
Never checked but somehow got me surprised: aren't all chess engines deterministic? The same program, given the same input, should give the same output unless it is specifically programed to try to avoid it (and then we have PRNGs).
Some things that make chess engines non-deterministic:
1) Most chess engines use an opening book instead of calculating moves early in the game. These books are often programmed probabilistically, so it may have 4 reasonable responses to a given move and pick one randomly.
2) Many engines are programmed to "ponder", that is do optimistic calculations during the opponents turn. This means that the time taken by you to make the move could potentially affect the calculations performed by the engine.
You forgot two more things, they might not happen often enough because of the sheer number of possible positions in the early gameplay but it does make a difference in the game if you play the same position every time.
Many chess engines are (also) made for humans to play against.
Humans wouldn't want their opponent to play the exact same way every time. For a simple example, playing white, one wouldn't want the computer to always open 1. h4.
So, either the computer has to pick an opening, or the human opponent has to pick one.
Of course, that extends past the first move, so, assuming the computer to play deterministically, one would end up with the human opponent having to specify "let's play opening X, variant Y, as typically played by Z up to black's 15th move". It probably is easier to use a "set up a custom board" feature than to specify that.
And it wouldn't even stop there. The human specifying that particular opening likely wants to study that opening, not just the single continuation that the computer thinks to be the best one.
Also, as another poster said, a chess engine may use Monte Carlo simulation to pick a move, and that means using a random number generator.
A reply that was deleted mentioned that some engines use Monte Carlo simulations which are non-deterministic (?).
My experience with chess engines being non-deterministic is that if I pick the same opening I don't always play the same game with the same engine. I really might just be off here, and that variance might be related to random artificial handicapping.
Most chess engine opening books weight their branches to pick certain moves x% of the time, and offer 0 or negative value to 'bad moves' never to pick.
e.g. 1.e4, d4, c4 and Nf3 will get picked more often than 1. b3, c3, nc3 and f4, and 1. g3, e3 even less (or not at all).
Unless efforts are made for results to be deterministic, concurrent algorithms may complete their work / return their results in an ordering that is unstable (depending mostly on host OS and CPU management of time-slicing).
I'm very interested in the values assigned to pieces. Does anyone know the source or reasoning behind the table in step 2?
How are pieces relative values calculated? What's to say a pawn is 1/3 of a rook or a knight?
And why is the king 900, not simply the total value of all other pieces or slightly more? 8 pawns (10 ea), 2 knights (30 ea), 2 rooks (30 ea) and a queen (90) totals 290 points. Why can't a king simply be 300 points? If it needed to be worth more than both sets (white and black) for some reason why couldn't it be worth 600? The value 900 seems arbitrary to me.
If there's sound reasoning behind this can anyone recommend material related to deriving similar weighted values?
Check out this chess programming wiki article [1] for a (still fairly hand-wavy) rationale for similar piece values, and the Wikipedia article on chess piece relative values [2] for a more in-depth look at various weightings. Some modern approaches use analysis of a huge corpus of master games to come up with piece values, but many of the systems are based on intuition and empirical evidence.
> To follow on though, shoukdn't it technically be the case that piece values should in theory fluctuate based on current situation.
Yes. One common example is knights and bishops. Both are worth about 3 pawns, but knights are generally more useful in closed positions due to their ability to jump over pieces, while bishops are better in open positions since they can more attack and move long distances.
So in some sense, and I'm just brain-farting here, the value of a piece is a weighted sum of all the possible squares it could occupy during move generation. Something like a rudimentary path trace.
Now trying my best not to get distracted building chess machines. :/
Right, although I didn't mean castling into check. I meant tempting a greedy algorithm by throwing away a high value piece (which was always a weakness of early chess machines), although I realize the tree search would spot that.
Also now that I'm awake, read the article fully now.
Toledo Nanochess is the world's current smallest chess
program written in C language. Now for the first time is
published the complete documented source code. Also
including the documented source code of the JS1K 2010
Chess entry (2nd place winner)
I recently wrote a chess AI in javascript, and found that it wasn't able to evaluate nearly as many moves per second as I expected, even though the implementation was pretty light (though not extensively optimized).
My feeling is that for serious AIs that need to perform huge tree evaluations (whether classical alpha-beta or something closer to monte-carlo minimum regret searches) there's several orders of magnitudes of optimization that can be performed, huge gains from subtle tradeoffs (larger static memory allocations, memory caching strategies, etc) and deep heuristics that can lead to pruning search spaces by huge percentages.
Highly tuned implementations such as these - or the graphics visualizations from the demo scene - have always fascinated me as an art form.
In practice, for most practical purposes, the industry seems to value more code for more features over the incredible feats of superimplementation.
I am working on building a generic card game environment/runner which could plugin into different AI systems, and this is very helpful.
I've been looking for a reinforcement-learning version of this. How do you build an AI that plays Tic-Tac-Toe against itself to figure out the best strategy?
I made a few minimax based AIs for games in uni, but I had always wondered how I would calculate score. How are these point systems made? Are they just educated guesses? How far can minimax take you as far as skill level?
I'm currently in the process of building my own chess AI (in python), and I'm using as a score a weighted combination of the material and of the number of squares controlled by each side. I am planing to experiment with weighting more the squares that are closed to the opponent's king, and possibly to improve the evaluation function using reinforcement learning.
That said, my program is currently pretty weak, first I have to optimize its calculation speed to it can calculate deeper.
There's a common scoring system that is often used to help children who are learning to play chess (pawn is 1, knight and bishop are 3, etc).
A pure minimax engine isn't that hard to beat because the engine will be basically playing random moves during the opening phase. An opening repertoire + minimax on a modern computer will beat casual players (probably 1700-1900 Elo if I had to guess). You also have to do some good time management.
Why don't we have artificial intelligence? Well, I imagine that it would require that 'intelligence' be something other than an delusional artifact of our neurophysiology in the first place...
One of the preinstalled apps on macOS is /Applications/Chess.app. Turns out it uses an open-source chess engine called sjeng, the binary for which is inside the app bundle. Chess.app is itself open source, so I tweaked Apple's code for my own purposes. The code launches an sjeng process, opens a pipe to it, and sends commands over the pipe.
There's a couple of sentences about this in the _README file here (as well as my tweaked source files):
Fun fact: you can play chess in a terminal window by running /Applications/Chess.app/Contents/Resources/sjeng.ChessEngine. You can enter the `help` command for instructions. Note this will create four files with .lrn extensions in your home directory. I forget how to control this behavior -- you can Google "sjeng" for details.
Plug: Any gophers out there looking to build their own bot can use my chess engine https://github.com/notnil/chess
Edit: wording