AI's Game Playing Challenge - Computerphile

Sogo is a very very simple game in terms of the rules but it's very difficult computationally there's an enormous depth of complexity that comes out of the very simple rules which is I think part of what makes people love it so much as a game so to understand why it's hard for computers I guess you have to go back a whole bunch and talk about just how computers play games in general these sort of turn-based strategy games or that kind of thing and start with something easy like knots and crosses the sake of internationalization yes tic-tac-toe I like knots and crosses has a name because it's descriptive you know but whatever yeah we're going to look at noughts and crosses as a game and I'm going to keep calling that I apologize but you don't have to apologize I just what I just want to make sure people if people understand what was right right right right that's all so I'm talking about this game where you draw you're up to Thorpe and then one person you know goes here and one person goes there and so on and you alternate placing noughts and crosses and you have to get three in a row to explain knots and crosses we should play it an even simpler game so the idea of the game is we're going to take it in turns to choose left or right and I'm going to try and get the highest number possible and you're going to try to get the lowest number possible it starts off my turn so if I choose left for example it goes down to here and then it's your turn and you get to choose left or right and then which number it ends up on is the outcome of the game so I want the highest number possible which is seven you want the lowest number possible which is one failing that I'd prefer the five to three this is a perfect information game what's the difference what's what's an imperfect information right right so so a perfect information game is just a game where all of the players have all of the relevant information so this is like that knots and crosses is like that chess go these sorts of games you do get games that are not like that for example poker there's hidden information you can't see each other's hands so you have to if you want to write something that's going to play those types of games obviously it has to work differently to take into account that uncertainty the question is should I choose left or right and how do I make a principled decision now I want the seven so in principle I should be going this way right you would think I want to steer towards the seven but on the other hand at this point it's your choice you're not going to choose the seven because I know you want the low number you're going to choose the one so I find choosing this node I'm effectively choosing the one because I can predict you'll do that whereas if I choose the right then your choice is between a three and a five so you are going to choose three which is better than the one so I should go right I'm trying to maximize the minimum value yeah I'm trying to make it so that the best choice available to you is as bad as possible for you and as good as possible for me so this is this is called minimax because I'm trying to minimize the macro you're trying to minimize the maximum I'm trying to maximize the minimum if you see out of me yeah and then purely based upon who goes first as to who wins this one right right yeah this is absolutely unfair game yeah I start off saying I want that I want the seven so maybe I should go left to get the seven right that's one thing I could look for the highest possible payoff and try and steer towards it that seems like a reasonable way of playing the game not on something this simple where you can see it obviously fails but in a more complex game you might think that look for the best outcome and try and steer towards it yeah but you've gotta bear in mind your opponent is doing away from it or I could look at it and say ah that's the one I definitely want to avoid the one so I can't possibly steer left I'm trying to avoid the bad outcome so I should go right or you could look at it and say okay how about this entire tree what's the average here what's the average goodness of steering left or right if you take an average on seven and one yep aren't you going to get you get four four because that's simplest one say if you take the average of three and five you also get four so in this case they're the same does that mean they're both equally good well no because one of them I end up with one and one of the minor was a three so so we're basically saying here okay there are different ways to evaluate the choices that you make yeah most of them don't most amount any good okay but there is one way that works which is basically what we did which is mimics and so it's a recursive function so let's try a more complicated game I'm going to generate some random numbers just using Python to get us a list and then shuffle that list and there it is so I'm just going to draw the trees before it was obvious that I kind of designed those choices to make a point here it's random so it's a real game now in many ways a better game than not some crosses because somebody's can actually win probably whenever you see a tree in computer science you should always kind of be thinking about recursion which you've done a video on before rights amigos what I dive back into this same piece of code because a tree has this kind of fractal structure where ideally you want to have an algorithm where you do the same thing and every part of the tree and then you can have one algorithm that processes the whole tree so the problem with recursion a problem with recursion is infinite recursion where you have this sort of loop of nested stuff that never ends you need a degenerate case you need a case where the answer is easy and in this case it's the bottom right so if we are at the bottom first move by the maximizing player second move by the minimizing player third move by the maximizing player so here which way should I go I should go with whichever one is bigger it's the seven right so we can effectively call this a seven it's not the end of the game but the value of this node is effectively seven because if this player directs us to there the game will end with a seven so you can do that in each case so this one is a five because that's the bigger one this one it's a three and this one it's the six so now these nodes which before you couldn't do because they didn't have any values now these look a lot like the nodes below so here now we're being the minimizing player so this will be a five and this will be a three and now we're being the maximizing player again who wants to go for the five so you can see here then as the maximizing player the best score I can get is the five that's assuming that we're all playing by the same decision-making stress right it helps that it's the optimal decision-making structure in this situation okay but you don't have to make the best choice right if you make a mistake I have values on all the other nodes of the tree I can make probably do even better but the way that min/max works is you end up with the making the best possible player you could make as bad as possible and you're trying to do the same to me this is a game you can play with your friends it's a it's a huge fun for everyone if you can do min max in your head and obviously if you have you can put 16 numbers at the bottom 32 whatever but you'll notice of course the more numbers you have at the bottom the more work you've got to do to figure out all of these into intervening nodes and it's tractable for some real games that people play like noughts and crosses so I could say I'm going to try it so if we take a game like notes and grasses tic-tac-toe which is so simple that human beings reliably learn to play it optimally you start off at the beginning your notes you have nine choices right because you can go one two three four five six seven eight those your options now it's the crosses turn and you're there you have eight options because one of the squares is taken so one two six five six seven eight and here there's a and you see just quickly this becomes ridiculous but no game of noughts and crosses lasts more than nine turns guaranteed you run out of spaces we go along slow I'm only going to fill in part of the tree now the point is what's the degenerate case because we're not trying to get numbers so what you do is you say this isn't going to be right but let's just say as an exam for a moment yes said it's that so it's a win for knots so if we're playing Nords we give this board a score of 1 because we say 1 we've won excellent a different board where the crosses have a win that's a minus 1 because I really don't want that and then any state where the game is over but nobody's won it's surprisingly difficult I accidentally want it this is how hard this game is there what what can I do all I do is win so so you're ok then it says the drawing that's a draw so that's a zero if it's your turn and you have a move that can win then that board state is it win and therefore you just propagate that up indefinitely exactly the same way as you would before yes so you can see how you can plot this out and it's much too big to actually do but if you write a computer program to do it it's not difficult it's a short program doesn't take long to run and noughts and crosses is a solved game right so let's draw the thing for chess how much paper if we go yeah it's this drawer chest okay yeah I'm not gonna draw chess while you're not going to draw chess while you know to come be that much more difficult kind of yeah so we need more paper we need a lot more paper to draw chess and the issue is the thing the thing you can see the thing that's so different here between the simple game the very simple game and noughts and crosses is this thing called branching factor which is basically at each little node how many branches does the tree have simple in this game it's two here we have two choices here we have two choices here we have two choices you always have two choices this is a longer game it has more turns but the branching factor is still two every turn you have two choices you can make in noughts and crosses okay firstly it's more complicated because the branching factor is higher secondly it's complicated because it changes in the first turn you have nine choices the second time eight and so on so the branching factor actually reduces as the game goes on which is one of the things that makes it easier to compute so let's think about it let's think about chess then in chess the very beginning let's say you're white you're about to start you've got eight pawns you can move you can move them forward one so that's eight possibilities or you could move it forward two so that's 16 plus you have two knights that are allowed to move because they can jump so each of those has two it's another four I think it's 20 I really play chess but I think I think it's 20 I think you start off with 20 so I'd be drawing one two three four five six seven eight nine ten eleven twelve all the way up to 20 and then as the game goes on much like in noughts and crosses the number of possible moves available to you legal moves varies right so presumably first it goes oh yeah as the game opens up early on you get more moves available because you've got sort of more space and things can things can move to several different you know positions and all that kind of thing and then past a certain point it starts to go down again because pieces get captured and when obviously when you have only a few pieces on the board you don't have as many moves available to you but on average when people play chess I think the average branching factor is about 35 but chess games generally go longer than nine turns right so when you're calculating the number of nodes in your tree every turn you're multiplying by the branching factor and that quickly gets completely unmanageable so you can't just mid maxilla chess like this it's computationally completely infeasible which is why chess was considered such a big milestone for a long time if you could make a computer that could play chess you know you're not just doing this very trivial brute-forcing thing like you're doing for noughts and crosses you know for a computer could play chess it really have to be thinking right you can see a cow here we were taking the end states where we knew the value of the game and then propagating backwards in time from there to give value to these board states that we didn't know the value of before the problem is there you have to go right from the very end of the game which in chess you can't do this there's just too many possibilities so you need some way of giving boards values that isn't just propagating backwards from the possibilities from known and you know checkmate states and luckily in chess there's a lot of things you can do about that the most obvious one is just counting up the pieces you just say well a pawn is worth you know one point and a queen is worth nine you do some analysis of how games tend to go and you you try and figure out how good the pieces you have left are basically and the position of them obviously is important but you can get a good it's a good heuristic it's a good approximation to just add up the scores of the pieces and say well you know this team has both their Knights and still has their queen and this this only has one night and is lost their queen so it's really obvious that this team is winning and therefore that's a good stay to the board and you don't need to be able to see all the way to the endgame to know that it's a good stay to the board so the point is because chess is branching factor is so much higher you can't do this thing where you work backwards from the end States the branching factor is too high you have to start from where you are and look forwards and say okay hypothetically if I went this way what would that look like what boards would that allow me to get to and then if from there I went here how would that look and so on you don't know whether you're heading towards a win or not and this is where the heuristics come in is that they let you put some kind of numbers on these notes like you know do I still have my Queen in this note and that should guide you towards winning positions because there tend to be more winning positions in situations where you have your queen but it's always a heuristic you they're not the the chess AI is not seeing forwards in time to a win they're seeing forwards a certain distance and seeing that it's a good to be in according to and it obviously it's not just what they have on the board like that's an oversimplification there's a lot of different heuristics but the point is you're going to have to evaluate a very very large number of boards so you want something you can compute quickly because the more boards you can evaluate the further ahead you can look and therefore the better you can play even in this game if you're playing with someone and you can think more moves ahead than them that gives you a huge advantage because you can force them into a into a situation where the best move available to them is quite bad and they didn't think to steer away from that because they didn't look as far ahead as you what this number means is if I go here and then play perfectly from that point on what's the worst score I'd end up getting this algorithm assumes that your opponent is always going to play the best move that's available to them because you're always prepared for the worst possible scenario so you're only ever pleasantly surprised chess is a different ball game it's got more complicated maneuvers it's got different ways of branching as well as larger branches so how does this all feed back into our original point of go looks pretty straightforward to me right okay go right let's draw go okay we're going to need more paper is there also significantly larger universe to put that paper in go is difficult for a lot of reasons actually the first reason that makes go difficult is the branching factor is very high it's generally more than 200 compared to chess is 35 so every turn there are at least 200 possible moves you could be making and so if you imagine me drawing this tree with 200 come on then most draw it all right 301 I begin it I'm going to run out of pen to see what I'm gonna go in between so six thirty nine forty you know what I think life's too short Rob yeah no you're right yeah this margin is too too narrow to contain so um it's not going to happen right it's not gonna happen and what's more even you know it wasn't going to happen with noughts and crosses but you can do it in a computer you can't do that with go we can't do that with chess even and you really can't do it with go and so even a lot of the cleverness of tree search and like pruning and all of the really neat algorithmic improvements people have made for ways of navigating these trees that allow this type of old-fashioned AI to be extremely good at playing chess and better than any human at this point that approach is not going to work with go and was never going to work with go and so go became the great on the goth past tense go became the great the great milestone right after chess go was the big one so right where we were going with wise it's hard the branching factor is huge that's one thing but also you don't have a lot of the tricks that you have with chess you can glance at a chess board as I said and just add up the pieces and say well this you know white is probably winning or black is probably winning in go that's not the case in the middle of a game of go between two good players other good players could not necessarily tell you who's winning right now because the specifics of who's winning depends very sensitively on the precise layout of the pieces it's not just a matter of who has more stones on the board or who has more territory or who has more points or anything like that it's sort of an emergent property of the pattern of the layout which means you don't have these easy shortcuts you can use to evaluate a position not only are there 10 times as many possibilities to search there's no obvious way to even Carol if a position is good once you once you're looking at it which is well this is why this is so impressive what's been achieved by alphago to beat the best human players at a game where all of the standard tricks of the trade won't work and you have to really try something new hidden melty display that tracks where you're looking and various other things so it overlays and this can represent the other paddle so we've got two objects with the identical interfaces want to represent

Channel: Computerphile

Views: 663,903

Rating: 4.9233084 out of 5

Keywords: computers, computerphile, computer, science, computer science, ai, artificial intelligence, Go, Chess, AlphaGo, Deep Mind, Robert Miles, Chess AI, Tic Tac Toe, Noughts and Crosses, War Games

Id: 5oXyibEgJr0

Length: 20min 0sec (1200 seconds)

Published: Thu Mar 24 2016

Reddit Comments

[u/kg_b]

He doesn't explain how the engines work. He states how difficult it is computationally because of a high branching factor and that engines are choosing based on evaluation (and not brute force). Waste of time for me.

[u/kuteva]

The post's title is misleading. This pretty much explains Minimax and nothing more. You don't need to waste 20 minutes for that.

[u/jsloan4971]

I thought that was fascinating and very informative as someone who loves chess but has no understanding of computer science. Thanks for posting.

[u/t0f0b0]

He reminds me of Jon Richardson.