A purely self-trained chess AI

Question

Insofar as I understand, it appears that, before moving, all strong chess software

1. examines thousands or millions of possible, future positions;
2. evaluates each future position according to some heuristic, called an evaluation function;
3. separately evaluates each future position for quiescence, to decide whether to explore continuations from the position;
4. chooses from among available moves by minimax; and
5. uses an opening book.

So far, so good. However, the strength of a chess program seems mostly to depend on the quality of its evaluation and quiescence heuristics -- and also on its opening book which, from the computer's perspective, is yet another heuristic. Such a chess program apparently, only, exactly knows as much about the game as does the human who has crafted the heuristics. The program seems to have no insights of its own.

Has anyone ever written a chess program that does have insights of its own? That learns the game on its own? That trains itself? Such a program would be provided with the rules of the game, of course, and would presumably further be provided with raw minimax and quiescence infrastructure, and would be able to recognize and prosecute a forced mate if it found one. However, it would be provided no heuristics. For example, it would not be told to open the game toward the center, nor to prefer rooks to knights, nor what is the Sicilian defense. It would have to infer such principles (or, conceivably, to discover better principles) on its own.

In its pure form, such a program would never be provided master games to study, but only its own games, played against itself. Only once fully self-trained would it be unleashed on human competition.

Does such a pure chess AI exist? Has a mechanical chess autodidact ever appeared? Indeed, can the old Turk teach himself?

Here seems to be a brief notice of a pure chess AI that failed.

(A tangentially related question has earlier appeared on this site, regarding the computerized study of chess openings.)

UPDATE

The question is graced by three different, illuminating answers at the time of this writing, by @WesFreeman, @GregE. and @Landei. All three are strongly recommended and I am going to feel guilty when, according to site policy, I formally accept one to the exclusion of the others. Let me here give thanks for and express my appreciation of all three.

Questions want brevity. A response to answers however might run longer. The interested reader therefore can skip from here directly to the answers and then, if still interested, can return to read the longer update that follows.

When I asked the question, I had in mind something like the following.

Suppose a hypothetical village on the outskirts of Shangri-La where the people have never heard of chess. During your brief visit, you teach the village elders the rules of the game, but never instruct them in any of the game's principles. Two of the elders play a game as the rest of the elders watch, while you (not wishing to disrupt the play by kibitzing) confine your commentary to questions of the rules. No postmortem follows the game, nor is chess played or discussed again while you are remain in Shangri-La. However, when you depart, never to return, you leave your chess set behind.

In your absence, the elders teach the game to the people. Some of the people later play a little during leisure hours, a few with growing enthusiasm, who fashion chess sets of their own.

It might not immediately be obvious to such villagers that a rook were better than a knight, but the people might still gradually work out the relative strengths of the chessmen over the play of many games. Likewise, it might not immediately be obvious to them that 1. a4 were a poor opening: they could but try it and consider the results.

To what extent would the villagers' understanding of the game eventually converge to that of the outside world? Lacking an opening book, might they develop novel openings of their own? Of course, one would not expect the villagers' openings to be very good at first but, given a couple of centuries of isolation, the villagers might develop a respectable opening repertoire, for all I know.

Would any of their openings, independently developed, prove interesting to the outside world, when the next traveler passed through to take note of them, 200 years later? Might Shangri-La give the world the new, novel, Shangri-La Defense?

If so, then, with respect to my original question on chess AI, what I had in mind was more or less this: could a chess AI more or less duplicate the chess progress of the villagers on the outskirts of Shanrgi-La?

Considering Sussman's story in @Landei's answer below, it is undoubtedly true that my villagers would bring certain preconceptions to the game. For example, they would bring an understanding that to possess more of a useful thing were generally better than to possess less of it, and therefore that to capture an opponent's chessmen were probably, usually preferable to suffering the capture of one's own. How territorial the fictional people of Shangri-La were by nature is a question for literature, but one can assume that they would recognize a position that commanded more space as superior to a position that commanded less. And any bright novice, once shown a chess set and instructed in the game's rules, can infer that a queen is likely better than a pawn, simply by that the queen has up to 27 moves available, whereas the pawn has no more than four -- and moreover, by speculative inference against the game's design, by the observation that a player begins with fewer queens than pawns.

