3 ms·

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 st

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

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.