18

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?

  • 4
    I am not sure if you are asking, and if HAS to include "machine learning", or if it simply CAN include "machine learning". – PhishMaster Nov 25 '19 at 21:17
  • 1
    The topic must include machine learning and preferably come up with a new Chess AI that is superior to existing ones. I am not sure if what I suggested above in my question is feasible. – lbragile Nov 25 '19 at 22:02
  • 14
    Google is already up to engines based on CNNs that don't even have to be told the rules of the game, just the dimensions of the board and a list of legal moves in the current position. So they can play many games. That's more or less the state of the art that you need to improve on. – RemcoGerlich Nov 25 '19 at 22:22
  • 3
    @lbragile it need not be superior - it can branch in a different direction and reach a reasonable successful result that advances research for other areas. – corsiKa Nov 26 '19 at 14:41
  • 2
    @corsiKa is totally right and this is why I strongly recommend you to look at the answer of Snack_Food_Termite. – Surb Nov 26 '19 at 15:57
46

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.

|improve this answer|||||
  • 7
    Thank you for the idea, never thought about it that way. I do agree that computers on "easy" make ridiculous moves sometimes just to be easy and let you win. – lbragile Nov 26 '19 at 6:10
  • 6
    for instance, on levels < 1500 stockfish seems to forget to recapture. – Nathan Hughes Nov 26 '19 at 19:34
  • 1
    Similarly, I know at least chess.com and almost certainly lichess employ ML techniques to detect cheating. They are pretty secretive about exactly how, but it this would be a similar and extremely relevant subject, that does not have nearly as much existing literature – Callus - Reinstate Monica Nov 27 '19 at 18:54
  • 1
    Cool ideas! there are also works that look into the state space structure of the game, such as sequencing chess, maybe ML approaches can prove useful there too. – user929304 Nov 28 '19 at 12:41
17

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.

|improve this answer|||||
  • 1
    There are several NN based PhD topics. To make a few: NN as compression for egtb, dag search, better search for simple regret minimization, expansions on deepmind's mu zero paper from last Friday. The hard part with any of this is that the field is moving fast enough that you will have a hard time making sure no one else publishes first – Oscar Smith Nov 26 '19 at 5:08
  • 1
    It's worth noting that it won't really be a chess topic - in this direction, all the work you'll do will be with various properties ML, and you'll most likely use no chess specific knowledge whatsoever after you've coded (or reused from someone else) the very basics of what's a legal move and what's the winning condition. So if the idea is to work on something where you'll be spending your time on nuances of chess, this won't really be it. – Peteris Nov 26 '19 at 11:55
  • 1
    In the original article I read about AlphaZero it says that it beat Stockfish while running several hundred times slower than Stockfish. Here's the article, fresh from my browser history The quote is "AlphaZero was calculating roughly 80 thousand positions per second, while Stockfish was running at 70 million positions per second". That article is from 2017, though, a "long" time ago :-) – Aaron F Nov 26 '19 at 16:47
  • 1
    @Peteris that's the Zero approach, which is not necessarily the best - both AllieStein and Fat Fritz use human-imparted chess knowledge. – Allure Nov 26 '19 at 19:39
  • 2
    @AaronF AlphaZero (and the other NN engines) certainly run slower than Stockfish. This ratio of the number of positions searched per second is actually critical in determining whether the hardware comparison is fair. Computer chess moves really quickly as well, and Stockfish has improved tremendously since 2017, which was one of the main criticisms of the AlphaZero paper - it tested against an old version of Stockish. – Allure Nov 26 '19 at 19:44
10

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?

|improve this 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?
|improve this answer|||||
  • These are great suggestions but would require massive surveys to be made after implementation to prove the point. I would rather have something that can be measured without much user input/testing (as suggested by @John Coleman) above. But none-the-less, here is a thumbs up :) – lbragile Nov 26 '19 at 6:13
  • 4
    While I agree that these are very interesting research topics, since OP mentioned machine learning, I suppose he is interested in a computater related topic. – lvella Nov 26 '19 at 12:51
  • 1
    @Ivella I am assuming that you were the downvote. I wrote my answer BEFORE that was clarified. Note that the question was edited. – PhishMaster Nov 26 '19 at 16:59
  • @PhishMaster, just to be clear the edit was purely semantic and made by another member. I rolled it back to be the original post, but the question remained identical to what was originally asked. – lbragile Nov 26 '19 at 21:22
  • 1
    @ibragile, that does not mean that the original question could not be interpreted both ways, which is why I asked you to clarify it. – PhishMaster Nov 26 '19 at 22:14
6

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.

|improve this answer|||||
  • 3
    I worked in a machine learning group in the past 5 years and I think this is probably the nicest project suggested so far. It is certainly super interesting to see how to beat this horizon problem which is closely related to a lot of common problems in ML (how to find nice approximate solutions to combinatorial problems). Also, providing OP works seriously, it is quite guaranteed to obtain at least a reasonable solution (important for a PhD). Defining when does the "end" of the game starts might be tedious but definitely an interesting question to start with. – Surb Nov 26 '19 at 15:01
  • 2
    As you would know these are huge topics. I was writing pretty informally. To simplify chess computers to a ridiculous extent, there are basically two approaches: brute force or heuristic. Brute force just takes all possible moves and tries to find the best outcome. Heuristic [more human] approaches instead look at a position's characteristics. Obviously the hardware becomes relevant; brute force with a supercomputer will beat any heuristic approach with an average CPU. Thanks for the comment! I try my best! There are Phd topics here! – Snack_Food_Termite Nov 26 '19 at 15:22
  • 2
    Yes, this is indeed more or less what I had in mind. And precisely building such heuristics is a big part of ML and computer vision when tackling NP-hard problems (graph matching, feature selection, clustering, etc.). So there is certainly a huge pool of heuristics to take inspiration from and adapt to this chess endgame problem. In particular, making such connections with a seemingly unrelated problem is nowadays extremely appreciated by the the community (making it a great PhD topic). – Surb Nov 26 '19 at 15:53
4

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.

|improve this answer|||||
3

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.

|improve this answer|||||
3

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.

|improve this answer|||||

Not the answer you're looking for? Browse other questions tagged or ask your own question.