My question therefore need not be construed to imply an absolute, Sussman-style injunction against bringing any kind of knowledge whatsoever to the chess board; but rather to imply a general injunction against preconceived, chess-specific knowledge. After all (disregarding the matter of the evolution of the game's rules long ago), at some time in the past, the first game of chess was played. Maybe the first player did open 1. a4; but eventually he learned better, and taught what he had learned to his disciples; who in turn learned more and taught more, generation by generation, to give us Kasparov.

Could an AI not do something like that, only in weeks rather than centuries?

Plato would be skeptical, I suppose. Hume would be more optimistic, but the question is no longer to be settled by philosophy alone. We have electronic computers now with which to test the proposition, and I was wondering what the state of the AI art was. The best chess AIs at present seem to be thoroughly unintelligent expert systems that beat everybody while intuiting nothing. I wondered whether slightly broader AIs that, in some sense, actually think about chess, had had any considerable success at teaching themselves the game.

I gather that the answer is no, probably not.

Answer 1

You have some very interesting points. I have a bit of experience in AI research (my M.Sc. was in this field), so I think I can provide some insights.

Reasearch in the area

First, research in this field is certainly happening - searching for "evolutionary approach chess" came back with this paper from 2001, doing pretty much exactly what you suggested, leaving the min/max approach and only modifying the evaluation function. It's possible to dig up many more, and I'm aware of several people who were working in this field in general.

Theoretical possibilities

In my opinion, the only real limiting factor for the creation of a "pure" chess playing AI is computation time. There is absolutely no reason why such an AI cannot theoretically be created using current approaches.

Practicalities

There are two main problems with using evolutionary or genetic approaches in evolving a chess heuristic function, the first is that even at its most basic, a heuristic function for chess is hugely complex. We're talking hundreds of rules, piece valuations (which may differ based on position, etc), positional analyses, etc. You'd need a flexible computer language in which to describe these rules, and then these rules could be randomly generated, mutated, bred with each other, etc. It's certainly possible, but I'm guessing you'd end up with a rule set that is comprised of several thousand entities. That's a very large rule set to evolve dynamically.

The second problem is that to actually evaluate your newly modified rule, you have to play games of chess, and see who ends up winning. If you want to do this "correctly", you will want to give both players plenty of time to think, something similar to a typical game length. However, playing only a single opponent is not enough, you'd want to play many different opponents, and perhaps even the same opponents, many times, before you can truly be convinced that you have found an improvement in game strength. This would probably mean playing a couple of hundred games per individual in your population, and that gives you one generation of your algorithm.

Typically with these types of approaches, you'd be looking at least several hundred generations, or with such complex functions as a chess heuristic, several hundred thousand (or even millions of) generations. Some quick maths should convince you that you'd need several thousand hours of CPU time for a single generation, even scaling this out a server farm of significant size, you will probably need several (possibly hundreds) of years to actually evolve, exactly as you mention in your update.

At the end of that time, you'd have an interesting algorithm which would probably have tons of insights into the game which have never really been discovered. It's difficult to tell whether they'd be useful or even understandable to humans. Why does this rule exist? Because over several thousand games, it seemed to work.

Future

I have no doubt that these approaches will gain more an more popularity, as computing power increases. Currently, we're at a point where a machine has just enough computing time to beat (almost all) humans, if it's intelligence is carefully hand-crafted. In 20 years' time, it's quite possible that processors will have moved on so much that one or two extra moves in depth no longer give the "hard-coded" machines enough benefits, but are routinely beaten by evolved, strangely intuitive machines which have millions of hours of evolution behind them.

Update 2018 May

As Robert Kaucher mentions in a comment below, recent news deserves a mention here. Specifically, Google's AlphaGo project seems to be the first truly viable AI-based approach to these types of games, and in late 2017, claims to have won against StockFish 2, after being re-purposed for the task.

Answer 2

It's worth revisiting this question in light of the recent striking success of AlphaZero against Stockfish 8. A further evolution of DeepMind's AlphaGo and AlphaGo Zero programs, AlphaZero finished with a staggering score of +28 =72 -0 against one of the strongest "traditional" chess engines on the planet.

AlphaZero taught itself to play through reinforcement learning, training its neural network architecture through series of games against itself. According to the accompanying paper:

1. The input features describing the position, and the output features describing the move, are structured as a set of planes; i.e. the neural network architecture is matched to the grid-structure of the board.
2. AlphaZero is provided with perfect knowledge of the game rules. These are used during MCTS, to simulate the positions resulting from a sequence of moves, to determine game termination, and to score any simulations that reach a terminal state.
3. Knowledge of the rules is also used to encode the input planes (i.e. castling, repetition, no-progress) and output planes (how pieces move, promotions, and piece drops in shogi).
4. The typical number of legal moves is used to scale the exploration noise (see below).
5. Chess and shogi games exceeding a maximum number of steps (determined by typical game length) were terminated and assigned a drawn outcome; Go games were terminated and scored with Tromp-Taylor rules, similarly to previous work (29).

AlphaZero did not use any form of domain knowledge beyond the points listed above.

I'm sure one can raise questions about things like the differing hardware being used -- "AlphaZero ... used a single machine with 4 TPUs. Stockfish ... played at [its] strongest skill level using 64 threads and a hash size of 1GB." -- but in any case AlphaZero's result is a remarkable one, and very much in the vein of the OP.

Revealing perhaps even more support for how little domain-specific knowledge was at play, in addition to beating Stockfish in chess, AlphaZero also trained at shogi to the point of besting the champion program Elmo, and of course also surpassed its predecessor AlphaGo Zero in Go.

Here's one of the games against Stockfish, a Berlin in which the material imbalance is eventually AlphaZero with the bishop pair against a knight and 4 pawns for Stockfish after 31.Qxc7. In that position, all of AlphaZero's pieces are on the back rank, with the bishops back on their original squares. Ultimately, after the queens come off the black pieces slowly maneuver to pick up white pawns, and that's curtains.

[fen ""]
[Date "2017.12.04"]
[White "Stockfish"]
[Black "AlphaZero"]
[Result "0-1"]

1.e4 e5 2.Nf3 Nc6 3.Bb5 Nf6 4.d3 Bc5 5.Bxc6 dxc6 6.O-O Nd7 7.Nbd2 O-O 8.
Qe1 f6 9.Nc4 Rf7 10.a4 Bf8 11.Kh1 Nc5 12.a5 Ne6 13.Ncxe5 fxe5 14.Nxe5 Rf6 
15.Ng4 Rf7 16.Ne5 Re7 17.a6 c5 18.f4 Qe8 19.axb7 Bxb7 20.Qa5 Nd4 21.Qc3 
Re6 22.Be3 Rb6 23.Nc4 Rb4 24.b3 a5 25.Rxa5 Rxa5 26.Nxa5 Ba6 27.Bxd4 Rxd4 
28.Nc4 Rd8 29.g3 h6 30.Qa5 Bc8 31.Qxc7 Bh3 32.Rg1 Rd7 33.Qe5 Qxe5 34.Nxe5 
Ra7 35.Nc4 g5 36.Rc1 Bg7 37.Ne5 Ra8 38.Nf3 Bb2 39.Rb1 Bc3 40.Ng1 Bd7 41.
Ne2 Bd2 42.Rd1 Be3 43.Kg2 Bg4 44.Re1 Bd2 45.Rf1 Ra2 46.h3 Bxe2 47.Rf2 Bxf4
48.Rxe2 Be5 49.Rf2 Kg7 50.g4 Bd4 51.Re2 Kf6 52.e5+ Bxe5 53.Kf3 Ra1 54.Rf2 
Re1 55.Kg2+ Bf4 56.c3 Rc1 57.d4 Rxc3 58.dxc5 Rxc5 59.b4 Rc3 60.h4 Ke5 61.
hxg5 hxg5 62.Re2+ Kf6 63.Kf2 Be5 64.Ra2 Rc4 65.Ra6+ Ke7 66.Ra5 Ke6 67.Ra6+
Bd6 0-1

Answer 3

I suspect that what you're asking about would be classified as some sort of genetic algorithm or evolutionary algorithm approach. I suspect there's no realistic way of designing such an algorithm without intrinsically embedding some degree of human bias at a fundamental level, since the programmer still has to define the static features of a position (material count, pawn structure, color complexes, etc.) according to which the AI would classify and compare positions from different games. If you do a Google search on the above algorithmic terminology in the context of chess, you'll find numerous results, but probably little in the way of serious research that has actually been used to build successful, competitive AIs.

The fact is that, as a consequence of Moore's law, computers are now such powerful calculating machines that extremely sophisticated AI methods are not only unnecessary (in terms of playing at a level higher than the best human opponents), but can even conceivably be counter-productive. Chess is the kind of game in which -- due mainly to its comparatively small search space of reasonable moves in any given position and the existence of forcing tactical combinations (comprising sequences of checks, piece captures, threats of mate or catastrophic loss of material, etc.) -- a brute-force approach with some conservative search-tree pruning is simultaneously the most algorithmically simple and the most effective approach. If you factor in the availability of endgame tables and opening books, the logic of that approach only grows. I understand that there's a still a great deal of theoretical interest and potential value in the sort of novel AI that you're talking about, but I suspect chess is the wrong arena in which to develop it. On the other hand, a game like Go, which is less tactical by nature and encompasses a vastly larger search space that renders brute-force approaches impractical, might be a better candidate for cutting-edge AI research.

Answer 4

See Wikipedia's page on General Game Playing. It's an active research area. There is an annual GGP tournament in which programs are given the rules of a new game, get to think about it for a while, and then play the game against each other.

If you give the rules of chess to a GGP program, I think you'll find that it plays much stronger than a human beginner and much weaker than a purpose-written chess program.

Answer 5

Please meditate about the following AI Koan:

In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6. “What are you doing?”, asked Minsky. “I am training a randomly wired neural net to play Tic-Tac-Toe” Sussman replied. “Why is the net wired randomly?”, asked Minsky. “I do not want it to have any preconceptions of how to play”, Sussman said. Minsky then shut his eyes. “Why do you close your eyes?”, Sussman asked his teacher. “So that the room will be empty.” At that moment, Sussman was enlightened.

Our applications have always preconceptions, whether or not you close your eyes...

Answer 6

I think the main reason it's difficult to produce such an AI is because of the space required in storing the "training" to be effective.

Also (as a response to your self-training comment), self training can be detrimental while trying to improve such an AI--I've done some research with tic-tac-toe (admittedly much simpler), and it found all sorts of horrible ways to win (and train those horrible ways) because both sides played horribly. It took much much longer to get reasonable performance with self-training than training against a good look-ahead AI in tic-tac-toe.

However, I think it would be interesting to see a hybrid that uses both deep search and "training"--some sort of stored database of positions for middlegame (instead of just endgame and openings). It would need a lot of space.

Maybe you're thinking of a more "real" AI approach that would learn positional concepts rather than position win/loss/draw, but I don't think that would be very effective (compared to strong engines).

Answer 7

I just want to expand on Greg's and Wes' answers here. The sort of AIs that thb is proposing simply do not exist with the sophistication that is required for this application. And even if they did, I suspect they would fail at this. It's as if thb wants a strong general purpose AI that can be taught the basic rules of the game and then be sent forth. But if you look at the general purpose AIs that are in development they are all being taught things like object and speech recognition at a 1 to 2 year old's level. Any general purpose AI would first need to have the sophistication to be able to understand what a game even is before it could understand how to play a game. You cannot design a general purpose AI and expect it to perform like a narrow or specialized AI. A general purpose AI would need to be taught chess like a person and you cannot expect to put two novice players with no knowledge of chess history together and spontaneously reinvent openings and strategic themes. It would take many hundreds of instances of the AI playing each other, each with access to the historical data of all of their games over many hundreds of thousands of iterations. And each AI would need to have certain distinct characteristics weighted at different levels.

It took humans nearly 500 years to get from Rodrigo (Ruy) López de Segura and Pedro Damião to Paul Morphy and then consider the further changes that occured between the play of Steinitz and Alekhine. And all of that change occurred through the dynamism of many hundreds of thousands of players with different temperaments and other influencing characteristics (such as randomly favoring knights over bishops or bishops over knights) not to mention playing styles and fashions. All of these things contributed to the dynamo of change that influenced chess through the centuries. No weak AI - even a weak general purpose AI- could duplicate that sort of dynamo because it lacks desire. Only desire can drive something to sit for hours over many days to analyze an opening with the intention of busting it or improving it after a rival "busted" it. Really it's this sort of drive for analysis and preparation that improved play over the centuries - not blind play of million of games between equally weak players.

It's like taking a bunch of people who do not speak English and who never read their native tongue's masters of literature and putting them into a room with English as a Second Language books and expecting them to come up with something like the works of Shakespeare. It's never, ever going to happen.

EDIT: I should have known better than to make this claim because it has happened.

“AlphaZero was not ‘taught’ the game in the traditional sense,” explains Chess.com. “That means no opening book, no endgame tables, and apparently no complicated algorithms dissecting minute differences between center pawns and side pawns. This would be akin to a robot being given access to thousands of metal bits and parts, but no knowledge of a combustion engine, then it experiments numerous times with every combination possible until it builds a Ferrari. … The program had four hours to play itself many, many times, thereby becoming its own teacher.”

My continued, obviously baseless blathering:

We take for granted all of the implicit knowledge that we have about the world. In order to be able to understand that if I have to pieces of wood and a nail, then a hammer is more useful to me than a screwdriver I have to first understand that certain classes of things are more useful in certain situations than other things. I also have to understand that things have a use that can be applied to a goal. These are heuristics. If the AI cannot be told that certain pieces have more value than others, how can it even understand what mate is? If it cannot be programmed with specific heuristics, it must be able to extrapolate these ideas like "value" and "utility" form experience. And that is not the domain of narrow AI. It's the domain of general purpose, strong AI.

Answer 8

Has anyone ever written a chess program that does have insights of its own? That learns the game on its own? That trains itself?

Yes. Check out the Giraffe chess engine written by Matthew Lai. He wrote the chess engine as part of his Artificial Intelligence research for a masters degree in computer science.

There was a lot of discussion about this last year on the TalkChess chess programming forum. I know because I am a chess engine author whose engine is roughly as strong as Giraffe. However, I implemented my engine using traditional techniques whereas the author of Giraffe trained his engine using "temporal-difference reinforcement learning with deep neural networks." Matthew still had to implement traditional alpha / beta search to dynamically evaluate a position- in other words, to look ahead many moves. His innovation is in training the engine to evaluate a static position. In comparison, I wrote specific knowledge into my engine's static evaluation routine.

I wrote code to tune evaluation parameters using a particle swarm algorithm (see Thank You page on my blog for links to technical discussion) that did yield positive results- a stronger engine. However, this wasn't a task of getting the engine to "learn" so much as minimizing error in an extremely large space of evaluation parameters (the order of 10 ^ 150 discrete parameter combinations).

Matthew discusses his dissertation on the TalkChess forum. He works for Google on DeepMind now, if I remember correctly.

Also, check out Thomas Petzke's blog. He has written an extremely strong chess engine, iCE, and used genetic algorithms to improve the engine's static evaluation. See his posts from 2013 and earlier, such as Population Based Incremental Learning.

Answer 9

A Google search like this can turn up results like this.

Most particularly, I believe you will want to look at this paper. They do give their engine some initial data such as piece values, so it's not exactly what you're asking for, but it performed quite well.

Answer 10

It's possible with machine learning.

Opening books of chess engines use machine learning. Engine tests opening lines in the book by playing them, if a line scores better comparing another, then it promotes that line in the opening tree. In time, engine learns the better lines.

After opening phase ends, engine stops using the book, and starts using evaluation function.

---

How to implement a self learning engine using machine learning?

Imagine an engine using a book without an evaluation function. And the book is empty initially. So engine has no knowledge about chess.

Engine starts to play with this empty book, and doesn't close the book until the end of the game. We can think it like a regular engine which uses an opening book till the end of the game.

In time, engine would find best continuations statistically, as bad lines will score worse in time. But of course, a lot of games should be played to obtain a good book. I don't know how many, but as many as we can say impractical.

December 2017 Update: Well, I guess Alpha Zero proved me wrong by training itself strongly enough to beat one of the strongest engines, Stockfish, with a practical amount of games.

Answer 11

Whatever you try in this area, be sure to read first Turry's story here: http://waitbutwhy.com/2015/01/artificial-intelligence-revolution-2.html

TL; DR; spoiler version per request:

In Turry's story Turry's self-training AI has to write nice handwritten notes and end ups getting rid of humans because they are not needed to achieve the apparently innocuous goal of writing nice handwritten notes. The analogy is that a self-trained chess engine with AI most likely will also get rid of humans because they are not needed to improve the apparently innocuous goal of improving chess skills.

Answer 12

And there is AlphaZero. Celebrate a whole new generation of chess engines

Answer 13

The use of anthropomorphic terminology when dealing with computing systems is a symptom of professional immaturity

From How do we tell truths that might hurt? by Edsger W.Dijkstra pretty much sums up the mistaken assumption underlying your question. Artificial Intelligence may be artificial but it is not intelligence in the human sense.

In the 1984 Reith Lectures for the BBC the American philosopher John Searle explains exactly what is wrong with hard AI. The "too long, didn't listen" summary of his argument is "Syntax is not semantics" but I would nevertheless encourage you to at least listen to lecture 2 "Beer Cans & Meat Machines".

Once you've grasped what Dijkstra and Searle were saying more than 30 years ago you will recognize what is wrong with your questions:

Has anyone ever written a chess program that does have insights of its own? That learns the game on its own?

Human beings have "insights" and can learn. Computers can not. Your village of primitive humans could over the centuries reproduce chess opening theory but computers not.

Answer 14

This answer is given by the asker of the original question, four years after the question. It does not substitute for or supersede answers earlier given, for most of the earlier answers are more interesting than this one is. However, this answer might add some additional context.

As far as I can tell, most AI research seems implicitly to grant the premise that thought and reason were solely material phenomena, or at least that results indistinguishable from thought and reason must necessarily be achievable by solely material processes. I do not dispute the premise (nor here promote it, for that matter). I merely observe that it seems to be a premise.

And, after all, in AI research, how should this not be a premise? AI researchers must work through material processes, whether they will or nill.

The schoolmen of realist philosophy, back through Duns Scotus, St. Thomas, Aristotle and Plato, have had much to say regarding the theory of mind. Representationalists like Kant have had rather different things to say. AI research is probably closer to Kant, but this does not make the schoolmen wrong.

Admittedly, there is a God-of-the-gaps objection which tends to pop up at this point in conversations of the present kind, yet a professional philosopher would tell you that the God-of-the-gaps objection attacks a straw man, that this objection tends to be useful only against persons who have studied no philosophy and thus do not know what they are talking about. Per Aristotle, it is formal and final causation which might be implicated in the question of the self-trained chess AI. Yet in Aristotlean terms, the AI researcher works purely with material and, especially, efficient causation (except perhaps obliquely, insofar as human trainers personally bring formal and final elements into the system). If reason is formal, if thought is final, if Searle's Chinese room proves to be an ontological impossibility (as it might), then it may be that a purely self-trained chess AI cannot even in theory be achieved.

I suspect that a purely self-trained chess AI can be indeed be achieved, and will be—that, in Aristotlean terms, this question will prove to be adequately framable in view of merely efficient causation. I am more skeptical of strong AI generally, but these are to be proved in experience, are they not? No one really yet knows.

The philosophy of causation and mind is subtle, grasped by few (and probably by few, even among AI researchers, who are more practical men). If you wish to learn such philosophy, it is well worth the learning; but be advised that, on the Internet and even often in print, it is extremely easy to find misleading explanations based on untutored misunderstandings. For my money, the best introductory teacher writing today on the subject is Edward Feser, whose books remain in print at reasonable prices. You can learn much more from him.

However, one doubts that even Dr. Feser would venture an authoritative answer on the present question! The answer remains to be proved in the laboratories of AI.

Answer 15

I want them to release the code, then we can talk. It is not that easy to solve chess, Alpha will not solve it even in half a century. Funnily, it still plays 1.d4. Why? Because it has been trained on human games and human theory gives highest performance rate for 1.d4. The poor thing does not know 1...c5 achieves a draw in precisely 8 moves. Now they want me to believe Alpha did not use a simulated opening book... They say Alpha played openings great. Well, yes, with some exceptions. 1.d4 certainly does not speak well of the level of intelligence the program attained. Luckily, SF is even weaker in the opening stage. :)