Reading about how Google solves the translation problem got me thinking. Would it be possible to build a strong chess engine by analysing several million games and determining the best possible move based largely (completely?) on statistics? There are several such chess databases (this is one that has 4.5 million games), and one could potentially weight moves in identical (or mirrored or reflected) positions using factors such as the ratings of the players involved, how old the game is (to factor in improvements in chess theory) etc. Any reasons why this wou开发者_StackOverflow中文版ldn't be a feasible approach to building a chess engine?

Something like this is already done: it's the underlying concept of opening books.

Due to the nature of the game, computer AIs are notoriously bad in the beginning, when there are so many possibilities and the end goal is still far ahead. It starts to improve toward the middle, when tactical possibilities start to form, and can play perfectly in the end game far exceeding the capability of most humans.

To help the AI make good moves in the beginning, many engines rely on opening books instead: a statistically derived flowchart of moves, basically. Many games between highly rated players were analyzed, and recommendations are hard-coded into "the book", and while the positions are still in "the book", the AI doesn't even "think", and simply follow what "the book" says.

Some people can also memorize opening books (this is mostly why Fischer invented his random chess variant, so that memorization of openings becomes far less effective). Partly due to this, sometimes an unconventional move is made in the beginning, not because it's statistically the best move according to history, but precisely the opposite: it's not a "known" position, and can take your opponent (human or computer) "out of the book".

On the opposite end of the spectrum, there is something called endgame tablebase, which is basically a database of previously analyzed endgame positions. Since the positions were previously searched exhaustively, one can use this to enable perfect play: given any position, one can immediately decide if it's winning, losing, or draw, and what's the best way to achieve/avoid the outcome.

In chess, something like this is only feasible for the opening and endgame, though. The complexity of the middle game is what makes the game interesting. If one can play chess simply by looking up a table, then the game wouldn't be as exciting, interesting, and deep as it is.

Well, 4.5 million games still only covers a very tiny (infinitesimal small) fraction of all possible games.

And while you would have a large number of winning and loosing positions, that would leave the problem of reducing that to a usable set of parameters. A very old problem, with neural networks as a standard approach. But NeuralNets aren't winning chess tournaments.

This general strategy has been tried for a variety of games. Very often people generate a suitably large database of games by having the computer play itself. A quick internet search turns up http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf - which builds on previous work in Backgammon. In chess, brute force look-ahead is very effective for computers, though - and in general statistics is much more effective when you can mix in all of the previously known information about the problem, rather than trying to re-learn it from the data. I note that in this link the computer learnt what amounts to the evaluation function at the bottom of the look-ahead, not the whole process.

There is something similar that works very well in computer Go - the UCT method. It does not use a known set of games but instead plays a huge number of random games while keeping statistics which moves lead to higher ratios of wins. It does so starting from the current position.

The statistics are kept in a tree of moves (similar to one used in minimax) and influence the choice of the next random game to play - the moves with higher win ratios are chosen more often. The growth of the tree is also guided by the games - usually each game adds a leaf to the tree. This leads to the promising paths being explored more deeply.

I like the idea, but the analogy [with text translation] seems to fall short when considering that the context of a sentence in natural language requires much fewer elements than the context of a chess board position (even though the elements of such sentences, namely words, may come from of a bigger set than the elements of a chess game, namely the game pieces, knight, pawn etc.)
Furthermore, the availability of multi-lingual corpus (documents of various nature, in various languages) far exceeds the number of chess games which one may find in a digital form, in particular when considering that for chess analysis one needs the whole game whereby, for translation purpose, one can use every sentence independently from the rest of the text.

