Answers.Body: <p>You might be interested in <a href="https://en.wikipedia.org/wiki/AlphaZero" rel="noreferrer">AlphaZero</a> 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 <a href="https://science.sciencemag.org/content/362/6419/1140" rel="noreferrer">this one</a>.</p>
  
  <p>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.</p>
  
  <p>I do not know if there's enough material here for a PhD project, but there's a great deal of territory to cover.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T05:08:18.263Z
Answers.Text: 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
Answers.UserDisplayName: Oscar Smith
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T11:55:56.777Z
Answers.Text: 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.
Answers.UserDisplayName: Peteris
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T16:47:14.367Z
Answers.Text: 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](https://en.chessbase.com/post/the-future-is-here-alphazero-learns-chess) 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 :-)
Answers.UserDisplayName: Aaron F
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T19:39:35.627Z
Answers.Text: @Peteris that's the Zero approach, which is not necessarily the best - both AllieStein and Fat Fritz use human-imparted chess knowledge.
Answers.UserDisplayName: Allure
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T19:44:17.320Z
Answers.Text: @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.
Answers.UserDisplayName: Allure
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T23:59:37.487Z
Answers.LastActivityDate: 2019-11-25T23:59:37.487Z
Answers.UserDisplayName: Allure
Answers.Body: <p>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:</p>
  
  <ul>
  <li><p>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? </p></li>
  <li><p>Can you use this model to simulate games by any particular player?</p></li>
  <li><p>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?</p></li>
  <li><p>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?</p></li>
  <li><p>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?</p></li>
  <li><p>Can you distinguish between female and male players just by analysing their moves?</p></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T13:56:48.177Z
Answers.LastActivityDate: 2019-11-26T13:56:48.177Z
Answers.UserDisplayName: BlindKungFuMaster
Answers.Body: <p>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". </p>
  
  <p>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. </p>
  
  <p>[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. </p>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <p>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. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T15:01:54.130Z
Answers.Text: 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.
Answers.UserDisplayName: Surb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T15:22:14.813Z
Answers.Text: 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!
Answers.UserDisplayName: Snack_Food_Termite
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T15:53:47.997Z
Answers.Text: 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).
Answers.UserDisplayName: Surb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T13:20:38.563Z
Answers.LastActivityDate: 2019-11-26T13:20:38.563Z
Answers.UserDisplayName: Snack_Food_Termite
Answers.Body: <h3>Feasibility of non-search based approaches</h3>
  
  <p>I'm going to talk about the feasibility of using a non-search based approach. Immediately, some questions that come to mind:</p>
  
  <ol>
  <li>Does there exist a good <code>static_eval</code> function that takes a <code>(Position, PlayerTurn)</code> and returns some <code>Score</code>? ¹</li>
  <li>Small changes in positions can often lead to massive differences in evaluation.</li>
  <li>Search is not solely used by chess engines. <strong>Humans extensively use search too</strong>, albeit for a far smaller amount of nodes.</li>
  </ol>
  
  <p>In theory, any large enough model (e.g. with some multiple of 6^64 parameters) can exactly represent a function <code>perfect_eval : (Position, PlayerTurn) -&gt; {Win, Loss, Draw}</code>. But we only have access to finite space and time, so we desire a function <code>static_eval : (Position, PlayerTurn) -&gt; Score</code> instead. Your proposed formulation <code>cnn_eval : (Position, PlayerTurn) -&gt; Move</code> is roughly the same, but without having to choose the <code>argmax</code> of candidate moves in a position. However, it's a bit easier to talk about how <code>static_eval</code> behaves, so I'll stick with that for the rest of this answer.</p>
  
  <p>Let's say we've managed to find ourselves a good <code>static_eval</code> function. Consider <em>all moves</em> in this position:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Most of the moves are terrible, right? (b4, a5, Qe6, ...) So clearly, small deviations in its input <code>Position</code> should result in big differences in its evaluation. But this means that the "surface" that <code>static_eval</code> 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.</p>
  
  <p>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.</p>
  
  <pre><code>5rk1/3R1p1p/2p2p2/1q2nB2/5B2/QP3nP1/4rP1P/R4K2 w - - 2 34
  </code></pre>
  
  <h3>Another idea</h3>
  
  <p>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.</p>
  
  <p>As <a href="https://chess.stackexchange.com/a/23774/1090">@konsolas puts it</a>,</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>More interesting ideas that people have tried can be found <a href="https://chess.stackexchange.com/questions/5056/is-there-a-chess-engine-that-does-not-use-brute-force-search">here</a>.</p>
  
  <hr>
  
  <p>¹ Naturally, one also needs to input a <code>State</code> parameter to handle rules like castling, en passant, and 50-move rule.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T15:29:02.597Z
Answers.LastActivityDate: 2019-11-28T15:29:02.597Z
Answers.UserDisplayName: Mateen Ulhaq
Answers.Body: <p>A couple of ideas:</p>
  
  <ol>
  <li>Does chess help kids do better in school? That question has long been debated.</li>
  <li>Do certain businesses with chess players, especially strong chess players, have an advantage in certain types of business, like finance?</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T06:13:25.760Z
Answers.Text: 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 :)
Answers.UserDisplayName: lbragile
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T12:51:45.613Z
Answers.Text: 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.
Answers.UserDisplayName: lvella
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T16:59:14.377Z
Answers.Text: @Ivella I am assuming that you were the downvote. I wrote my answer BEFORE that was clarified. Note that the question was edited.
Answers.UserDisplayName: PhishMaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T21:22:45.573Z
Answers.Text: @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.
Answers.UserDisplayName: lbragile
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T22:14:10.157Z
Answers.Text: @ibragile, that does not mean that the original question could not be interpreted both ways, which is why I asked you to clarify it.
Answers.UserDisplayName: PhishMaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T21:15:59.970Z
Answers.LastActivityDate: 2019-11-25T21:15:59.970Z
Answers.UserDisplayName: PhishMaster
Answers.Body: <p>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.</p>
  
  <p><a href="https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/4935/5300" rel="nofollow noreferrer">This paper explores that concept for MCTS</a> </p>
  
  <p><a href="https://science.sciencemag.org/content/362/6419/1140.abstract" rel="nofollow noreferrer">This article explores the concept in RL.</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T20:55:15.567Z
