Suggestions for a dissertation

[James Constance]

Hi all

I've just finished my second year of a Computer Science degree and need to come up with a topic for my final year's dissertation. I'd quite like to do something chess related, but I'm not sure what a suitable area to focus on would be. My supervisor has some expertise in pattern recognition, so I thought perhaps there might be something there. I'm also quite interested in the idea of quantifying how difficult a move is to find for a human, which could perhaps be used in computer annotation of human games or to identify cheating. However, I don't have much prior experience, so I'd like to aim for something that is doable. I haven't yet written a chess engine.

I'm sure a lot of you have already done something similar while studying, so I'd really welcome any suggestions that you have.

Thanks

James

[jdart]

I have not seen a really good theoretical or practical treatment of book learning.

It is complex because by the nature of it you are operating on imperfect information. You can know certain things about book moves: eval (up to some limit of depth), historical success rate, frequency of play, how recently it has been used and by what strength of player, etc. But this knowledge is still limited and it is incomplete because typically at each node there are possible moves about which you have no knowledge.

A good algorithm would make maximal use of the available information to determine a best move, ideally taking into account the rating of the opponent (and thus favoring a draw against higher-ranked opponents). It is also interesting to consider weighting higher moves that require the opponent to find a tricky countermove, so that there is more likelihood for the opponent to go wrong. A statistical analysis that backed up a proposed algorithm would be valuable.

Another topic is offline learning: if you have available CPU cycles and you want to extend the knowledge on which the book is based, what is the best way to do offline analysis or game play so that you improve the book?

Bob Hyatt did some fairly elaborate stuff in Crafty at one point (https://www.cis.uab.edu/hyatt/learning.html) but it did not address all these areas.

--Jon

[dkl]

How about making an engine play "human", especially adapting to the skill level of the player to make a challenging yet fun-to-play opponent?

I think this would be a broad-enough and challenging enough problem, to tackle both from a HCI perspective (i.e. is perceived "unhuman" when playing against chess engines?), over pattern recognition (identify "human" patterns in chess by e.g. mining large databases) over machine learning (i.e. deep learning how to play "bad", adapting a Google/GO like approach)...

should be way enough for some publications...

[Henk]

What about "Playing games using fuzzy transposition/hash table". But how much time do you have available and how much time may it cost you to write an engine. But of course also possible to start with a simpler game.

[James Constance]

Thanks Jon, Dominik and Henk for your ideas. They are very useful for giving me an idea of the kind of things I might be able to do. Food for thought!

[mjlef]

Fortress detection and avoidance is an area chess programs have failed in real games, including TCEC games. They just do not understand them. Some advancements in this area could benefit the computer chess community.

[smatovic]

What about an explanation why techniques like Lazy SMP, Jabot, Nagging,SPAM outperform classic parallel search algorithms like YBWC etc.

--
Srdja

[Evert]

Better opponent modelling for human play would be an interesting topic.

My son is learning to play chess, and I sometimes play with him. This is tricky, because he actually doesn't play with a clear plan and doesn't yet have a full view of the board (his vision is too local). He also doesn't think very far ahead.
When I play with him, my task is to try to create interesting situations where he can win something if he pays attention (forking a queen, for instance). This is sometimes very hard, and it is something that computers are completely unable to do. Some sort of scheme that finds the move that is optimal for human learning rather than the best move for winning the game would be very interesting.

There is of course also Deep Learning, which has been somewhat applied to chess evaluation but can be explored more.

[Aleks Peshkov]

I agree that opening book learning is important but yet unexplored topic.

[Rein Halbersma]

I agree that opening book learning is important but yet unexplored topic.

Thomas Lincke (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich,
http://e-collection.library.ethz.ch/ese ... 905-02.pdf

His dropout-expansion method is now the standard approach in computer checkers/draughts, and it should generalize to computer chess as well.