Practical Game Theory

so on room I'm Scott we're those who dig knives the late-night podcast for geeks if you like this at all there's Flyers out there we've got videos of most of our lectures for the last many years of paksas we probably have a video of this one up to people on the internet will know if we did that or not and we're here to talk about game theory which is interesting because we talk about game theory a lot we talk about it and act like we know a lot more than we do we'll get it right over to the port where we talk about the math and then we say but the rest of it isn't that important we move on because we just read the Wikipedia and now we're gonna tell you what we read and we reference game theory a lot and the problem is that we always talk about how useful game theory is and it is useful in games but it is not really about the things you think it's about you think game theory I'm gonna study games you're studying games in the same sense that if you're like racecars you can go and study I don't know carburetors so what is game theory game theory is actually a very recent mathematical field that is used in a bunch of other areas it's used in war it's used in biology it's used in politics and really all game there is is the idea that you can study and describe and maybe even predict the behavior of rational actors making decisions and maybe cooperating maybe competing it's actually a fairly open field I mean almost everything you do is some sort of cooperation or competition and you're making some sort of decisions you believe in free will at least now game theory in terms of games is a little tricky because the math is usually not useful like really not useful you'll study all the math of the prisoner's dilemma it's not gonna help you win games so what we want to do is take all the lectures we've done for the last many years and talk about how to actually use this game theory stuff we talk about all the time and actually apply it to games and not hawks and doves fighting over who gets to eat whom so game theory actually has its origins if we talk about what we're talking about with the Prussians pretty military powerhouses of the seventeen hundreds the 1800s 1900s not so much after that yeah whatever most of our society comes from these crazy people right I mean just you know the art of war but not the sunsoo Art of War right our school system the idea of oblique education is we have it today came out of Prussian military academies yeah I mean all wargaming period on tables so it's funny you mention wargaming because this is a very old picture but it's a picture of something that you might see in a tabletop library today wargaming as we know it today existed back in the in the Year 1812 with a game called Krieg field which means war game now this game if you saw people playing it in tabletop today it has dice it has a game master and has a red pieces versus blue pieces with rules about moving around a board it is a modern Morgan you can go read the rules to this and play it today this game was used to train military officers in Prussia to be better at doing military things aka killing people now this is very important games are used you know we think of games is fun but look at biology play the idea of play generally is animals learning how to fight or survive without the consequences of failing to fight or survive properly okay dying so we can play racing and study you know how war works and there is nothing like war without having to actually go to war and die so Prussia got the idea very early on that they could train they could do military exercises and then they could go one step further and simulate battles and study how war will work on tables with funny dice and this turned into a hobby and Prussia independent of its use in the military but the core thing to remember is that the games were talking about came out of our station of trying to use games to simulate reality to be able to learn from our mistakes without being killed by them and it's weird that today we play games we're not trying to sort of simulate reality with a lot I mean guess flight simulator if you write and stuff like that Starcraft right when I play Puerto Rico how am i applying that every I'm not I'm just trying to remain at Porto Rico itself the game is the means and the end obviously in fact we've moved beyond the creek fields to the point where we're playing games purely for enjoyment but if you play games enough to start to understand the sort of real-world ramifications and the underpinnings of these games and as a result you'll get a lot better at games now game theory in quotes game theory with a capital G and a capital T that you you know we talk about all the time that actually didn't really exist until around the 1920s and it didn't exist in the form we know it today until as late as the 50s it's a very new field compared to other things almost his news video games and the few jobs john von neumann or no Ayman depending on how you pronounce it and John Forbes Nash who's still alive I'm not gonna get into the history of game theory and like where it really came out of but these two people kind of founded the idea of a modern game theory that you could take the decisions that rational actors make codify them with math and study them and figure out things about them you'll see these names all over if you study game theory people call toy game theory games von neumann games to this day Nash equilibria you'll hear that term thrown out all the time these two dudes are relatively recent to the field and then this field is relatively recent to the world now game theory at its core has some problems it assumes some things you all know what happens when you assume so one game theory assumes that everyone involved acts rationally and to the Barrell acting in their own best self-interest so you can see how already if you were to just go by game theory and playing all games it would fail all the time because number one and none of your opponents are gonna be rational right everyone you play against is doing dumb stuff right they don't know they don't know what the best move is even if it's obvious right so they do that and suddenly I that guy keeps trading wood with his girlfriend because he wants her right man well that's the self-interest part well right the self-interest is you know some guy is playing Counter Strike he doesn't want to win the Counter Strike which would be in his self-interest he's just wanted to shoot his friends in the head and team kill right and it's like in theory doesn't confident now the real world to the difference between these war games and game theory why they're distinct is that war teams tried to simulate reality and then use that to teach people how to deal with reality or to figure out how reality works game theory tries to figure out how perfect people act in a perfect world so I want to talk about these assumptions it's very important these assumptions imply a lot of things that you might not realize the whole point of this discussion as we're gonna try to show you the practical side of game theory game theory assumes people act rationally that means that your opponents in a game should or could be just as clever as you that is a huge assumption if you've ever played chess and you move your bishop out a little bit and you're kind of hoping he didn't notice and that he might move a guy there later that's not game theory you should assume when you're playing games that everyone at the table is just as smart as you that you cannot hide the existence of a strategy from them they figured out that maybe you're gonna put the bomb in the back corner of Stratego surrounded by bombs if you think they hasn't figured that out you're not thinking like a game theorist you're thinking like a normal gamer and you don't want to be a normal gamer you came to pax and instead of playing games and watching drivers go on the main theater you're talking about game theory in this room you made it so rational people are playing logically there Falken stare clever they're just as clever as you think about that think about imagine playing Settlers of Catan with three of your self who is self-interest it assumes that you are trying to win the game you're not trying to let your boyfriend win the game because you expect something later you're not trying to flash your teammates you were trying to win the game by the rules of the game which means we have to define some game theory terms words in game there's a whole lexicon of words that have very specific meanings utility is the character it's what you're after in a game right so in a game with his victory points right you're after winning but the key to winning is victory points right you try to get the most victory points if you don't try to get the most out of your points maybe you just try to get money and money isn't victory points you're not happy you'll have a different utility that everyone else has now think about the implications in gaming if someone's trolling in a game they're seeking a different utility from what the game told them to hey we're gonna play the prisoner's dilemma he just punches you in the face he's playing the punching game anytime someone is not playing to win they're not playing like a game theorist their game theory suddenly breaks down it's hard to analyze that game because that player is acting irrationally now think about that in a perfect world nobody extra irrationally but your attacks you know what's up yeah so sometimes I planted that runner deck I made right and I didn't try to win with this deck there was just this weird combo - did a silly thing that didn't actually make you win it only helped you in any way just to make it be silly as a guy so think about this when you're playing games if someone else doesn't appear like they're trying to win you try to figure out what they're after what the utility is and then use that knowledge to win imagine trying to figure out when other players are acting irrationally and take advantage of their irrationality we'll talk about that more later but just remember utility is victory points game we're at Magfest and we tried to define what a game is on a panel with a bunch of gaming industry experts and you know what people got mad in the audience when you dared to say that watching a movie might gay right but in game theory right a game has an extremely strict definition in the context of game theory right first of all a game and game theory has to have multiple players anything a single player is not a game in game theory end of story it's a puzzle not a game right or something else it's not a game unless it has two people because game theory is all about what decision do you make based on the decision the other person could make if there's no other person to make a decision then it's not a game anymore it's just you solving the math problem the end but roomin Scott you're thinking what about AI won shut up today we want to be pedantic and really get into you know the idea of what does a man what does it mean to be sentient all those things we're trying to be practical about this the ivory tower side of game theory is awesome but that's not we're here to talk about so think of AI if you can't distinguish it from another person fine it's a game theory game if you can figure out it's AI then no it's not a game theory game or it is and you're just gonna assume that it's a player who's dumb and follows a strategy in the real world today every AI is not a real AI so you could know what it's going to do so it is in effect just a really really hard puzzle that is hard to differentiate whatever now humans might or might not have freewill we could get into all that but are you if the only argument you can make about anything is the low level solipsistic what does it mean to be a lot that shut up but it has to be interactive you have to actually interact with the other players or we're not talking about it if we're playing versus solitaire whoever wins first sonic game theory game we're gonna we have nothing to say the versus progress quest let's go I started in AI star and both of us the game has to involve decisions you have to make a decision at some point now you might have decided what you're going to decide ahead of time let's call the strategy we'll get to that later and the game has to have payoffs it has to have victories someone has to win someone has to lose you have to get something poker to win some money there has to be something that you can get more of than someone if you play tag it's like well when does the game of tag end is there a winner is just someone who's it all the time but there's no winning ending it's not a game three I just read an article in The Times about a group of guys you never play for yet they've had like 40 years right so the game has texture the game has to have been winning and ending a victory of a prize you know some way to do to end and there you go with the results so and this in general whatever you're talking about games there are different definitions of all these words but if you want to have a serious discussion you have to define the terms you're gonna use ahead of time so you're not arguing about well what if I play a drinking game while I'm watching a movie that makes that movie on game now shut up strategy I use that word that word means something very very specific in game theory a strategy means I'm gonna be looking constantly but if it gets close to me you see where I'm going with this a strategy means you've decided what you're going to do for the entire course again I have a rock-paper-scissors strategy Rock okay yeah I lose I lose knives a strategy strategy means you have already made every decision you're going to make before the game starts your decision was what strategy will I use but it's not necessary that you've decided right is that a strategy is a complete set of all the decisions right so in chess if you said I'm gonna you know you have a complete set this one there then this one there then this one there then this in there and you plant you know it's got the plan for the whole game that is strategy number one and let's say you take that exact same strategy and you say well I'm gonna be the exact same thing except on the last turn the pawn will move one space less all right well that's strategy number two and if you figure out every possible set of moves right for any particular game that is the you know complete strategy set every move you can make in for a game like chess we haven't calculated the whole thing yet but for checkers we may never calculate the whole thing it's not likely in our lifetime we will we'll get to that so in Street Fighter if I the Duke in one millisecond differently that's a totally different strategy so practically you're not going to have a pure game theory strategy when you play games but you'll have a colloquial straight I'm gonna don't get this out of him and that's all I'm doing that works surprisingly well I guess people who don't know how to jump so the whole point of this is that there are games in game and if you want to study this stuff for real go to Wikipedia and look for the list of game theory games there's like a hundred of them there those games are not fun to play but those games exist inside of the games you play every day so if you study those games you'll recognize when an analogous game like those games exists in your other game so you're planning game while you're playing okay so now remember every one of these game theory games meets the requirements of the true game theory definition of game right it's a multiplayer game you make decisions there's a payout there's a winner right and when studying those games and what to do in them you're assuming the rational actors people trying to win and not trying to do whatever else so the prisoner's dilemma now there's a whole description of the prisoner's dilemma you can bring this up in every talk about game theory because everyone knows it's super simple rather than using the classical definition I want to use the definition from a game I might have all played when you were young now it's not a game theory game obviously but this people you'd argue this is a game it's more it's no more less of a game than a final fantasy in some senses so in this in this game you're a kid and you have a magic bike so you get invited to be in the bike race and you and another kids got I'll play this right now so the guy comes over and says we each get a piece of paper you're right Apple or arms if you're both right Apple both get into the bike race if you both write orange neither one you gets into the bike race if one of you writes Apple and the other one writes orange government orange goes home guy wrote Apple gets 500 bucks and gets in the bike race and the option of the game gives you are right Apple right orange wink and the other player and right Apple wink at the other player and right orange that is the prisoner's dilemma you are competing someone else in some sense you can cooperate to mutual benefit or you can defect against the other person and if you do so you get a much larger payout at their expense but if you're both defect you're both you might see on YouTube that was a clip from some British game show I think it was like split or steal right and basically it's the exact same thing you've had two balls they had to do the split ball to steel ball think both do the split ball then they split this money evenly a surprise if one guy does the steel ball and the other splits the steel guy gets all the money and if they both steal they get nothing right so this genius went on the show and was like I'm going to steal the other guy's like what what do you mean it's like I'm gonna steal there's nothing you can do about I already decided I've decided how do you win I have decided a hundred percent I'm going to steal your two choices are steel and neither of us gets anything or you split I take all the money and I will promise I will give you half of it after but you'll have to go right so there's the only chance if you're getting any money at all because I'm going to steal is to play split and let me have the money if you pick steel neither of us will get any money I'll be able to share it with you right now rights and signaling and things like that we're gonna talk about in depth and a little bit but just honest so turns out that there's a prisoner's dilemma side of El Grande Le Grande is a game theory game there's a copy of it right there that Scott doesn't necessarily agree with if you want to learn all these like sub game theory games El Grande is probably the best game to learn this stuff with because it has so many of these little games in it so in El Grande one aspect of it as there is a Rundle that is used as a secret spinner so say on ranma Scott's blue or we just switch him it doesn't really matter if you select a territory you have a bunch of dudes like troops you can throw into that territory Scott and I could both collaborate to say yo I'll put all my troops on green you put all your troops on green we'll both benefit because our homeland we get to score it with the extra points and green screw we knock him out of the game now it's a 50/50 shot which one of us wins in the end we could collaborate or maybe we say we're gonna collaborate and then Scott attacks me anyway no no he's going to Greene for sure I say yeah sure and then I see well if he goes to green Red's wide open I'm going ready so we have to decide are we going to defect or not well I defect against that will he defect against me now this gets really interesting for a lot of reasons one we can cooperate if we cooperate we change our chance of winning in a three-player again of El Grande from 33% well thirty-three point three three three you get the idea to 50% and greens just out nothing he can do but simultaneously I could turn my chance and almost a hundred percent if i betray Scott but if Scott betrays me and i betray him know that you learn a lair is gonna win so it's the same thing it's the prisoner's dilemma happening as this one tiny sub game inside of El Grande if you know how the prisoner's dilemma works you're gonna be good at El Grande it so in El Grande if I wanted to say rim I'm going to pick thread I'm going to figure out if you paint green I will give you half now if you ever watched us play games you'll see me and Scott will be playing with a bunch of like listeners or fans in the tabletop somewhere now look it's got little bit like Apple Apple I'm gonna show him anyway that's just how you do so the word cooperative you know we're gonna do find some more chirps does not mean what you think of me right well in game theory doesn't right someone says call cam you're thinking double dragon right double dragon is not a cooperative game in the game theory land and the game theory land for a game to be cooperative right people need to be able to form teams and win together and both receive the result the reward so we think about this cooperative no we're not talking about shadows upper camlock during those times don't get me started no co-operative has such a specific meaning like Scott said binding coalition's in monopoly if I could make a deal with you like yo if you land on boardwalk I won't charge you and the game forces that to happen extrinsic enforcement the rules say that is what happens then monopoly becomes a cooperative game games are cooperative if you can make deals and those deals are in the rules of the game now I've made deals with people and games like risk before their diplomacy doesn't work out so well does it so this is nothing in the game that says you have to do that so there's nothing you're basically just talking so what ella grande I can say all I want about whether or not we're gonna cooperate I totally won't attack you that means nothing and you're a good player you realize that if you're playing a non cooperative game anything anyone says means nothing so non cooperative games if we're talking about non cooperative games it's pretty much every goddamn game out there all those no games actually have game theory cooperation in them so we'll get to that in games like diplomacy or Civ you can make alliances in the course of the game you can break alliances but it's hard to make complex binding deals like I won't attack Australia for 10 rounds I promise I will never attack you in Asia as long as Scott is still in the game you can make all these kinds of things that people love to make these cooperative deals but games are only cooperative if the rules say so is the real world cooperative real world games like I'm gonna sign a contract to be in packs and do this lecture well it depends right on the one hand we could sign a contract but then not do it nothing stop physically prevents us from doing it but there is a post enforcement of the police who will come there is extrinsic enforcement contract law in the United States Atlas is effectively a cooperative game because I break the rules the contract the government comes and does something to me and if I don't want to do what the government says then the government's cousins come and do something in the end does force me to do what I said I'll do or some compensation comes out so the world is effectively cooperative in society because we have laws we have structures if you don't cooperate impacts the enforcers will do something about it so what happens if you make a game cooperative why aren't games cooperative there aren't that many Crawford games because they make games very different in do you can form an alliance of players whenever and you win collectively you all just win together if you your group can win it's just three on one maybe if the other players couldn't form a coalition imagine monopoly if you can make four real deals mention risk if you can make four real deals so whenever you're looking at a game and someone's trying to make a deal with you consider whether or not that deal is actually binding yo dog I'll totally give you wood but next time I have it in settlers but I don't have anywhere now if you give me a stone now I'll gladly pay you Tuesday Frank we're good today that's not gonna happen bro now what if you never get a wood for the rest of the game I'm gonna get what are you so let's talk a little bit about so-called co-operative cancers I like to call them games I don't like these games and here's why if you're playing pandemic assume no expansions assume no traders anything weird you're all trying to win right so what it's not a game theory game so there is no incentive to not share all the information you have so as a result games like this tend to break down to the one guy who figured out how to play perfectly telling everyone else what to do that's not fun people get mad and try to limit that communication but they're limiting themselves they're giving them they're basically handicapping themselves the game itself gives you no incentive to not do exactly what the smart guy said this game is really just a solitaire game but what they do is they say well it's a solitaire game but we're gonna split up the turn into four pieces and each person takes a different part of the turn right there's no actual cooperation necessary at all it's really just yeah well I'm gonna finish Great Scott I said in the shadows of her Camelot I said I got a bunch of good cards that I just don't play them and we lose great I lost two yeah you know it's just a puzzle that's slightly different every time and you solve it together with your friends but usually one person can solve the whole thing is it's not that hard a puzzle but rimming scott games like shadows over camelot have a traitor so there is someone you're playing in nope because those games if you do share all your information either the traders not going to share with you and you know he's the traitor and you're gonna win or sharing the information guarantees that you know who the traitor is so games like this especially games that traders force you with usually very poorly written rules to not share information you can't and shadows over Camelot tell people yo I have five of this card in my hand if the rules say you can't you have to be vague I got this I don't got this I need a little bit of help they're just obfuscating the fact that there's no game going on so I'm sure everyone loves pandemics upsetness yeah you're probably upset it's not so signaling this is what we're talking about in game theory there's a concept of signaling signaling is when in shadows over Camelot you say I have five of this car it's winning any game you tell the other players something else I'm gonna throw a rock the next time we play paper rock scissors are you yes can I trust you you lied so there's a game theory game called the signaling game and guess what signaling means jack signaling means basically nothing so the problem with these games is that there's no disincentive to signal so signaling is the optimal strategy but in vs games signaling generally doesn't actually bind anyone to anything now the question is is there ever a case where you would actually want a signal and it could benefit you so for example in paper-rock-scissors is there ever a case where signaling could help me out so only in terms of psychology only in terms of trying to rig the guy out but game theory he's just as clever as me he knows that the only way to win paper-rock-scissors is to play randomly so it's not going to work so here's a better question can I make a threat in a game like paper-rock-scissors is there a way to threaten the other players without actually threatening to punch them with my Rockets right it's like watch out man next turn I'm throwing rock you watch out it's gonna be rock you wear so singling is distinct from making threats threats are a very interesting part of games because you cannot make credible threats unless there is one of three conditions press one you're playing a game more than once in small world to give you an example from a real game or Vinci if you played the original I always threaten anyone who's coming on the Border's the new civilization it's like if you come when you're coming onto the board this turn if you come on to my civilization I will basically lose this game and destroy you and only try to destroy you but not try to win anymore I might lose the first few games of small world because I'm doing but eventually people learn that you actually do this and then they stop coming in on top of you and now you win because their choice is to either if they attack you they lose to or don't attack you letting you win so in repeat play you can make credible threats in games there's a whole mathematical theory around threat it's only works if you play the game more than once now you need to establish the press I think of all the ramifications of that say we play the prisoner's dilemma once I can't make it thread because whatever saying we play prisoners limit ten times well if I threaten look if you defect on me I'll defect the rest of the game I'll defect forever so maybe he's got cooperates and I cooperate all good so now by both of us cooperating we're king-making we're gonna win is there any reason for me not to defect on the 10th term he can't punish me for it so it's exactly ten games we know the tenth game is the last game so I should just affect on the tenth turn now I get more points I know he's gonna defect on the last turn because a giant is clever as me that's right nobody's got any smarts more than anyone else does we're both completely rational we both know this is the last turn his threat is completely worthless oh dude effects on the 9th turn but I know he knows how effect on a turn you see where this goes and everybody loses the secondary is the scene from The Princess Bride the second way to make a credible threat is psychology this isn't game theory but it's like collagen you can wake people out you can play head games with people and it totally works in the real world the Third Way and the reason I pictured a steering wheel here is example used in the previous panel let's say we're playing the game of chicken now they're gonna be in rows classic chicken 1950s rocker chicken we're going to drive cars and each other whoever swerves loses so if we both swerve we both lose if neither one of the servers we both die if Scott's words I don't I get the girl so let's try to make a threat I'm not gonna swerve I take my steering wheel throw it out the window I'm not gonna swerve so what has God done he's changed the nature of the game he is basically by taking a steering wheel out he's removed his own agency he didn't tell me what he's gonna he did not signal what he is going to do he already did it I can't have no choice but to swerve and lose the game B or to die along with Scott so I'm gonna swerve Scott's gonna get the girl but I'm not gonna die the decision was already made the whole like quantum state of the game collapsed down and the game was rude so the way to tell if signaling is good in a game or not right is it will help you in a game is show someone your move if showing someone your move makes you win signaling is good in that game if showing someone your move makes you lose signaling is bad in that game let's do Rogers as I signal I've already thrown the rock that didn't help me at all throw me the steering wheel out the window totally helps me makes me win makes the only choices for him is die and lose so just keep in mind the difference between signaling and making threats and threats have to be credible in game theory if a threat isn't credible it does not exist it's not a threat it's just head games so to use another game one of these toy games we're talking called Boosh field exists in many places it's also known as the game of pure strategy or gulps and it's a very simple game I guess hey it's in El Grande take a deck of cards and you split it up to have three players you give each player suits of spades hearts diamonds then you take the club's you put it in the middle each on every turn you flipped one of those cards up randomly it's worth the number of points of its face value you all secretly bid one card from your hand or ever play the highest card gets it in the case of a tie no one gets the card and you continue it's known as the game of pure strategy because what is your strategy in playing this game and it might seem like a really simple game but it's actually not how am I going to with we all have the same amount of cards we all have one ace we love one King how am I going to get more points than another person so if you start this game find out that exist a bunch of other games in fact the game it exists in I might've signaled this is El Grande a mechanic of Elrond days you have bidding cards these bidding cards determine who goes first in picking roles they also determined some other things so the lower cards that let you go last having more people on them they give you more stuff but the point is that you're basically bidding just like goosh field from this hand of cards to decide the order of play we played all Grande's so much they figured out that people tended to win if they went first in the third round because they could move the king and the king gave him extra points so people would want to have their 13 through the whole game and play it in the third round but because turn order determined who got to bid first and you couldn't play a card that was a tie you would have to go last in the second to last round meaning you had to go first in the third the last round so it became this musical chairs of bidding and it was just deuce field if we had learned about goosh field and played it and studied it we could have won out around there now goose Ville is an actual game you can play it just grab deck of cards get three people and try to bid on and win the most points of calm you might think well to get the ACE I got to bid the ACE right well what if somebody else ride decides what you know what for the ACE I'm gonna bid the two and for the King I'll bid the agent for the Queen I'll bid the King and write it so yeah let someone else have the ACE I took every other single card by bidding one above well we could take that a step further okay I won't bid on the king or they so I'll just get the Queen on down by bidding the ACE on the Queen and so forth right and eventually you're pitting the ACE on the two now it gets much more subtle than this because there this is a game of strategy it gave a pure strategy what if someone's acting completely randomly completely ran they just shuffle up their Gucci field cards without looking and bid now on one end that might seem like a very good strategy it is trivially beaten by a little more complaint strategy always play the card that is the face value off the card that came up but that strategy doesn't work against the players not acting randomly because if I see Scott doing that I play n plus 1 and you can see how that escalation happens well I'll always be here by one but he knows I'll beat it by one will beat me by 2 so that's cycle and that's track what is the good strategy to play this game if you can figure that out you can win a lot of board games and a lot of other games that include goosh feel inside of them but the key there how do you figure out what someone else is doing how do you figure out if another player is acting irrationally if you can figure out that someone's dumb or irrational you can use that to your advantage so Colonel blotto I couldn't find a picture of an actual colonel whose name was blossom I was very disappointed against the Colonel blotto game exists in El Grande oh you'll say Colonel blotto is very simply say you have three regions and you have ten troops you send a number of troops simultaneously to each of those regions and the other person does the same and in your review whoever wins the most regions wins the game you need to win two regions out of three to win how many troops do I allocate to each region to optimally win the game now you could play the blotto game with people it's very simple game if you study the blotto game you'll see it exists in other games in El Grande look at this it looks like a bunch of troops in a bunch of different regions and Loan the whole there's victory points for having the most troops in a region at a certain time now there's a whole mechanic of getting troops onto the board it's not pure Colonel blotto but if you understand fundamental concept of the idea of how do i allocate resources between a number of disparate places when someone else is doing the same to maximize my payout you'll find that that exists in the majority of games you play so now we're going to define some more terms because this is where a game theory gets even more interesting perfect information is a construct that exists in game theory people usually define this at the beginning of any talk about game theory but it's usually not very useful perfect information means something very specific it means I know everything that has happened in the entire course of the game up to this point I mean you know how many games do you play where it's like you don't know everything you don't Starcraft is a father war you don't know what the other guy did for the past five minutes cuz he shot all your Scout side of this guy right you know a little bit you know he has the things that you scouts out of this guy but that's about it right maybe if you play maybe without the father before or if you play chess it's like you can just rewind and look at every move that was made there is no secret thing that has happened nobody's holding a hidden card that they've drawn that you don't know about right there are no mysteries whatever both players have all of the information it is perfect no this has certain ramifications but it does not have any effect on the solvability of games a lot of people don't like the idea that games are solvable but games are eminently solvable a lot of people think that oh yes the game like chess is solvable because it's perfect information but you can't solve games or people like simultaneously know you can solve those games just the same there are certain ramifications of perfect information you can't have simultaneous terms in a game that is perfect information by definition if we can act simultaneously the decision that affected my turn just now I didn't know the decision that was made I was acting without knowing the perfect information of what he did so perfect information games are completely distinct from complete information games a complete information game is where you know all the rules are just why we have the hockey rules up there so I know all the rules I know the payoff matrix I know all the possible strategies you can use the game was a complete information game you know his chest is also complete information right you look at the board you know every single move he could possibly make on his next turn its equal to the number of fees he has that's how many moves well even greater than that because he could move it this way or that way so you know it's this is how many moves he can make you know every single possible move he can make in theory but there are games we don't know everything the other guy could do if he's got a hand of cards and you don't know what cards are in that hand you don't know what he could do it as an extra magic gathering now maybe you know the possibility of all the poor total set of cards he could have in his hand so rather than get into the minutiae of the edge cases of complete and perfect information consider the interesting ramifications of different combinations what's the difference between a perfect complete information game are a perfect non complete information game can you think of an example of a game that has perfect information but not completed for me you know everything that's already happened but you don't know everything that could happen you don't know the rules and I got a toy example is a game where we're playing chess on a board with chess pieces we make chess moves every turn I win if I get my king two faces up and one space to the right if I get him to that square I immediately win Scott wins if he does some other thing we don't know what the two of us are doing I don't know what he's after he doesn't know what I'm after it's a perfect information game but it's not a complete information game so think about perfect and complete and practically think about every game you play is it perfect is it complete and then think about that game in terms of other games that are the same combination of perfect and complete and you'll start to see a lot of really interesting parallels between all these games so most people when they think about game theory I think about analyzing games solving games you know how we got into game theory Scott I went to the RIT library and I saw a book of one of those blue library bound books and you said game theory on the side of it I'm like I like games it's a library is free and I will take this back to the apartment we were really into German board games like we just learned about Settlers of Catan and carpa so this is in the year 2000 we go to NAS blew our minds so we decided that we're gonna double down on this we wanted to win these games so let's read these game theory books it's all about hawks and doves and old people there's lots of math so we're gonna talk about how to analyze games how the concepts of game through your use analyze games and we're gonna skip the math because we don't know it skies usually makes that joke so a very simple game we've talked about a lot rock-paper-scissors is there a good pure strategy for rock-paper-scissors a pure strategy means you've decided what they're going to do every time you play the game is it possible to have a pure strategy in rock-paper-scissors that is in any way effective and the answer is no so what you want to use instead rock paper scissors assault by I think a mixed strategy my strategy for Rock Paper Scissors is to play rock paper or scissors randomly each one of them thirty three point three repeating percent of the time now it's impossible to actually play this strategy as a human being because human beings cannot really generate randomness in their head very well right thank you for any of these things humans are the worst AG right it's like you might think you're playing randomly but really you're not right if you actually had a computer do it the computer there would be strings I'm like five or six rocks in a row they would be like some you know home and it was in a row over there if you have a human do what they think is random there's gonna be a lot more mixing up this is like rock paper scissors maybe juices is in a row but never let three usually now humans can get good at acting randomly is the extremely difficult skill to build and I'd recommend you try it come up with wait act randomly if anything find someone like us and try to write a string of ones and zeros and try to make it random and we can probably eyeball it and tell you if it was random we haven't added by a shooter or by you have a computer print out a random string of ones and zeros and then write a string of ones as yours with your hand printed both out and like a you know a mathematician or a probability or a statistician they'll say that one's not random you can just tell about looking at it it's it's obvious but the perfect strategy solutions your paper rock scissors if everyone is rational is to play completely randomly and as a pragmatic tip in many games if decisions are arbitrary it is in your best interest to act as randomly as possible there's a lot of games where it's like you know you've got three things to pick from and they're all pretty equal you're just the best thing you can do is shuffle them up and pick one randomly the thing is in a lot of games there might not be cards to shuffle up or a die to roll and you have to determine randomly without a mechanism and you could be said that you know a lot of you will bring a die and like use it to help them pick randomly sometimes that could be considered cheating I mean I'm gonna bring my steroids to the bike race that's okay right yeah yeah only the steroid bike race what I will do I'll let you into my secret heuristic will talk about heuristics at the end that's kind of the whole or driving toward heuristics is that I'll look at a watch or I look at a clock or something and I'll come up with some decision-making matrix like I'll always break right if but not the second hand is odd when I look at the clock I'm cheating basically now we're told the interesting part of a practical game theory is that we're not in a perfect world we know humans are bad at this so how do we be better than the perfect strategy against humans because we were detecting that humans are going to act irrationally there's a computer outer element does this it'll be any one of you at paper-rock-scissors reliably and the way it does this is as you play it keeps track of every throw you did and it figures out your cognitive biases it is mapping your brains random number generator and over time it will beat you a hundred percent of the time it is uncanny so as a person if you pointed against itself it's 33 percent obviously well unless you're using the pseudo-random number generator in which case it might figure out this right if you had say up a piece of caesium creating true random numbers in one computer and just a normal like you know intel core2duo generating random numbers and other computer eventually the cesium would be the Core 2 Duo over time or you can argue that the cesium would cause the other computer to itself become perfectly rant it would approach true randomness over time and things get tricky but we're not gonna get in all those details so there's an old heuristic for paper-rock-scissors that's very interesting this really hits on the idea of discovering the irrationality of your opponents the heuristic that I use as I figure out how many steps away from an idiot child is the person that plans assuming they are American so kids tend to throw scissors because seasoning is dangerous I mean you're not allowed to run with scissors you're not even allowed to have systems they can have rocks and paper rights but scissors like the most dangerous rocks like second most dangerous so I know a kid is gonna throw scissors more often he's definitely gonna throw scissors first so I know how to beat a monster rock and I'll throw a rock more often now that kids gonna figure it out when he's one step away from an imbecilic child what he's going to do is think I know that everyone thinks I threw scissors first so I'm gonna through the thing that beats the thing that beats scissors so if you step through these iterations she's got about 17 iterations away from an imbecile so you can use heuristics like that to figure out the other person's irrationality watch for players who deviate from perfect play and try to exploit them in fact a really good example of that in multiplayer games you've all been at that table of pacts where one guy's just not as bright as everyone else not playing as well as everyone else among smart players people who play games in her serious about him the game becomes exploit him exploit his randomness or exploit his poor play to benefit the rest of us yeah it's like Soames playing settlers or Genoa or game of trading especially right and they're really bad it's like who can rip off that guy the most right is eventually that guy he's playing so badly but he actually ends up mattering more than the good players it's the good players it's just like well there's a bunch of pile of free resources how many freezers gonna get out of that pile now back to this whole idea of pure versus mixed strategies the best strategies in real games tend to be mixed strategies if I go craftsmen captain every time I play Puerto Rico I've become a very predictable player and it's very easy for Scott to exploit that I'm basically acting irrationally by having a too predictable of sort of mechanisms in the strat where you can't do it so I'll have a strategy like I'll play craftsman captain 80% of the time but 20% of the time I go factory now anywhere just a pro Rico a lot those should be reversed factory is the game winner factory because like it is a good mod for Puerto Rico you switch the prices of the factory in the University and anyone who starts with an indigo gets one doubloon extra to start with it really makes the game crazy one way to solve games is brute force just try every possible combination now tic-tac-toe has about 20,000 unique board he's like place I wish everyone in this room is solved ticktick now those are redundant but that's not really the point connect four is somewhat more complex checkers that's the ten followed by 2000 know how that notation works 2004 was solved many years ago there is a absolute solution to connect four checkers was solved several years ago by some Canadians with some crazy computers it took 19 years and 200 computers to figure out checkers the solution to checkers is as you play perfectly both players can guarantee Utley force a drum so the game is a draw if people play perfectly chess is somewhat more complex that's actually a rough estimate we don't even know how many possible positions there are in chess it is somewhere between 10 to the 43 and 10 to the 50 something and go in size go board is that that's a 19 my 19 go board go will probably never be solved and the bottom computer is some ridiculous test will likely not be solved with the technology we have available it's true now you are not going to prove for sir games but you can understand games that can be brute force and understand how complex games are and how strategies for mine and just even knowing how complex a game is gives you a lot of insight into what heuristics to use to be better at that game this is gonna make a lot more sense at the very end of this like so just remember that brute force is basically petered out already with modern technology combinatorial game theory has a relatively recent and relatively the theory of games and I learned it from my seventh grade math teacher you talkin again called me in the name is very similar draw some number of sticks in three or four or five columns and every turn you take turns removing some number of six from a color you can remove sticks from two columns at once you to pick a column and remove some number of sticks from that country whoever picks up the last stick loses so you want to leave the other person with one stick left in one column so that they're forced to take that stick cuz you have to take at least one now it turns out combinatorial game theory which is the idea that if there is a game and another game and you add those games together you can do a fairly simple math and determine like if I've solved this game and I've solved this game and add them together I know the solution to this game by using combinatorial game theory so for example NIM with just one stick guess what the player who goes first loses because they have to pick up that one stick NIM with two sticks is a different game and then with two sticks the player who goes first wins because they pick one stick in the second player takes the stick then with three sticks if we're still wins player one wins in other words live with one stick plus min with two sticks equals name with three sticks which is player who goes first wins right therefore right it's player goes first wins plus player second wins equals player first wins you can combine the games with a plus sign and get another game and know the answer to the third game by just adding the first two games together no what's interesting is that some games are more resolvable by in theory than others tic-tac-toe is actually surprisingly difficult to express in that in that way it's hard to solve tic-tac-toe as a person using combinatorial game theory but if you know the solution to them if you've looked at the equation you can calculate in your head who wins no matter how big that it could be a million six in the first one 9,000 in the second one eight and the fourth one 40 in the fifth one you can look at it and immediately know who's gonna win assuming people play perfectly assuming people play perfectly the way to get good at games like this and all the games that are derived from games like this it's too plain in literally all of you should around pax take pieces of paper and plain in de straw like five six three six two six take turns removing some number of six and the last person to pick one up loses and you'll start to notice all these patterns you'll notice if the game gets to this state where there's two sticks here and two sticks here this player always win because some game with a big number of sticks you played in a bunch a bunch of sticks are missing and now it's a new game it's the game with only that many sticks you might as well have started with that many sticks and the answer to the big game is the same as the answer so eventually you're gonna figure out you're not playing to get the game to the end you memorize this list of 20 conditions that if you get to that you win you're now this playing to get the game to that point and then the game's over because you know you win so if you're doing that and other people aren't you are way ahead of them in terms of winning this game and after you do that you'll start and you'll start to figure out like the fullness of this game then I want you to go and read a book by Richard Garfield and some other people called characteristics of games in the back of that book there's an appendix in that appendix he explains the math of combinatorial game theory if you figure out NIM and get good at it and read that you will understand this surprisingly complex area of mathematics in a surprisingly intuitive way and you'll be better at games that involve this because you have learned that pattern recognition is the key to winning games if you can recognize the pattern that we the game before someone else this guy's playing for the end you're playing for the pattern he doesn't see what you're doing you're gonna win because you're going for something he doesn't realize it's important yet more importantly players are playing in if you don't know how to play you're all going to do the same thing it's how humans solve problems you're going to act randomly until you have figured out who won you do this in every game you play whether or not you realize it if you play go how many of you play go we had a few all right so go has almost non-existent heuristics both directional and position which we'll talk about in a second as a result you don't know how to evaluate whether or not a move you're making is good or not it takes a lot of learning to even get to the point of knowing if you're doing well and go as a result you will play randomly until you notice oh that pattern appeared now I can circle that thing and win so every time you're playing games think about this what am i doing and the answer is almost always going to be oh I'm acting randomly because I don't know what to do so as soon as you get good at the game try to recognize what other players are clearly acting randomly and use that to your advantage you'll know if they've solved the game or not you know what to shoot for so this is kind of we're building up to this heuristics now I mentioned it once I'll mention it again there's a book by Richard Garfield you may know him he made some moderately popular game Magic the Gathering runner yeah so this book if you're interested in games game theory at all you should read this book every one of you should read this book we're gonna throw out do you care enough to be in this room here is this book yeah so we're gonna talk about something called heuristics now heuristics are part about humans work they're part about games work for the whole point of this because you even if you're super good at Puerto Rico I'm super good at Puerto Rico I do some math I do make some calculations in the course of the game I am NOT calculating the entirety of the game that might be larger than chess that might be more different possible for me to do I'm not that smart none of us are I'm using a heuristic figure out how to play the game and I'm using math to augment that heuristics this is a diagram of something called the gaze heuristic the gaze eristic is something that human beings use and you all use it if you're running to catch a ball someone throws a ball like a baseball and you're trying to catch it maybe you're crazy and you're using differential equations and calculus to calculate the trajectory to predict where the ball will land and then you're running to that point but if you watch people they don't use someone throws a ball they're not looking at where they predicted it landed and running to it they're looking at the ball and running they are not predicting where the ball is going humans almost have no ability to predict where something will land based on what it was shot to do it you were playing baseball and you could watch the guy swing and hit and then they closed your eyes and you had to go and stand in the spot where it was gonna land and catch you like that it's not gonna happen you think you can britta queer things will land you can't very quickly and even if you do learn how to do that your body will not do that when you're trying to catch something it will fall back on the gays here is it this is built into your brain your head will lock at an angle looking at the object and keep the object at the same angle no matter what and mathematically it just so happens that if you do that the ball will end up in your hands because you have to move forward it is forcing you to catch the ball no matter what so think about this the next time you're playing baseball imagine realize that your next stop moving you're locking the gaze that's take your wrist it is a sort of soft or fuzzy way a rule to follow that if you follow it is pretty much guaranteed to make the ball land in your hand or if you're doing what I've said and you're thinking about this it's gonna hit you in the face that's why they say keep your eye on the ball so in games there are two kinds of heuristics directional heuristics and positional heuristics so directional heuristic is which direction do I go right method you are using to figure out do I do this or do I do that you have multiple choices or some kind of decision to make the heuristic directional heuristic is how do I figure out which of the decisions I make which way will I go for example one that I like to use is in power grid when I'm bidding on power plants right I will look at the power plant and I'll say all right how many that power plant to win the game it's a big one I'm needed I want it how much am I willing to pay for it well if I buy that I will have to spend this much money to buy resources this turn I put that money aside then I say okay how much money do I want to spend on houses this turn I would can power up to this many houses it would be nice to buy that many it will cause this I put that money aside and the remaining money is the money I'll spend in the powers on it and not a perfect strategy but does very well very good straight off loads more complex processing from snaps brain because he just follows the rule he came up with to a fault and he puts the money aside on the table and I see what he's gonna do know and I know what you're doing that's why when power grid you don't so I mean look in all games directional heuristics it's telling you which way to go do you want to fall off that rickety-ass bridge into the deep chasm the darkness below her eyes the screams of the undead right here and you know what in the game if you walk up here you're fine look up here you die unless you come back after drinking potion - I don't know anyway so think about what I said before with go-go has no reasonably useful directional heuristics for beginner players they just don't exist so when you're playing go you're just acting randomly by default your first directional heuristic is act randomly your second direction with your stick is act randomly until I figure out how to win the game or act to maximize victory points I'll just do whatever gives me the most victory points that's usually not the best strategy but you know what it's better than completely rent if you play a game that everyone at the table just read the rules to it no one knows how to play best thing to do is to skip over the act randomly and go straight for it get the most victory points you will win that first game 99% of the time now you have to construct increasingly complex heuristics to know what to do a directionally heuristic and go involves such crazy crap as how many areas of the board are still alive how many pieces are there still they're going to be played because you know how to calculate that is the other guy working on this area board or this area of the board you have this whole huge heuristic in your head but you're not calculating that because as we know you can't calculate Chuck go I was gonna say chess and checkers at the same time they said go instead I'm Scott simultaneously yawning that's right so horsing yeah what you're gonna do is you're gonna recognize patterns and go you know these very tiny sub games just like in NIM combinatorial game theory you recognize this one pattern is a win for this player this one pattern is a win for this player if this pattern exists do this and this and this to turn it into points for you to win the game you build this lexicon of little strategies of little games and you use those to construct a directional heuristic and that is how you win games game theory just let you construct extremely effective heuristics without having to do the math every time in the panel before I said learn modulus math when I play games with rondelle's I use modulus math to figure out the cycle and then I use that cycle to populate my heuristic knowing modulus math lets me calculate that very quickly and because we're running out of time positional heuristics I put the blasts are actually more important who's winning in game who knows it's almost impossible for people to actually know who's winning games even in places like Carcassonne you can see there's a victory point track you can see someone's at the front of that track they already have 50 points no one else has anything and winnings at the back I've got less points to everyone but money on the board that rims farm has a whole bunch of farms in it and we can also see that he's got a guy a big meatball in a city that's will likely finish and it's worth like 30 points so rim is in first place so using the positional heuristic of count the points on the board is much better than look at the scoring track which lies to you Mario Kart it lies to you yeah it says Mario's in first place no blue shell he's not in first place guys and you might think no no he was in first place they caught up no he was never in first place you were just using the wrong position heuristic so going back to all this gamester stuff no dirty stuff knowing where you are whether or not you're winning or losing is crucial to form your heuristics because for example if you're falling behind in a game you want to act more randomly you want to attack decreasing odds for greater gain because that's the only way to catch up you have to actually know you're behind a lot of people lose games they don't realize they're behind right like you know football team the only way you can win now guys do a Hail Mary but what if you didn't know that you were losing you looked at the score Barney's right you thought you're about to win and you're dumb but the point is that you construct these heuristics by using the pieces of the game theory games from that Wikipedia page that you all need to go and look at that list game theory games and the more of those games you study and understand it'll take you a few minutes to get the gist of some of these and you'll start to be able to construct really advanced heuristics and none of your friends are ever gonna want to play games with you again now the point is though beyond all that is that you have to actually play these games because sure you can make the best heuristics in the world you can study the game theory memorize everything we just said you've got the perfect strategy to beat all your friends in Puerto Rico but if you don't actually play with people you're not gonna be able to do that intuitively you're not gonna be able to do it quickly you're gonna be stuck calculating people are gonna be yelling at you to take your turn you're gonna lose count of the cards and then it's all over no one wants to play with you the only reason we know this stuff is a combination of reading Wikipedia reading that Richard Garfield books and playing Puerto Rico 20 to 30 times a day over the course of entire summer yeah a lot of people right you don't play games enough right as I use people that come to tabletop it's like I put a power grid a few times dude there was a time when I was my apartment every day all right maybe twice a day right and that's you have to do something a lot to get good its practice right but practice for one game transfers over to another so you really just play games like crazy if that is what you're in to do it more a lot more and on that note I'm afraid we have to end because we all have to go on shift as enforcers in negative two minutes no I haven't earlier kisses I'm amazing and that's done so we will not have time to take questions if you take one of those flyers email us a quest Jose Flyers are really old those flyers from 2005 just ignore everything on them but the URL we will try to put the video of the previous lecture that you all miss because you were in line for this one online and we will also try to answer your questions perhaps in video form associated with the video of this panel or perhaps in the newsletter you can show it to your friends to make them better games you cannot show it to them so you'll be pin the game [Applause]

Channel: Rym DeCoster

Views: 49,026

Rating: 4.8549514 out of 5

Keywords: PAX, PAX East, Penny Arcade Expo, Games, Game Theory, Game Design, Heuristics, GeekNights, Rym, Scott, Convention, gaming, tabletop, videogames

Id: hZDxLi6Xc40

Length: 63min 27sec (3807 seconds)

Published: Mon Apr 01 2013