Answers.LastActivityDate: 2019-11-26T20:55:15.567Z
Answers.UserDisplayName: Octopuscabbage
Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T13:14:32.657Z
Answers.LastActivityDate: 2019-11-26T13:14:32.657Z
Answers.UserDisplayName: Surb
Answers.Body: <p>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 <em>amateur chess</em> in a convincing way. Can a program pass a sort of chess <a href="https://en.wikipedia.org/wiki/Turing_test" rel="noreferrer">Turing Test</a> 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 <em>human</em> chess-playing rather than targeting optimal chess-playing seems like an interesting AI problem. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T06:10:54.053Z
Answers.Text: 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.
Answers.UserDisplayName: lbragile
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T19:34:44.410Z
Answers.Text: for instance, on levels < 1500 stockfish seems to forget to recapture.
Answers.UserDisplayName: Nathan Hughes
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-27T18:54:30.473Z
Answers.Text: 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
Answers.UserDisplayName: Callus - Reinstate Monica
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-28T12:41:41.277Z
Answers.Text: Cool ideas! there are also works that look into the state space structure of the game, such as [sequencing chess](https://arxiv.org/abs/1609.04648), maybe ML approaches can prove useful there too.
Answers.UserDisplayName: user929304
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-27T15:39:39.847Z
Answers.Text: The Maia engine is exploring precisely this research, and indeed it is being done by PhDs, so that's a great idea you had, John!  https://lichess.org/@/maia5
Answers.UserDisplayName: Michael B. Currie
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-26T00:56:42.743Z
Answers.LastActivityDate: 2019-11-26T00:56:42.743Z
Answers.UserDisplayName: John Coleman
Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-25T21:17:58.707Z
Comments.Text: I am not sure if you are asking, and if HAS to include "machine learning", or if it simply CAN include "machine learning".
Comments.UserDisplayName: PhishMaster
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-25T22:02:14.147Z
Comments.Text: 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.
Comments.UserDisplayName: lbragile
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-25T22:22:44.417Z
Comments.Text: 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.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-26T13:25:38.333Z
Comments.Text: Yeah. But do engines like Alphazero "cheat" by using table bases for the endgame? That's because the endgame was always been any chess engine's biggest weakness!!
Comments.UserDisplayName: Snack_Food_Termite
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-26T14:41:53.920Z
Comments.Text: @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.
Comments.UserDisplayName: corsiKa
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-26T15:57:17.430Z
Comments.Text: @corsiKa is totally right and this is why I strongly recommend you to look at the answer of Snack_Food_Termite.
Comments.UserDisplayName: Surb
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-27T00:02:09.353Z
Comments.Text: @NotThatGuy What? AlphaZero and all other successful engines I know certainly do explore future positions.
Comments.UserDisplayName: rlms
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-27T00:05:56.350Z
Comments.Text: @NotThatGuy Yeah I agree, both from the published papers and from the fact that even lichess analysis uses look-ahead to a large depth of moves. That's why it keep changing its evaluation until it finds the optimal move.
Comments.UserDisplayName: lbragile
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-27T21:09:02.253Z
Comments.Text: I think some of the answers here suggest interesting topics, but not necessarily ones that are necessary or sufficient for a PhD thesis. Beating state of the art engines is extremely unlikely, but within the realm of possibility if you're lucky enough to come up with the right insight. Beating the state of the art would be something that would probably get you published in Science or Nature, which is a  massively higher barrier to clear than a PhD thesis.
Comments.UserDisplayName: llama
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-28T12:51:51.013Z
Comments.Text: Haha, I saw you on the sidebar. :P
Comments.UserDisplayName: Mateen Ulhaq
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-29T03:31:22.430Z
Comments.Text: The purpose of doing research is to **find out** if something is feasible. If we told you the answer what point would there be in doing a PhD?
Comments.UserDisplayName: Bob Jarvis - Слава Україні
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-29T03:34:46.480Z
Comments.Text: @BobJarvis-ReinstateMonica was I asking for an *answer* or just looking for guidance? There is a big difference there, I think it is reasonable to ask for other's opinion when you are not sure what to do/how to progress. As you can see many suggestions here are beyond amazing making me grateful for asking this.
Comments.UserDisplayName: lbragile
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-29T10:36:41.433Z
Comments.Text: You've already received a bunch of great answers, some of which I could've posted too, so I'll just stick this in as a comment: find yourself a copy of Garry Kasparov's book Deep Thinking: Where Machine Intelligence Ends and Human Creativity Begins. It basically walks you through the history of computer chess, albeit on a pretty high level. Maybe you'll get some new ideas there, and if not, then it's a good book anyway. :)
Comments.UserDisplayName: ZeroOne
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-02T07:54:07.600Z
Comments.Text: is 'lbragile' a combination of 'lbra' and 'agile'/'antifragile' or something?
Comments.UserDisplayName: BCLC
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-02T15:28:00.887Z
Comments.Text: It’s a combination of my first and last name 
Comments.UserDisplayName: lbragile
Tags: <analysis><learning>
Title: Chess PhD topic in machine learning?
ThreadText: # Chess PhD topic in machine learning?
  
  (Asked by: username_0 on 2019-11-25)
  
  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?
  
  **Tags:** analysis, learning
  
  > **Comments:**
  > **username_1**: I am not sure if you are asking, and if HAS to include "machine learning", or if it simply CAN include "machine learning".  
  > **username_0**: 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.  
  > **username_2**: 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.  
  > **username_3**: Yeah. But do engines like Alphazero "cheat" by using table bases for the endgame? That's because the endgame was always been any chess engine's biggest weakness!!  
  > **username_4**: @username_0 it need not be superior - it can branch in a different direction and reach a reasonable successful result that advances research for other areas.  
  > **username_5**: @username_4 is totally right and this is why I strongly recommend you to look at the answer of username_3.  
  > **username_6**: @NotThatGuy What? AlphaZero and all other successful engines I know certainly do explore future positions.  
  > **username_0**: @NotThatGuy Yeah I agree, both from the published papers and from the fact that even lichess analysis uses look-ahead to a large depth of moves. That's why it keep changing its evaluation until it finds the optimal move.  
  > **username_7**: I think some of the answers here suggest interesting topics, but not necessarily ones that are necessary or sufficient for a PhD thesis. Beating state of the art engines is extremely unlikely, but within the realm of possibility if you're lucky enough to come up with the right insight. Beating the state of the art would be something that would probably get you published in Science or Nature, which is a  massively higher barrier to clear than a PhD thesis.  
  > **username_8**: Haha, I saw you on the sidebar. :P  
  > **username_9**: The purpose of doing research is to **find out** if something is feasible. If we told you the answer what point would there be in doing a PhD?  
  > **username_0**: @BobJarvis-ReinstateMonica was I asking for an *answer* or just looking for guidance? There is a big difference there, I think it is reasonable to ask for other's opinion when you are not sure what to do/how to progress. As you can see many suggestions here are beyond amazing making me grateful for asking this.  
  > **username_10**: You've already received a bunch of great answers, some of which I could've posted too, so I'll just stick this in as a comment: find yourself a copy of Garry Kasparov's book Deep Thinking: Where Machine Intelligence Ends and Human Creativity Begins. It basically walks you through the history of computer chess, albeit on a pretty high level. Maybe you'll get some new ideas there, and if not, then it's a good book anyway. :)  
  > **username_11**: is 'username_0' a combination of 'lbra' and 'agile'/'antifragile' or something?  
  > **username_0**: It’s a combination of my first and last name   
  
  ---
  
  ## 8 answers
  
  ### Answer by username_19 on 2019-11-26. Score: 51 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_20**: for instance, on levels < 1500 stockfish seems to forget to recapture.  
  > **username_21**: 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  
  > **username_22**: Cool ideas! there are also works that look into the state space structure of the game, such as [sequencing chess](https://arxiv.org/abs/1609.04648), maybe ML approaches can prove useful there too.  
  > **username_23**: The Maia engine is exploring precisely this research, and indeed it is being done by PhDs, so that's a great idea you had, John!  https://lichess.org/@/maia5  
  
  ---
  
  ### Answer by username_12 on 2019-11-25. Score: 17
  
  You might be interested in [AlphaZero](https://en.wikipedia.org/wiki/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](https://science.sciencemag.org/content/362/6419/1140).
  
  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.
  
  > **Comments:**
  > **username_13**: 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  
  > **username_14**: 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.  
  > **username_15**: 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](https://en.chessbase.com/post/the-future-is-here-alphazero-learns-chess) 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 :-)  
  > **username_12**: @username_14 that's the Zero approach, which is not necessarily the best - both AllieStein and Fat Fritz use human-imparted chess knowledge.  
  > **username_12**: @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.  
  
  ---
  
  ### Answer by username_16 on 2019-11-26. Score: 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?
  
  
  ---
  
  ### Answer by username_3 on 2019-11-26. Score: 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.
  
  > **Comments:**
  > **username_5**: 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.  
  > **username_3**: 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!  
  > **username_5**: 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).  
  
  ---
  
  ### Answer by username_8 on 2019-11-28. Score: 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:
  
  Does there exist a good static_eval function that takes a (Position, PlayerTurn) and returns some Score? ¹
  Small changes in positions can often lead to massive differences in evaluation.
  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 by username_1 on 2019-11-25. Score: 4
  
  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?
  
  > **Comments:**
  > **username_0**: 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 @username_19) above. But none-the-less, here is a thumbs up :)  
  > **username_17**: 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.  
  > **username_1**: @Ivella I am assuming that you were the downvote. I wrote my answer BEFORE that was clarified. Note that the question was edited.  
  > **username_0**: @username_1, 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.  
  > **username_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.  
  
  ---
  
  ### Answer by username_18 on 2019-11-26. Score: 4
  
  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](https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/4935/5300)
  
  [This article explores the concept in RL.](https://science.sciencemag.org/content/362/6419/1140.abstract)
  
  
  ---
  
  ### Answer by username_5 on 2019-11-26. Score: 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.
  
  
  ---
  
  