An Introduction to Artificial Intelligence and Deep Learning in modern chess
There is a strong need to re-invent the chess computer, and all (gaming)-computers for that matter, since they are programmed by human beings and not by computers themselves.
- Bendix Perschk, M.Sc. Economics, Münster University, Germany.
Good evening ladies and gentlemen, (please don't pronounce this in the voice of the Joker )
I would like to share with you my insights on Artificial Intelligence in chess computing. My Name is Bendix Perschk (finde me on facebook) and message me or feel free to comment here if you would like to add to the discussion.
Also: I myself am a quiet strong Bullet player, and my brain needs constant food That's why I am not the greatest fan of slower time controls. Feel free to challenge me to a game any time I am online. (FunnyFighter)
I have decided to write about this topic, because a vast majority of technological advancements will stem from artificial intelligence and deep learning processes.
In the following, "Artificial Intelligence" (A.I.) will be defined as "Software that writes its own updates". The chess world is in need of such a software as proven below.
There are already multiple possible apllications in Industries, including
- Automatization of processes: A.I. increases business efficiency. There is software like RESPONSE that analyzes the content of E-Mails before reading and puts it in different folders. This facilitates data flow for the co-workers, as they can directly view the folder "sales on 19th of June 2017" and simply saves a lot of time. Recurring day-to-day activities, like saving the address of the new colleague, transferring orders or invoices to the appropriate business site, handling our smart-phone via voice-recognition software, is handled by A.I.
- Predictive Analytics and Investment-Forcecasting: A.I. allows to recognize patterns much faster than the human brain. The easiest example would be to invest in a given stock/fund/portfolio, when the standard deviation of risk doesn't step over a certain bound, say 1/2 of standard of the mean of all investments. Also, new costumers to your business can be categorized and matched with pre-existing offers in your company just by analyzing their profile beforehand.
- Chatbots and Self-Serving Systems: Most chatbots in the past have been especially this: Stupid. Talk with any Tamagotchi and you will be bored after 10 minutes. Why? No chatbot until know was capable of changing from its core messages like "Hey how are you". Maybe after talking to one for 3 days you will get a "You are a cool person" as a bonus. What's greater than a smiling Tamagotchi?
No but honestly, there were no improvements, no advancements, in the "character", the personality, of the chess bot over time. Now there are messenger bots like the shopthewall-bot: Just search "shopthewall" in your regular facebook messenger program and click on the app. Here you have a great number of options readily at hand.
a) You can then send photos in the chat, and the facebook-bot will link you to online retailers where you buy the object identified in the photograph.
b)You can also type words like "jacket" and the app responds and tailors a list of jackets that you might want to buy. If you click on one, you can either buy it directly, or if you feel like you want to keep searching, the messenger will construct for you a list of jackets that match the one you last clicked on in terms of colour, size, price and other parameters relevant to your seach. A.I. in chess bots already exists and is accessible to everyone!! However, such trends usually take time for the public to be recognized and used.
The list goes on and on and thing like "Big Data Analytics", "Language&Pattern-Recognition" etc. could be added.
Intermediate result: A.I. is the future. More and more companies use A.I. in various vields every day. A.I not only faciliates work processes, it can also get rid of them: Who needs a taxi driver when you have self-driving cars? Who needs a secretary when you can tell your Smartphone to invite Mr. Smith to congress? A.I. can therefore be potentially very dangerous to many jobs. I will leave this point open to discussion in this threat.
However, the above given A.I. applications have one major flaw: They do not write their own updates and therefore they do not fall in the above given definition.
In chess, software that writes its own updates can well be programmed. (My own background is not programming, although I have constant contact to professional programmers). First, a mathematical approach to A.I. in chess will be presented. Second, the necessity for A.I. in chess will be explained. This essay concludes with an outlook to chess computer artificial intelligence in the future.
Artificial Intelligence in Chess
Chess is by far not the first game in which A.I. has been used - in Go, the software AlphaGo based entirely on big-data-analytics (going through hundreds of thousands of games) in combination with a self-learning software (approvement by factor k of the engine after every game) has won against world No. 1 of Korea, Lee Sedol.
Just think of the software AlphaGo as a tool that analyzes game after game after game and picks out "the good stuff". That could be a move combination that wins in 80% of all Go Games analzed or an opening that leads to very good results. By nature, computers will recognize far more precisely than humans. There may be good moves recognized by the computer but completely neglected by us humans. Thus, there will be a lot of paradigm shifts: New Variations suppused to not be playable by humans suddenly get relevant as the computer analyzed the variation thousands of times and says that they are playable. I appreciate the counterargument, that unlike the computer, human beings do possess intuition and therefore can rightfully discard some trash variations right from the beginning. It is almost impossible to programm an "intution" into a computer, since intution relies largely on emotions like fear, and computers don't currently have emotions.
But let's turn back to the incredible progress that AlphaGo has used:
By intuition, it can be deduced that k decreases after every game analysed, say by m. m may be interpreted as the information that the software already posseses.
All calculations are, of course, only true if each game analysed offers the same "information" to AlphaGo. This in itself is a useless assumption: When AlphaGo analyses a game of a player with the highest Dan (Rank in Go), the tactics, strategy and game approach (opening, middle game, endgame, attack, defense), that are analzyed, offer a very high improvement k, while the programm won't learn a lot from two beginners who randomly place their stones with one of them winning!
However, if you a) allow the program to run through games of grandmasters who are at a certain level, b) offer some programmatic rule for ignoring moves which are obviously losing (equivalent to sacrificing the queen in chess without any compensation) and c) programm strongly towards pattern recognition, so as to only "learn" of positions where patterns have not yet been seen before, then you can enhance k greatly. When t expresses the time, i.e the particular game studied, then the total amount of information gained can be expressed as
Total Information= x * (k-m)t
Where x is some number/coefficient. Using standard econometrical methods, x can be estimated by using the ordinary-least-square-approach (OLS), minimizing the variance [so (k-Trendt)^2] of the trend line explained by x or another likewise estimation method. For instance, it is almost certain, that the Information gained from each game will be decreased by m, where m increases over time.
That is, the A.I. learns how to put your pieces on the board of day one (Go or Chess doesn't really matter for argument sake), how to win on day two, and on day three you learn how to play just a little bit better, but not comparable to the increase in knowledge in day two. Obviously, k was smaller on day 3 than on day 2.
One could then go ahead and model the Information as a quadratic equation... At some point, m will be so big (thus k - m very small) that it almost won't improve the strength of Alpha go at all. The points k will thus be in some concave form when dt/dk > 0 but dt^2/d^2k <0. However, we should all agree that if a completely fresh chess/go position is analyzed, say Carlsen-Kramnik in Altibox, the A.I. should learn something form it, right? Some trick, some tactics, some positional consideration. k is therefore never 0!
The aim of this essay is to show that there is always some k, which can only be detected by Artificial Intelligence, not however by standard Programming.
The known results of "Standard Programming" include the classifical heavy weights in chess programming, such as
Now think of k in terms of chess.
Chess programming has clearly reached its bounds in Elo Strength. Houdini is rated at 3100 Elo. Question: Why is not rated 3500? Or 4000? Or Inifinity? If it always wins, it should be Inifinity. Why is that not the case?
Lay aside the point that in chess some games are always drawn and focus on programming errors - invert the argument, you get that programming errors lead to games lost. Games drawn are thus just results of incorrect programming. A.I. can help to overcome this inperfect programming!
Calculation power clearly is not a problem. You can basically turn the switch to "infinite" by simply adding 10 000 super computers to your Stockfish Software. Stockfish will still not be unbeatable.
To be more precise: It will perhaps be unbeatable, but it will definitely still miss some variations that A.I. won't miss, and that is provable.
In terms of the accuracy of programming that human beings are capable of carrying out, there is a clear limit. Consider the following examples.
So basically, there are inherent errors in the programmation of chess-supercomputers on all level of play. Stockfish relinquishes his chance to win against me in post-game- analysis. Nakamura exploits a 50 move - draw rule. But are computer errors only present in full games? Surely, with limited amounts of pieces on the board, say in endgame compositions, supercomputers calculate everything and therefore are unbeatable?
Wrong. Let's take a look at this third example.
This is clearly a positional draw, irrespective of which side moves first. White can not force stalemate nor perpetuals, meanwhile black cannot get at the white king. White would simply move his King aroung no matter what black does. If black pins the knight, the king just goes back to d8. Yet Stockfish gives -7.6 for black. The computer cannot evaluate this simple endgame correctly. Once again, an A.I. would look at this and instantly shout out: DRAW!!
- A.I. acknowledges the true result of a game, while conventional chess computers don't.
It goes on and on. Even conversion fail to be calculated exactly by the computer. Please run the following example through your chess engine (black to move):
In the above example, if black play ...b1=Q??, white has a stron reply in Qh3+! Drawing. Instead, black has to play ...b1=R!! mating in 15 moves, irrespective of White does. Once again, the A.I. is deeply learning: Just feed this position once to your A.I. computer and it will never commit to converting to a Queen again. It will forever be recognizing these positions without even thinking; just by pattern reconignition. Imagine, how strong it could be.
My last point if you still think that supercomputers are unbeatable is this:
Why do table bases exist? For people new to chess: A table base is a software that "knows how to win be heart" when there are very few pieces on the board, say 9 or less. It basically just knows the naswer without having to think.
Of course table bases only exist to tell the computer how to solve endgames without thinking (=calculating), thus they exist to tell the computer how to win when he can't win on his own anymore!!
I am convinced, that with A.I. also table bases become completely redundant. The A.I. will just incorporate all positions possible into its own mega data-base and therefore has an "integrated table base."
" A perfect chess player plays against a perfect chess player. Since both play perfect chess, the game should end in a draw. But a perfect chess player who draws against ANY other chess player is not a perfect chess player."
This is the kind of paradoxon that we have dealt with here. A perfect chess player, i.e. the machine, might win against all human beings. He might also win against other machines. Reasons are
a) Higher calculating power
b) Software better programmed
c) Fewer glitches in the programming powers.
Point a) is just a question of money. A millionaire with a nice computer will win against an average income person with the same software but a lame PC. Further, b) will always be answered by people who are far smarter than me, i.e. programmers. They can sit down, add some code, and make the program "better". The code will be more precise. I get that. But I am sceptical over discussions on point c):
Will it be possible to program chess engines so that there are no glitches whatsoever? My stance: Definitely not. Rybka played the Grob with 1. g4 (Will it even ever know that this move is bad?) against Nakamura, achieved an equal position, yet lost. Notice how the stupid machine doesn't even realize that it commited to an opening mistake - playing a dubious flank opening. It doesn't learn from its own mistakes. It doesn't update itself upon them. The position has closed up, and in order not to draw via the 50-move-rule, the program collapsed.
So, the obvious argument that people have been suggesting is this:
"Well, Rybka has to programmed in a way such that there are no closed positions, and therefore the 50-move-rule will never be an issue."
- Yeah right, but what about playing 1. g4?
"Well, you can tell Rybka not to play 1. g4 but always go 1.e4 instead. Very easy, mechanical-type programming. Not a biggie."
- Sure sure, but that's how an A.I. works. Only difference is, it tells itself not to play 1.g4 - it thinks for itself. But let's assume Rybka is programmed in the traditional way such that it always goes 1. e4, never blunders, always plays perfectly. -->
Okay, then I guess Rybka will be unbeatable. But wait, what about the positional draw I have shown above? The one with Que knight and pawn. Rybka shouldn't ever lose, so it shouldn't allow for White to draw positionally. This is when people get really impatient:
"Well, Rybka has to be programmed just a bit better, really not a big deal, just so that it detects positional draws from far away, avoids them, and wins at the end."
-Okay, now Rybka must be unbeatable! Right? I mean, no positional draws, no 50-move-glitch, nothing! A perfect machine, that wins everytime it plays a game of chess...
Or does it? A simple philosophical approach will answer this question very quickly with NO! Because when Rybka plays against itself, you can only have 3 results: win, draw, and loss. So one of the two engines is bound to commit an error. If Rybka 1 playes against Rybka 2 and wins, then Rybka 2 has commited to an error. The same holds for a draw. A draw is clearly imperfect. There was something, some detail, some nuance, not even visible for the computer brain (let alone the human brain), that it missed. But it has missed it.
I urge my entire generation to rethink the role a computer partakes. Aritifical Intelligence Software has at all costs to be applied!!!!!!!!!!!!!!!!!!!! All costs is meant literal.
A.I. can actually learn. It can update itself. When it loses against Rybka, if it plays the exact game again. The next time it will win by switching to a better move at some stage of the game. In the most extreme case, it will stop playing the grob. Something which I hope we can all agree would be a good idea. It improves upon itself, without human inteference. Rybka will never stop playing the Grob, not in a million years it won't, if nobody tells it to. With each game that AlphaChess plays, there still is some factor k, that cannot be detected by human beings.
When there is no factor k, then there is no improvement - the machine is unbeatable. Simple.
But there is some factor k, some improvement, and as long as it exists we have to rely on that mysterious technology called artificial intelligence that detects it. A technology that looks at two perfect players drawing at each other and that then says: "Ohh, that's were they went wrong." Then it plays one of the perfect players and wins.
The machine wrote its own software, and wins against software coded by human beings.