>> Hello, this is games without dice or cards. Combinatoriai Game Theory. I'm Tom Morley. So let's start by jumping into the water head first, and let's play a game. Let me first introduce you to our two players. Our two players are called left and right. These two players alternate. One goes, what the other one makes a move, then the first one makes a move, then the other one makes a move. Typically, left is associated with the color blue and you can remember that because there's an L is blue and right is associated with red, and you can remember that, because there's an r in red. Now, these players are going to alternate, alternate, play and the 1st 1 that can't move loses. So there's no ties. At each stage of the game there will be various moves available to one player or the other player or perhaps both, and whoever runs out of moves loses. So let's take a look at something like this, and So let's start with a little horsey. Okay. So this is a game called Hackenbush, well, it's a particular position in the game called Hackenbush. And you can start in various ways but we start with this little horsey. The two players, red and blue, left and right, take turns, and what they do is cut one of their edges of their own color. So if blue starts, he could cut this edge, and that edge is no longer there. Now, these, these edges have helium in them, so and they're attached to the ground here, which is green. So if something gets disconnected from the ground, it floats off and is not available to either player. So, for instance maybe, right goes here maybe left goes here. Now, at this point, this whole piece here is still connected to the ground. But once right moves, it all floats up, and now left moves, and there's no moves left for left. Okay, so, so whenever the two players alternate, left cuts blue edges, right cuts red edges. Any edge that's either cut or no longer connected to the ground to where the nutrients are, the nitrogen and the water and whatever. Any edges no longer connected to the ground, floats off and is not available to either player. When a player has no edges to cut, the game ends, that player loses, okay? We'll see a lot of examples in terms of Hackenbush as, as the game goes on. Let's take a look at some very simple positions in Hackenbush. Here's the ground. It's green. And now we go, I don't know. Blue, and blue, and maybe a red in between. And maybe a red. And then, say, a blue on top. Up, now up. It's okay that these aren't connected, but they're connected to the ground, so that's okay. So, they're there maybe, maybe red goes first and red says aha, I'm going to cut this and now these float off and that top blue end is no longer available for blue. Blue say, what's the best move for blue? I don't know offhand, but blue might cut this, and then red cuts this, and then blue cuts this, and now red loses. So that's how that works. And we'll, we'll look at various variations of this where we start with, with, with more complicated pictures and, and try to analyze in terms of, of who, who wins, if left goes first, who wins if right goes first? Okay. Let's take a look at another class of games. And this is a class of games all played with coins. In this case the coins are pennies and dimes, but and maybe right is pennies, because the copper in pennies, although, there's very little copper actually in pennies looks kind of red. And then the dimes, say are, are left. Now both players push coins to the left in the direction of, of that and the three games push, shove, and run over have slightly different rules. Now you can, you can, you can push a coin off the edge, off the end, and if it's off the end, it's no longer in play. So the two players alternate pushing one coin to the left one space. And let's look at let's look at, say, this position here in push, the first game. If left pushes this coin over this, this coin over one, then that pushes also that, the, the coin next to it over. So that's, that's called push. In, in, in shove, when you push a coin over, everything to the left moves over one space also. So with shove, this, this, this coin over here gets thrown off the cliff. In run over, what happens is when you push, say this coin over here one to the left, you run over that person and that, that coin disappear from playing. So you can look at longer positions to start with, different relations of coins on the thing. I think it's not too hard to show. Whoever has the right most coin will win the game. But, but if we have several of these going at once, then, then things get a little bit more complicated. And still what we want to do, even if we know who, who's, who wins the game what, what's the best play maybe to, to delay, going off the cliff as long as possible. So, so here's four games to play with and I urge you to start with pictures like this. Find someone to play, find, figure out whether we want to be left or right doesn't matter. Draw a picture like this and go play some games get some coins out, draw pictures like this. Play several of these at once and we'll explain as the course goes by how to do that more carefully and, and see what see what looks like good moves and see what looks like bad moves. So there's some games to start with and, let's, continue next time.
