Hacker News Reader

Comment by pk2200 | Hacker News Reader

There was a recent thread about challenging projects every programmer should try, and I think writing a chess engine would be a nice addition to that list. Chess programming is a refreshing change from modern software development, because you don't need any complicated frameworks or libraries, just a basic grasp of the minimax algorithm for searching a game tree. I have fond memories of writing an engine as a fresh college grad - it was my first "big" project and I made every mistake imaginable, but it was great fun and sharpened my coding skills immensely. It's exhilarating to play against your own program and then try to improve it. Highly recommended!

View on HN

You could expand this category to an AI for a number of similar games (like checkers and reversi) as well. I've written a double dummy solver for bridge--a program that computes the optimal result of the play of a bridge hand--as a side project and I think it's also a very good choice. A lot of the same tools as chess engine development apply: alpha-beta and the myriad variant search algorithms like MTD(f), transposition tables, heuristics like the killer move heuristic or the countermove heuristic. But you also need to apply some domain specific heuristics and tools, and since the whole thing is performance critical you need to worry about low level optimizations and good multithreading. In the bridge case it's not at all trivial to get something that can even finish at all in a reasonable timespan.

I wrote a chess program in college, and agree that it was fun. But isn’t the whole exercise a bit outdated? Building a chess program now surely would start with deep learning

There is plenty to learn about algorithms and data structures by coding up a 'conventional' chess program, you're likely not going to go up against the world champion players or computers but against a much more inferior opponent: yourself.

When I was 17 or so I wrote a chess program, at the time I was pretty deep into chess and color me surprised when after a week or so I could only beat my own program by really paying attention because it would never mess up and I would mess up all the time. All it would take is a little mistake and then you'd be lost already.

The code was written in 6502 assembler, it was a lot of fun to write. My buddy who wrote his own in Pascal was quite ticked off that my very straightforward 'dumb' program would beat his extremely elegant program hands down simply because it would look on average two ply further ahead. That's a lot of extra moves to analyze but the speed difference between machine language and Pascal (at the time, today this would definitely no longer be the case with our much better optimizing compilers) on an 8 bitter made this an uneven match.

On the plus side: his code was far more readable than mine.

The top two chess programs, Stockfish and LC0, both use neural nets for evaluation but Stockfish's is very shallow CPU-based one with a clever way not to have to re-evaluate the whole position after each move (borrowed from Shogi). LC0 is modeled after AlphaZero and uses reinforcement learning.

> with a clever way not to have to re-evaluate the whole position after each move (borrowed from Shogi).

details?

Edit: well ok it was easy enough to duckduckgo it myself ;)

https://www.chessprogramming.org/NNUE

https://www.chessprogramming.org/Incremental_Updates

For me personally such projects are also about having fun, and I just like implementing some of those elegant algorithms and maybe understand them at a deeper level. I don't enjoy pushing data through some intangible neural network and tweaking it nearly as much. Especially if it involves reading through the documentation of some library and the coding is just the boilerplate required to shovel data in.

That said, everyone has their own preferences and as long as you are motivated to spend a long time with it you can learn something from it, even if the improvement isn't noticeable immediately.

Reply on news.ycombinator.com