Chess PhD topic in machine learning?

Question

I searched this online and couldn't find sufficient answers. Is there a topic in chess that includes machine learning and would be sufficient for a PhD thesis? I was thinking of utilizing a CNN that tells you the correct move based on the current position (and previous couple of moves) without calculating all the tree branch moves ahead. Would this be feasible?

Answer 1

You have little chance in your dissertation of surpassing state of the art chess engines. Perhaps you could find a hook which hasn't been explored so much. One idea is to train your program to play amateur chess in a convincing way. Can a program pass a sort of chess Turing Test where a human-player couldn't tell if they were playing an AI or playing a player rated e.g. 1600? When I play computer chess programs with a level setting at a level that I can actually beat, there is something not quite right about it. The program is deliberately hobbled (so I can beat it) in such a way that it sometimes makes blunders that a human player of the target level is unlikely to do, but at other times it still makes moves which seem just too good for that level. Trying to imitate human chess-playing rather than targeting optimal chess-playing seems like an interesting AI problem.

Answer 2

You might be interested in AlphaZero and its derivatives. AlphaZero is the original neural-network based chess engine; since then there have been various other attempts (Leela Chess Zero, AllieStein, the recent Fat Fritz ...) to replicate AlphaZero's ideas. The key paper to read is this one.

The data right now seems to indicate that although these neural network engines are very strong, the conventional chess engine Stockfish is still the strongest engine on the planet on consensus equal hardware. That said, the situation is fluid; a few months ago Leela was probably the strongest.

I do not know if there's enough material here for a PhD project, but there's a great deal of territory to cover.

Answer 3

There are plenty of possible Phd-topics that connect chess and machine learning. The more interesing and feasible ones have nothing to do with building better engines. Here are some ideas:

• Human players have a particular playing style. Is it possible to learn to extract some metric of style from games that allows to assign games to players with a certain probability?

• Can you use this model to simulate games by any particular player?

• Humans play chess via an intuitive feel for the position. Engines used to just calculate on top of a simple evaluation function. Is it possible to use Leela's NNs to give an output that matches human intuition regarding stuff like "king safety", "lead in development", "weak squares", etc?

• Can you use this output to create automatic annotations that provide insight to humans beyond: This is the best line and this is the evaluation of the resulting position?

• Language models like GTP-2 are getting extremely good at modelling text. There are roughly a billion online chess games availabe for free. Can you use this massive dataset to train a transformer model to play chess without ever having seen a chess board, just by learning from pgn?

• Can you distinguish between female and male players just by analysing their moves?

Answer 4

I am not a computer scientist. But I have been a chess computer enthusiast since the 1980's. My first engine was a tabletop Novag in about 1988. I read David Levy's book "how to get the most out of your chess computer".

The two traditional weaknesses in chess engines have always been [1] The horizon effect. David Levy describes it as being like a man in a maze who shines a torch at night. The man looks ahead and thinks that there is a clear path forward. But just past the "horizon" of vision the maze turns and has a dead end. Chess computers, like this dead end, see 8 moves ahead and think that they have a win. But 9 moves ahead they have a dead loss.

[2] Endgames. This is where [1] is most severe. Because to even a relative novice human player, we can see that a pawn will be pushed from its start square and make a queen and win the game. But to early chess computers that was far too many moves to see that!! Early chess computers struggled to win even totally won endgames.

Now, obviously in 2019 engines like Fritz and Stockfish and Alphazero manage [1] and [2] much better than my 1980's Novag. Levy's horizon effect is a bit dated. But it still applies. A few weeks ago I used it to beat an engine. I tricked the engine into thinking that it was rook ahead. But at my leisure I could over 20 moves get the material back easily and have a won endgame. The engine was probably about 2000ish.

If I had to suggest any Phd on machine learning and chess, I'd like to see one done on the endgame. Instead of filling the engine with huge endgame tables, what about taking classic endgame themes in Fine's Basic chess endings and conducting machine learning? A Lucena endgame for instance. Or some classic endgames from World Championship matches? Or endings with a million checks such as queen and pawn endings? I sincerely believe that there is a lot of new ground in endgames. I don't think for a moment that machine or human learning has covered everything in chess; endgames don't get the degree of attention that openings or middlegames get. Ideas in endgames have also developed. Steintz made it look like a pawn majority closer to the king was enough to have a won endgame. Alekhine showed that wasn't necessarily the case if you had other dynamic factors.

