4 ms·

I was thinking about this last week and maybe like to try some time. How does one start out?

pigscantfly 6y ago
I would check out Michael Genesereth's course on general game playing [1] -- I don't remember if we specifically implemented a chess engine, but it's more or less exactly what you're looking for. Once you've mastered that, I'd move on to Mykel Kochenderfer's series on decision making under uncertainty [2], which extends to more state of the art approaches to the problem (ie. MCTS + deep Q learning + better encoders, which is basically what got us AlphaGo, AlphaStar, Atari agents, etc.). Once you've got that down (or before), you should start reading whitepapers. Genesereth and Kochenderfer also have books on the subject; Kochenderfer's is extremely good (I haven't read all of Genesereth's). [1] http://ggp.stanford.edu/ http://ggp.stanford.edu/ [2] https://web.stanford.edu/class/aa228/cgi-bin/wp/ https://web.stanford.edu/class/aa228/cgi-bin/wp/ and https://web.stanford.edu/class/aa229/cgi-bin/wp/ https://web.stanford.edu/class/aa229/cgi-bin/wp/
dmichulke 6y ago
You need three things: 0. A function A(s) to generate actions (moves) A given a state s: 1. The state evaluation function v(s) to distinguish good from bad states. I would start by using only piece value, then add mobility, piece-field values, ... You can find a few simple elements of such a function here: http://manual.freeshell.org/gnuchess4/HEURISTICS http://manual.freeshell.org/gnuchess4/HEURISTICS With this you can generate s'=as (Successor state is action a applied to state s) and choose the action a=argmax(v(s)) 2. A simple minimax implementation that searches the possible moves https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Minimax From there you start optimizing your both by adding additional features to the evaluation function and improving your search using pruning and caching
- thom 6y ago
  But also think about all the potential projects that branch off this! Say you want to code your own eval heuristics... how can you find what's significant? Well, let's build a database of games and plug them all into a decision tree or something and see what rules are most important to work out winning or losing positions. Now, what if that database has 1.7B games and is 412GB, like Lichess's? And what if you want to search it fast? So many fun problems to solve!
  - dmichulke 6y ago
    And this only takes into account Chess. General Game Playing (referenced by a sibling comment) allows in its simplest version to encode all deterministic games with complete information (which is an infinite set but includes Rock Paper Scissors, Connect 4, Checkers, Chess, Go, ...). Now finding heuristics there given only the game description is a completely different set of problem but for quite a few Chess-like games it boils down to valuing pieces (proving that something is a piece is a problem by itself), positions and combinations thereof which again all are derived of "mobility", i.e., the number of possible moves in a given situation. In that sense, piece value is a mere "maximum mobility" indicator per piece. Positioning is a "real mobility indicator" but not only affecting your own mobility but also reducing your opponents. Check is then a mere reduction of your opponents mobility, promotion is a great enhancement of your piece value and castling a way of reducing the chance of "immobilizing your position" via check. TLDR: Machine Learning aside, you could also deduce all Chess heuristics from first principles.
thom 6y ago
The Chess Programming Wiki is one of the great wikis: https://www.chessprogramming.org/Main_Page https://www.chessprogramming.org/Main_Page

I would check out Michael Genesereth's course on general game playing [1] -- I don't remember if we specifically implemented a chess engine, but it's more or less exactly what you're looking for. Once you've mastered that, I'd move on to Mykel Kochenderfer's series on decision making under uncertainty [2], which extends to more state of the art approaches to the problem (ie. MCTS + deep Q learning + better encoders, which is basically what got us AlphaGo, AlphaStar, Atari agents, etc.). Once you've got that down (or before), you should start reading whitepapers. Genesereth and Kochenderfer also have books on the subject; Kochenderfer's is extremely good (I haven't read all of Genesereth's). [1] http://ggp.stanford.edu/ http://ggp.stanford.edu/ [2] https://web.stanford.edu/class/aa228/cgi-bin/wp/ https://web.stanford.edu/class/aa228/cgi-bin/wp/ and https://web.stanford.edu/class/aa229/cgi-bin/wp/ https://web.stanford.edu/class/aa229/cgi-bin/wp/

dmichulke 6y ago

You need three things: 0. A function A(s) to generate actions (moves) A given a state s: 1. The state evaluation function v(s) to distinguish good from bad states. I would start by using only piece value, then add mobility, piece-field values, ... You can find a few simple elements of such a function here: http://manual.freeshell.org/gnuchess4/HEURISTICS http://manual.freeshell.org/gnuchess4/HEURISTICS With this you can generate s'=as (Successor state is action a applied to state s) and choose the action a=argmax(v(s)) 2. A simple minimax implementation that searches the possible moves https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Minimax From there you start optimizing your both by adding additional features to the evaluation function and improving your search using pruning and caching

thom 6y ago
But also think about all the potential projects that branch off this! Say you want to code your own eval heuristics... how can you find what's significant? Well, let's build a database of games and plug them all into a decision tree or something and see what rules are most important to work out winning or losing positions. Now, what if that database has 1.7B games and is 412GB, like Lichess's? And what if you want to search it fast? So many fun problems to solve!
- dmichulke 6y ago
  And this only takes into account Chess. General Game Playing (referenced by a sibling comment) allows in its simplest version to encode all deterministic games with complete information (which is an infinite set but includes Rock Paper Scissors, Connect 4, Checkers, Chess, Go, ...). Now finding heuristics there given only the game description is a completely different set of problem but for quite a few Chess-like games it boils down to valuing pieces (proving that something is a piece is a problem by itself), positions and combinations thereof which again all are derived of "mobility", i.e., the number of possible moves in a given situation. In that sense, piece value is a mere "maximum mobility" indicator per piece. Positioning is a "real mobility indicator" but not only affecting your own mobility but also reducing your opponents. Check is then a mere reduction of your opponents mobility, promotion is a great enhancement of your piece value and castling a way of reducing the chance of "immobilizing your position" via check. TLDR: Machine Learning aside, you could also deduce all Chess heuristics from first principles.

thom 6y ago

The Chess Programming Wiki is one of the great wikis: https://www.chessprogramming.org/Main_Page https://www.chessprogramming.org/Main_Page