[Music] [Applause] last time we stated a very interesting result uh one of the first results in game theory due to von neumann and that deals with the game of chess and the the result was that one and only one of the following three statements is true either white has a winning strategy or black has a winning strategy or each player has a strategy guaranteeing at least a draw because exactly one of them is to be true therefore the fourth possibility of neither of these three things are true is is not a possibility now in this module we are going to prove that formally so because we want to prove it we will have to develop a little bit of more notation so each vertex in this game tree let us start with the game tree of fetches is a game situation because this once you are given a specific node let us say this node you exactly know through which path it has been reached and therefore you know the whole game situation we denote by gamma of x the sub tree rooted at x including the the node x itself so this whole ah subtree starting from x we are going to define that denote that as gamma of x now we also have this notation in x which says that number of vertices in gamma of x because it is a finite game ah we can always enumerate and say that there are exactly nx number of vertices in gamma of x now consider a node which is which is a vertex in this sub tree of gamma of x and y is not equal to x so something here and we are we are clear that because this is a tree the the subtree that is rooted at y and denoted by gamma of y is going to be a sub graph of ah sub graph of of gamma of x and therefore this n y if you want to call the number of nodes here that is certainly is going to be smaller than n of x the number of nodes now we also know that if the nx is equal to one that means there exist exists only one node in this subtree which is x itself then x itself is a terminal node there is no future nodes possible no future actions uh possible there the game ends and when the game ends it ends in one of the three outcomes win for white in for b or a draw now the proof process via an induction on this number of nodes on nx so the theorem the theorem that we have just mentioned is trivially true for n x equal to 1 and why is that because at this terminal note as we said either one of the three uh outcomes can happen uh if the white king is removed then b wins if the black king is removed then white wins and if both of them exist and there are no more moves then the game ends in a draw all right so we know that for one node system it is definitely true now what we are going to look at is suppose we have nx which is strictly greater than 1 and our induction hypothesis is that for all the vertices y in in gamma of y such that this n y is less than n of x then this the statement holds right so for all the all the sub trees here so because there is more than one node there must be some y ah which is not equal to x and that leaves in the sub tree of gamma of x and in that uh subtree every vertice follows three statements one of those three statements and exactly one of those three statements is true and as we know that gamma of y is a sub game so sub trees of game are all i mean used interchangeably in this as we go along in this proof so i think drawing a figure will make it more clear so what we know from the induction hypothesis is that if we start from x we do not know how we can conclude which of these three statements or we haven't proved that one and exactly one of these three statements is true at x but we know that at every sub tree of of x excluding x uh this statement is true that is because ah in each of these cases uh the the sub tree sub tree starting from here and the rest of the network ah the n y is strictly less than n x and there we already know that one of these three statements and exactly one of these three statements is true all right so uh let's get back to our definition so ah we without loss of generality let's assume at this game situation x it's the move for white and a very similar and analogous argument can be used if the it was a move for the black player all the things can be retraced in a very similar way and i can leave that as an exercise so let us define this notation c of x by c of x we had denote all this type of nodes which are reachable from x in one action of of this particular of the player white right so this is essentially this this node so and we know that ah at each of these nodes ah in each of the nodes in cx it's the it's a move for player b the black player now there can be three possible cases we are going to go over that one by one so the first case is it may be possible that there exists some y naught so suppose this one is y naught um which is in c x and in that place in that node the statement 1 is true because we know that the one of these three statements is definitely going to hold suppose the statement 1 holds in gamma of y naught then we conclude that this statement 1 is even true in this gamma of x that is the node starting from here and why is that true because why not node it the white player can guarantee a win the white player who plays here it can just pick this action and reach to that why not and at white why not it knows that it has a winning strategy so fair enough so we have found a winning strategy for white player even at the node x if case one holds so the let us go to the second case so the second case is that there could be a situation that for all y so for all the nodes in this c x the statement 2 is true that is b has a winning strategy then we know that even 2 is true in gamma of x because the moment so no matter whatever action the white player picks so suppose uh y is somewhere here i mean it picks the the white player picks this action and reaches this strategy reaches this game situation of y and then player b picks the optimal action or the winning strategy at that y and it will ensure a winning strategy so the fact that at every node in the cx there exists a winning strategy for b it also ensures that there exists a winning strategy at x now the case three is when none of this force and that is uh quite interesting so because case 1 and case 2 does not hold here then we can conclude both of these things one by one so because 1 does not hold then w the white does not have a winning strategy in any of this in any of these nodes in cx and since the induction hypothesis holds for every y in in cx therefore either b can have a winning strategy or they both have a draw guaranteeing strategy right this is these are the two possibilities right um one of the other two things has to happen now we notice that even 2 does not hold i mean case 2 also does not hold um then you can come back to case 2 and negate this sentence negate this statement which says that there must exist some y uh for which this this player b does not have a winning strategy so what was case 2 case 2 was saying that for all nodes in cx player b has a winning strategy the negation of that is that there exists some uh node at least where b does not have a winning strategy now from one we know that there could be two possibilities either b has a winning strategy or both have a draw guarantee strategy now we have found some y prime in c of x where b does not have a winning strategy so player a player white who is making the current move can actually pick that particular action which leads leads it to a specific y prime so let's say this is the y prime uh point where b does not have a winning strategy so this white player can just pick this action and go to a situation where b does not have a winning strategy but both of them has a guaranteed draw guaranteeing strategy and therefore the statement 3 must be true in this case and therefore we we also conclude that if case 3 holds then you can ensure that three the third statement of that of that proposition is true all right so that essentially concludes the the proof [Music] you