I'd be interested in seeing how you go! I like the previous suggestion of trying to realistically imitate weaker human play rather like a Turing test. I've noticed that with engines; they make weak moves that a human wouldn't make when set to a lower level.

Answer 5

Feasibility of non-search based approaches

I'm going to talk about the feasibility of using a non-search based approach. Immediately, some questions that come to mind:

1. Does there exist a good static_eval function that takes a (Position, PlayerTurn) and returns some Score? ¹
2. Small changes in positions can often lead to massive differences in evaluation.
3. Search is not solely used by chess engines. Humans extensively use search too, albeit for a far smaller amount of nodes.

In theory, any large enough model (e.g. with some multiple of 6^64 parameters) can exactly represent a function perfect_eval : (Position, PlayerTurn) -> {Win, Loss, Draw}. But we only have access to finite space and time, so we desire a function static_eval : (Position, PlayerTurn) -> Score instead. Your proposed formulation cnn_eval : (Position, PlayerTurn) -> Move is roughly the same, but without having to choose the argmax of candidate moves in a position. However, it's a bit easier to talk about how static_eval behaves, so I'll stick with that for the rest of this answer.

Let's say we've managed to find ourselves a good static_eval function. Consider all moves in this position:

3qr1k1/1b1rbp2/p2p2p1/1p1np3/4P3/P2BB2Q/1PP3PP/4RR1K w - - 0 22

1. Rxf7 Kxf7 2. Qh7+ Ke6 3. exd5+ Kxd5 4. Be4+ Kxe4 5. Qf7 Bf6 6. Bd2+ Kd4 7. Be3+ Ke4 8. Qb3 Kf5 9. Rf1+ Kg4 10. Qd3 Bxg2+ 11. Kxg2 Qa8+ 12. Kg1 Bg5 13. Qe2+ Kh4 14. Bf2+ Kh3 15. Be1 1-0

Most of the moves are terrible, right? (b4, a5, Qe6, ...) So clearly, small deviations in its input Position should result in big differences in its evaluation. But this means that the "surface" that static_eval represents is very, very bumpy. This is fine if there's a structure to that bumpiness, preferably one that can be represented within our space and time constraints. Personally, I think chess is complex enough and the surface too bumpy that modelling it with our very limited space constraints is going to be very challenging. In the above position, the obvious move is to regain material with exd5. But as Wei Yi shows, if you search sufficiently deep, you'll realize that Rxf7 is winning.

I think another argument against an approach which does not consider a search tree is that humans themselves can take a quick glance at a position and change their minds after some calculation. In the following following position, it is easy to assume that black is winning due to his many threats. But after discovering a simple tactical sequence (starting with Qxf8+), it's clear that white mates in 4.

5rk1/3R1p1p/2p2p2/1q2nB2/5B2/QP3nP1/4rP1P/R4K2 w - - 2 34

Another idea

So if search is so important, why can human grandmasters play reasonably correct games being limited in the number of nodes they consider? Human "static evaluations" might be far more time-intensive, but they are typically far more useful than the static evaluations performed by traditional chess engines. There is a tradeoff in evaluation time and accuracy, and until recently, chess engines have significantly preferred low evaluation times in order to search the most nodes they can.

As @konsolas puts it,

Neural networks operate much more slowly than handcrafted evaluation functions. In the TCEC Superfinal, Leela Chess Zero, running on two GPUs each with dedicated tensor cores, is able to search around 60 thousand positions per second. By contrast, Stockfish, on a single core on my PC, searches over 2 million positions per second.

I think a more fruitful endeavor than completely abandoning search is to experiment with more expensive evaluation methods, but with a smaller number of nodes traversed.

More interesting ideas that people have tried can be found here.

---

¹ Naturally, one also needs to input a State parameter to handle rules like castling, en passant, and 50-move rule.

Answer 6

A couple of ideas:

1. Does chess help kids do better in school? That question has long been debated.
2. Do certain businesses with chess players, especially strong chess players, have an advantage in certain types of business, like finance?

Answer 7

Have you considered something like general game play? If you can train an AI to be good at both chess and other board based games (with the same network) you could show some interesting results.

This paper explores that concept for MCTS

This article explores the concept in RL.

Answer 8

I think a cool project which mixes chess and machine learning is to build a chess bot for 4 players chess. Such variant can be played on chess.com and if I remember correctly, they don't have particularly strong bots at the moment. Probably the most fun would be to use reinforcement learning and let the bot learn by playing against human players on the website.