When I was a kid, back in the 70's and 80's, I thought chess programs were the most sophisticated computer programs in the world. That was back when the average personal-computer chess program wasn't very good, and dedicated chess computers cost hundreds or thousands of dollars, so it seemed to me that chess was something very difficult for computers to do. At the time, many experts still thought a computer would never be able to beat human grandmasters. I dreamed that I would one day write The World's Greatest Chess Program, and that would prove I was a great computer programmer.
But one's priorities change. I did look into how chess programs worked when I was in college, and while I found the topic interesting, I didn't try writing my own program. I still thought that writing a chess program was something every Real Computer Programmer should do, but I didn't get around to it.
Now, at age 50, I've finally done it. A few weeks ago I started writing a chess engine in Swift, and it is now capable of playing a real chess game. I call it "kjchess".
It works, but it's slow. On my 2013 MacBook Pro, my move search function can only search about four half-moves deep to find a move in a reasonable time, even when using all the CPU cores. That is terrible, considering that it is worse than the 4MHz 8-bit Fidelity "Classic" chess computer I had 25 years ago.
Why is my engine so slow? I initially gave myself a few constraints:
- Write it in "high-level" Swift (that is, it shouldn't look like a C or C++ program).
- Write it in a functional-programming style (in particular, use immutable data structures wherever possible).
- Don't refer to any other chess programs' source code. Use only the knowledge of chess programming I've gleaned over the last few decades.
These constraints made it an interesting exercise, but I relaxed them. For example, I copied the minimax algorthm with alpha-beta pruning from Wikipedia, and I've incorporated some positional evaluation ideas from the Chess Programming Wiki.
Now that I've seen how slow it is, I think I need to abandon the "only immutable data structures" constraint. I think the main reason my engine is so slow is that it creates a brand-new "position" structure for every possible move, leading to a lot of memory allocation, deallocation, and copying, whereas other engines have a single global position on which they make and unmake moves very quickly.
Also, my engine doesn't save any search state between moves, and it doesn't do any pondering during the opponent's move. I could probably make it a lot better by adding those features.
Despite its limitations, it plays well enough to beat me once in a while. That's not impressive, because I am a terrible chess player, but I figure I'm a winner either way. (I'm also a loser either way, but I can ignore that.)
If you want to play it, and you have a Mac and know how to build Swift programs, you can check it out here: https://github.com/kristopherjohnson/kjchess