Combinatorial games are sequential, deterministic games with perfect information where players take turns making moves, and the last player to make a move typically wins (normal play); unlike economic games where decisions are simultaneous and payoffs depend on others' choices, combinatorial games include examples like tic-tac-toe, dominoes, chomp, and hex, where players develop winning strategies through backward induction and analysis of game states.
Combinatorial Games: Introduction & Examples | Game Theory Course
Added:[Music] [Applause] welcome to this NPTEL course on game theory game theory is a mathematical discipline which models the conflicting behavior the subject originated during the World War and the pali mathematician funnyman is considered to be the founder of this subject the subject has some earlier results by ML burl and other people but the funnyman is considered as the main person who created this branch of subject there firmaments book with economists Morgenstern the games and economic behavior is the first book on the subject which laid the foundations so in this subject there are two are multiple people who make their decisions simultaneously and accord accordingly the each player gets a benefit or payoff function payoff now the objective is to decide how to choose their decision depending on others choices as well of course the major problem here is that when a player is making his decision he does not know what the other players are making so these games are known as economic games classical games and there is another class of games known as combinatorial games the combinatorial games are the games that we have played as a kid the examples are tic-tac-toe chess and other games like that these are this the theory of community such games is developed mainly by John Conway Richard guy and Ervil Balcom in fact they have written a very famous book called winning ways right now it has four volumes as mentioned in the introductory video of this course this course is divided into four parts the first part is about combinatorial games in second and third we will look at non cooperative games zero-sum and non zero sum game and in the final part we look at the cooperative games now we will concentrate on community games we will walk through some examples through these examples we'll introduce some of the terminology we start with tic-tac-toe tic-tac-toe is a game played by two players on a 3x3 grid players make alternative moves so started with starts with first players then the player who makes our marks a row our column or diagonal is is the winner so let's see what it means suppose let us say the player 1 let us say places a mark here then player 2 let's say he chooses a mark here then player 1 again makes his move that say he makes his move here then player 2 if he doesn't place a mark here player 1 is going to make a 3 in this along this diagonal therefore player 1 will so he will try to place his marker here then player 1 will be forced to play here then player 2 will play here in the next player 1 whatever wherever he places so let us say he places here then player 2 will be forced again here and then player 1 finally left with this mark now in this instance no player could make 3 marks in a row so therefore this game has ended in a draw but let's look at another instance that's a player one has started making mark here then let's say player 2 has make mark here then player 1 let's say has put here then that's say a player 2 has put here now of course obviously player 1 is forced to play here and in the next player 2 let's say he makes a mark here but then player 1 puts here and he wins so in this setup player 1 wins so this is a tic-tac-toe game of course in this game we also have an option of draw but in most common community games we always assume that the game ends either in a win are a loss but the tic-tac-toe since this is a well known to us we have start used this to illustrate the ideas of combinatorial games even though in a classical sense tic-tac-toe is not a community game but the arguments that we develop in common idol games are used to analyze such games ok now we will see another game so this is called a dominating okay the dominating game consists of a square cell where the players again make moves alternatively player 1 chooses two consecutive cells horizontally say player 2 chooses two cells of course consecutively and vertically so in a sense player 1 is going to choose two cells like this and player 2 will choose something like this now when they do like this the Eternity will each start choosing it whoever makes their last move he is going to be the winner so let's say already the the player one has choosen this and player two has choosen this now let us say the player one has chosen this two consecutive cells then let us assume player two now hydrogen this player one now can choose this then player 2 let's choose this then player player 1 is let's say he goes to choose this then player 2 let's say he chooses this then player 1 now goes back to this he chooses this then player 2 player 2 has these are all free for him so let's say he chooses this and player 1 is going to choose this then again player 2 can choose let's say this now player 1 has one choice here that's it so therefore he has only one choice here he will choose this then player 2 can choose this now player 1 has to no move here so therefore player 2 is the winner player 2 is winner in this setup so this is a dominating game note that in this instance of dominating game player one has no further no more moves to make of course player and the player 2 is the person to make the last move and hence player 2 is the winner so in typically in this combinatorial games the last person to make the move is the winner there is another version where the last person to make a move is going to be in the loser which are known as misery games but the common version is the normal play where the last person to make the move is winner so let's explain another game which is known as a chomp so this has again kind of a rectangular cell and each cell is considered as a chocolate here and this cell consists of poison all the cells are considered as a poison so now whenever a player as usual the players make moves they alternatively if a player makes let us say a move here there's a player one has decided to take here then he not only takes this particular cell he also takes the all the cell's above and right to it so that means this all these cells he will choose next player two will choose another cell let's say player two has choosen this then he will choose all the things above and right to this then next player one let's say he to just this then he will choose all this then player two that he will choose this so here in this setup player 2 is winner so this jump is another game where the in this instance player 2 is winner so now we will look at another game this game is known as hax there are two players here one is a blue player and another is that's a red player later okay so the goal of this game is to make a path from one side to the another side so the blue player wishes to mark these hexagonal cells such that he makes a path from this side to this side and the red player would like to make a mark from this side to this side and they will be alternatively making their moves so in each move the players will pick one of this hexagon cell and mark them with their respective color so let's play this game so let's say blue player starts here let's say he makes it blue then the red player comes so let's say red player marks here next blue player again then the red player next blue player I say he will put this here and the red player now choose yes let's say here next blue player will come and he will mark here and the next red player will do here and then the blue player comes here and now we have a path from the blue path from here here here this so in this instance the blue player won this game okay next we will see one more game which is known as a take away game so in this take away game there are some set of coins right now we will put it as a sticks here so let us say let's say ten sticks again two players alternate will make the moves and then the in each move players can pick one R 2 R 3 sticks again last player to pick is winner so there are certain number of sticks so in this picture we have 10 sticks and the players are making their moves alternatively and each player can pick either one stick are two sticks are three sticks now the last player to pick is a winner is the winner here so now let's look at this one let's say the first player let's say he picks three first player now let us say second player in his setup let's say he pick two then the first player will pick only one then the second player whatever he picks here and in the last player will pick the last stick here so this is a game where in this instant the blue player has won now the whole idea of this community games is to understand such games and see whether a player has a winning strategy or not Butler who has a winning strategy for example in this game can we see necessarily say that the player one always has a winning strategy our is it true that the player two can and force the win so in the following sessions we will discuss about some of these games and understand their winning strategies but before concluding this session would like to point out one very interesting application of this combinatorial games so we have seen in the previous game this hex game using this hex game we can actually prove what is known as a bra a fixed point there are so L stayed what bra a fixed point theorem is and then we will come back to this later so let us take a function f from let us say interval 0 1 2 interval 0 1 we assume that this is a continuous function then a point X in 0 1 is called a fixed point of yep if F F is equals to X now the question is does there exist a fixed point this is a question where Brower has proved that let's say KB convex and compact set R then every continuous function yep from K into K has a fixed point so this is a very very deep theorem and in this course we will see how this hex game can be used to prove this fixed point theorem but before concluding this session let me just give you a hint about proving one dimensional case so f is from 0 1 2 0 1 consider G of X to be FX minus X now note that G of 0 is greater than 0 G of 1 is negative therefore there exists X in zero one says that G of X is equal to zero which implies FX is equal to X of course a small issues one a one needs to check here the main thing is that how am i guaranteeing this existence of zero this I will leave it to you as an exercise so this is the kind of mathematics that we require to follow this course and we will assume that level of mathematics barring certain results in this course we will prove almost all and all results and we will not leave any theorem and prove ok with this I will conclude this session will meet again in the next session [Music] [Applause] [Music] [Applause] [Applause]
Up Next

Winning Strategy in the Game of NIM: NIM Sum Lemma & Theorems
@trevorpasanen9515
5K views•2020-05-11

JEE Maths | Circles: Pole & Polar Explained with Equations
@TargetPublications
14.4K views•2019-02-23

Fourier Series Introduction: The Big Idea Explained
@DrTrefor
387K views•2021-05-03

The Mathematical Impossibility of Accurate World Maps
@Vox
23.3M views•2016-12-02
Related Study Plans & Knowledge Roadmaps
Structured learning paths in Mathematics


