As a result, and with the possible exception of the opening portion of the games (when the board positions haven't had much opportunity to diverge relatively to other games), the number of chess games required to introduce some statistical significance would have to be astronomical...

Gotta run, but I'll be back with specific estimates on the number of possible chess games (in the absolute, and in the subset of plausible games), and should effectively prove that 4.5 million games is a relatively small sample.

There are approximately 10¹²³ game trees in chess out of which you have about 4.5 × 10⁶ in that database. We can ignore the game trees, and only consider state-space complexity of which there are anywhere between 10⁴³ and 10⁵⁰ legal states. Let's assume that all games in that database have unique moves, and that there are 1000 moves on average per game, which gives us 4.5 × 10⁹ states. Taking the estimated lower bound 10⁴³ of possible states, that only covers 4.5 × 10^-34 of all states. I don't know what is the total number of unique board positions that exclude rotations or reflections, but it will only reduce it by a factor of two or so, which is not very helpful.

You would need to add more domain knowledge into the statistical engine and find out the level of similarity between two given board positions as there is a 1 in 10³⁵ chance that you will not find a matching board position (including reflections and rotations). I think the biggest key here would be finding how how two given board positions are similar. That will incorporate a lot more domain knowledge than just simple transformations.

It is a great idea nonetheless that is worth exploring further, although I suspect that it has been tried before given the complexity of chess and the interest around it.

I would say yes, it could work. Nobody's really tried it successfully yet, but why not look for "patterns" using a statistical approach. I am not considering storing the whole board since there's astronomically many board positions to store, but merely looking for specific patterns.

Looking for Patterns

A typical chess program evaluates and gives bonuses for recognized patterns such as good defending pawn or an open rook line and on the other hand penalties for such as doubled pawns.

Such patterns could be programmed efficiently in 64-bit masks. You would have bit-masks for positions that matter and bit-masks for expected pieces in those positions. Each pattern takes time to match so it would be important to find the ones that makes a difference. That's where Google's statistical approach would be used. It could run through "historic" games and look for patterns. After it finds a pattern it would have to calculate a weight to the pattern and see if the improved evaluation outweighs the overhead.

I think this would be a rather huge project to try out, even too much for a PHD thesis.

Machine Learning has made big progressions lately, especially after the Google team beat the GO champion using ML. It has now also been demonstrated with chess. Take a look at the article in MIT technology Review, https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/

ML's Deep Learning is an enhancement to the old Neural Network self-tuning AI algorithms. Lai's demonstration didn't teach the machine the basic rules of chess or cared about the outcome of the games. He just fed the machine with a large database of games and the machine figured out the rest and played at a reasonable "human" level.

I assume two big enhancements would be to make it more efficient by teaching it the rules and then guide it by feeding it with the actual results of the games. Then after that go train with the current chess champions, engines like Stockfish! :-)

Deep Learning algorithm similar to the GO program that defeated the Master Human player might be killer. It would require a high cost though. However, one might use the learned deep learning patterns from GO and apply it to chess.

One thing I have not seen mentioned is consideration for the ratings of the players in games in your database. Some openings with good db percentages are a result of the better player tending to win and say little about the value of the opening.

In fact I have decided that databases are good for only one thing and that is indicating what moves are popular. Beyond that you are really stretching your interpretation of the data beyond what it merits.

Similarly computer analysis only shows the best result for computer vs computer games. Games between humans are different and you should not rely too heavily on computer analysis.

Both the database and computer analysis is interesting but they can easily be misinterpreted. Be-ware.

Chinmay,

I know this is an old thread, but it's a topic I've been exploring lately. Most of the people who answered above didn't really get your question. I think that, yes, it is worth analyzing numerous games in the past to develop suggested moves. Will it cover all possible moves? No, obviously not. But it covers all realistic moves from real games. A human (or another computer algorithm) would have to start playing very strange moves to throw things off. So, you can't build a 'perfect' algorithm that wins all the time, but if it wins a lot, say a >2200 FIDE rating, it's not bad right? And if you incorporate Openings and Endgames, not just rely on past move analysis, it makes it an even better engine.

There are an astronomically high number of possible board positions, but it is finite, and if you remove the stupid positions it reduces the number quite a bit. Is it possible to have 4, 5 or 6 of one players pawns lined up in the same file? Yes, would it happen in a real game? Doubt it. Include a basic Chess brain into your logic for situations where the opponent goes 'off book'. Micro Max is only a couple hundred lines of code for example. If the opponent has played stupid to thwart your moves, they are probably beatable by a simple engine.