Computer Chess: How It Thinks!

hello and welcome to our science webseries brought to you by science hope comm today we'll learn about the concept behind computers chess game it's basic algorithm and logic a human chess player starts with very limited abilities each defeat comes as something of a surprise and learning for a human being therefore the game of chess involves a great deal of high-level abstract thought visual pattern matching to recall board positions rules and guidelines conscious thought and even psychology computers do none of this chess requires intelligence and thought process so how can the computer possibly do it a computer that is playing chess is not thinking instead it is calculating through a set of formulas that makes it to take good moves let's go through this step by step step 1 constructing a tree let's say you've chess board set up with each player having 16 pieces and it's computers turn playing with white pieces now the computer can make one of 20 possible moves to each for the eight pawns plus two each for the Knights and in response to any of those moves the opponent can make twenty possible moves so with starting two moves into the game we have 20 times 20 equals 400 possible set of outcomes let's assume that the computer has 20 ways to respond to that opponent's move to each of these 400 scenarios which makes 400 multiplied by 20 available legal moves at the end of the third move this way the process will go on it thinks about it in the world of all possible moves up to its program depth and it makes a big tree for all of those moves in theory the perfect computer would be able to get to the very bottom of this tree and look at all possible configurations of the board approximately 10 to the power of 120 then it would see which are the paths down this tree that lead to its victory and choose accordingly step 2 evaluating the outcomes there is a big problem 10 to the power of 120 is a very huge number for example there have only been 10 nanoseconds since the Big Bang there are thought to be only 10 to the power of 75 atoms in the entire universe when you consider that the Milky Way galaxy contains billions of Suns and there are billions of galaxies you can see that that's a whole lot of atoms that number is dwarfed by the number of possible chess moves we'd be sitting around waiting for the damn thing to make its move tell the universe ended so what real computers do is build up this tree to the best of their hardware capabilities 5 10 24 whatever moves into the future once they have this limited tree they evaluate each position using an evaluation function for a really simple example an evaluation function could be the number of pieces the computer has minus the number of pieces the opponent has for example the computer has 10 pieces left on the board the opponent has only eight then the computer would evaluate such a board to 10 minus 8 equals 2 of course that's not a very good evaluation function but you get the idea this can be made more and more complicated taking into account the value of individual pieces board position control of the center vulnerability of the King to check vulnerability of the opponent's Queen and tons of other parameters step 3 making a move the analysis is done it's time to make a decision let's make up a simplified tree the computer playing as White has to decide its move it constructs the tree above and applies what is called the minim axe algorithm it starts from the bottom assuming third level here and chooses the one with the maximum score consider the leftmost circle in the second level it has two possible outcomes two and eight since it will be the computers turn at that stage it chooses the best outcome that is the one with maximum score which is eight and so it assigns it to the node similarly for all the nodes in the second level now for the second level the outcome is decided by the opponent since at that time it will be blacks turn the computer assumes that black will make the move which is best for black and so the worst for white hence it chooses the setups with minimum score for example for the center node on the first level there are three possibilities nine five and nine the computer assumes black will take the one that leaves the computer weakest and that is five so the first level nodes are all given values finally the first level is the computers turn so it makes the choice with maximum score that is seven there are many other functions to evaluate the moves minim x is just one of them by applying a technique called alpha beta pruning the algorithm can run about twice as fast and requires a lot less memory as you can see this process is completely mechanical and involves no thought it is simply a brute force calculation that applies an evaluation function to all possible board configurations thus the computer climbs the tree alternatively choosing minimum and maximum scores thus the name minim acts and makes the choice that leaves it best off in the end the better the hardware the deeper the depth of a tree it can analyze and so the better its chances of winning which is why computers couldn't usually beat humans in the 1960s but now are regularly able to thrash grandmasters so that's all about logic behind computer chess please like and subscribe our channel and don't forget to share this video

Channel: ProtonsTalk

Views: 323,759

Rating: 4.6667767 out of 5

Keywords: chess, computer, ai, artificial intelligence, programming, algorithm, science, game, minimax, technology, maths, computer chess, Math

Id: CFkhUajb8c8

Length: 6min 11sec (371 seconds)

Published: Fri Dec 04 2015

Reddit Comments

[u/IMJorose]

I suppose its a nice explanation for somebody who has absolutely no idea about the topic. With that in mind I don't mind the simplifications, but I do have one gripe. Specifically the video mentions minimax using more memory than Alpha-Beta which isn't true at all, both search algorithms use memory linearly with the depth they reach, Alpha-Beta just reaches the depth much faster. Furthermore they mention AB is twice as fast as Minimax which is also not really correct. In the worst case AB degrades to Minimax and in the best case AB reaches approximately twice the depth given twice as much time due to the odd-even effect, which is a superlinear speed increase in the case of chess.

[u/enigmahack]

Ugh. I hate these videos with Microsoft's speaking voice. At least the voice is getting better, and it's good information provided in the video but I still don't like it.

[u/red_uheq]

The damn thing!