Forum adverts like this one are shown to any user who is not logged in. Join us by filling out a tiny 3 field form and you will get your own, free, dakka user account which gives a good range of benefits to you: No adverts like this in the forums anymore. Times and dates in your local timezone. Full tracking of what you have read so you can skip to your first unread post, easily see what has changed since you last logged in, and easily see what is new at a glance. Email notifications for threads you want to watch closely. Being a part of the oldest wargaming community on the net. If you are already a member then feel free to login now.

Hi all

first off wow my head hurts. Ok i don't know game theory, i've heard of it but thats about it, I can't say whether its applicable or not but Nurglitch i'm interested in what you come up with.

Arn't you going to have problem with the whole rational thing? as scubman said people arn't rational, but you also have the problem in 40k of people not recognising somethings worth. You mentioned that a rational play will always pick $2 over $1 but what if the player doesn't know $2 is greater than $1. As was mentioned newer plays often try to table the other player rather than attempting to hold objectives/limit losses.

I would ask you try and keep this layman friendly for those of us with out math qualifications, however if this thread isn't designed for layman then that cool and i'll be quiet.

Nurglitch wrote:EvilEggCracker:

Well, I suppose someone had to go ahead and embarrass themselves in this thread. Way to take one for the team.

Not at all. I just feel that this entire discussion is inherently flawed - it's theory.

You have to remember that you're applying it to a game with random variables. Strategy and tactics are all too fluid to define as "Hawk" or "Dove". Ultimately, this discussion is pointless and has little-to-no relevance to the actual game.

I just wanted to put that point across in a more "fun" way.

Edit: Also, if you played a mass infantry Imperial Guard army, you'd understand why I'd want to strap the bayonets on and start marching.

Then why do you insist in detracting from this thread? I for one am enjoying what he has to say, and your posts only serve as a minor annoyance and nothing else. You should stop posting here.

Hesperus wrote:I like game theory, and I like that you know game theory, but I don't think the game theory is doing any work here at all. Consider this post an attempt to figure out exactly what you're saying.

First, a technical point. The prisoner's dilemma is a simultaneous game. 40k is a sequential game. The solution happens to be the same either way in this case, but simultaneous games in which there's no dominant strategy come out different if you make them sequential games.

Second, I don't really see where you're getting your payoffs. Where do you get these? I guess you're saying that, if the other player plays to win and you play to not lose, you'll beat them. And here your terminology is confusing. Shouldn't the player who plays to win have a better chance of winning? Otherwise he's not actually playing to win; he's just playing like an idiot. Maybe I simply don't understand your terms.

Maybe what you mean by 'play to win' is 'play riskily,' and by 'play to not lose' you mean 'play conservatively?' That makes your argument at least coherent, but it also makes it wrong.

It's wrong because risky plays don't necessarily have lower expected payoffs than conservative ones. Risk-loving people are just as rational as risk-neutral or -averse people. They just have a different preference when it comes to risk.

Now, you could be making an empirical claim, that in general risky plays in 40k do have lower expected payoffs than their conservative alternatives. That's very interesting if it's true, but (a) it doesn't require any game theory analysis, and (b) you haven't offered much evidence to prove it. Indeed, most tournament winners run pretty risky lists and play pretty risky games. On your payoff scheme, they should be losing to conservative players, but they don't.

Please correct me if I've gotten something wrong. I like the idea of applying game theory to 40k; I just don't think it works in this instance. Applying it to list-building has some potential, though. Maybe you can get us past the inane rock-paper-scissors analogy.

I'm very much on the same thought process as this. the hawk-dove talk is interesting but i don't see exactly how it works. I see the idea of playing conservatively as legit, def if you think of the article "way of the water warrior" which seems to show a viable way to play a conservative list that requires careful planning, but it doesnt seem to play to not lose.

and wha t exactly do you define as risk or rationality in a game such as 40k. Is rationality keeping objectives in mind? What comes to mind is a Land Raider wrecking havoc on my forces, I rationally need to stop it since it is hurting my chances of having troop choices to grab objective, but it could be a risk to take out that land raider. is that too situational for this? I like what you're saying, but I have trouble grasping how exactly it comes into play when I am looking at the field of battle and the various choices I can make.


Automatically Appended Next Post:
could you also maybe try explaining the prisoner's Dilemma in a bit more detail, not to derail the OP. I am really interested in this but I am having trouble grasping it

Firstly, I personally would like to thank Nurglich for this fantastic thread. As a Comp Science graduate, this is right up my street.

As I'm currently on a train I will reserve my full comments for later, but I do have one question - wouldn't the game tree for a game as compex as 40k be absolutely horrific in scale? You'd need some very tangible heuristics to search it effectively, and I'm not sure what you could use.


Automatically Appended Next Post:
@sageheart

The basic prisoner's dilemma is as follows.

You have prisoner A and Prisoner B, both arrested on suspicion of tge same crime. Both are interrogated seperately. If They both implicate each other, both receive 10 years. If they both remain silent, they both get 6 months. If one implicates the other, but the other remains silent, the accuser walks free while his partner is jailed for life.

To help clarify:

The reason it's called 'the prisoner's dilemma' is because, if both prisoners act rationally, they'll end up with a result that's worse for both than if they'd both acted irrationally.

Pretend you're prisoner A. You're thinking about what to do. If prisoner B squeals, then you have a choice between squealing and getting 10 years, or staying silent and getting life. If B stays silent, you have a choice between squealing and going free or staying silent and getting 6 months. In either case, it's better for you to squeal.

In game theory terms, squealing is the dominant strategy: no matter what the other player does, you should do it.

This means that, assuming both actors are rational, both will squeal, which means both will get 10 years.

Notice that, if both had stayed silent, both would have gotten 6 months, the jointly-optimal result.

A strategy is a set of choices that covers all possible events in the game. A Nash equilibrium is a set of strategies such that neither player ever regrets one of his choices.

In the prisoner's dilemma, the Nash equilibrium is:

For A: If B squeals, squeal. If B stays silent, squeal.
For B: If A squeals, squeal. If A stays silent, squeal.

It's a Nash equilibrium because both players are satisfied with all of the choices in their strategy: given what the other player does, they don't regret doing what they do.

Does that help? Also, Nurgltch, correct me if I messed anything up. It's been a few years.

I have heard of this before. Thanks for clarifing. It makes me understand the concept Nurgltch is explaining a lot more. The Dove-hawk confused me but this makes more sense to me.

So the idea behind this, tell me if i'm wrong, I really want to understand this as well as possible, is that if both players are acting rationally, both will squeal since it leads to the best results no matter what the other player does. and this becomes the way to play with the focus of not losing rather than to win. If you had not talked you had the outcome of life or freedom but no middle ground.

My friend, a neuroscience/math teacher at NYU, explained something like this to me in regards to ML. He was talking about some people mathhammer 2 orks with rokkits as being just as optimal as 1 Sm with a ML.

He was explaining this is not true, since the purpose is to hit one tank, you just want to get that hit, and if we assume a SM always hits, and the orks get either: no hits, one hit, or two hits, you would rather have the SM since you get that one hit no matter what. I believe that is how he explained it. If you have a chance of failing it isn't always the best option since it is more risky.

If i have this correctly understood, I would then wonder how exactly one puts this concept into game terms, and "squeals" in the game. Does one do that by not taking risks?

Anyone wanting a slightly more in-depth but very readable intro to game theory (and, in fact, a kind of history of economics and economists in general, most of whom were a right rum bunch) could do worse than look at a pop science book called Doctor Strangelove's Game.

Ken Binmore's A Very Short Introduction to Game Theory is also very accessible for people, and contains many amusing anecdotes.

Something Mr. Binmore points out about toy games like the Hawk-Dove game is that they're simply little things used to illustrate game theoretic concepts, and I related that in the original post. Neither the Hawk-Dove game nor the Prisoner's Dilemma apply directly to Warhammer 40,000.

Where they do apply is getting people to understand the concepts when they're applied in new and novel ways.

Which is why I originally proposed a verion of the Hawk-Dove game called the Sequentially Iterated Hawk-Dove game, wherein the dominant strategy is to play the Hawk tactic for whatever number of finite iterations.

The Sequentially Iterated Hawk-Dove game has more in common with Warhammer 40,000 than its predessors, the Hawk-Dove game and the Iterated Hawk-Dove game. Specifically, it is sequential, or "IGO-UGO" in the vernacular.

In my last post I proposed two other properties of Warhammer 40,000 that an accurate game theoretic model should have, namely an account of resources (time, space, material), and uncertainty in non-player random elements.

While the latter is covered by Statistics, the former pays out differently depending on what's known as the evolutionary perspective on game theory, as opposed to the rational perspective we've been exploring so far. I'll go into it further in my next post.

Remember that the game theoretic account of rationality is simple, it merely assumes that players consistently prefer $2 to $1, all else being equal. That's all there is, consistency and a preference for better. As assumption of rationality go, this one is pretty spectacularly successful.

Remember that rationality is fixed to the goal of the game, rather than to any sub-goals, so that in Warhammer 40,000 the rational player consistently prefers to win rather than tie, and tie rather than lose. Victory points, kill points, and objectives are all ways of expressing and mediating this preference.

And even if one can't trust one's opponent to be rational even according to this broad definition, then one can simply go with the dominating strategy rather than seek the Nash Equilibrium.

Regardless, I believe the modifications offered concerning the Sequentially Iterated Hawk-Dove game in a previous post could bear some examination. The modifications are again simple, to demonstrate what they do: A limit to the money being drawn on (a shared pot of $10), and a single player-turn delay in the result.

Okay, so I'm guessing this is just a discussion on mathammer? Okay, fine

I can appreciate math hammer. It does have its uses. But I really hate when people justify how much something sucks with mathammer. Or justifying how good something they have is. I don't care. Stfu and play, and stop hiding behind your math.

I.e: "Dude, why are you taking terminators? On average, my inquisitor lord's acolytes will wound one per turn, and my lord's force weapon will auto kill one guy per turn. Then you take your morale check, which you'll probably fail...."

Feth off buddy. I think you forgot to factor in that my bolters are AP 5 and will have probably torn apart your stupid 5+ save guys before they even get into assault, and that I'll probably be shooting lascannons into the unit from my land raider.


That's just an example I came across today

I'm not sure if this is really mathhammer as much as the metaphysical psychlogical world of wh40k. Almost like the weird demention of the stack in magic the gathering. Don't mean this insulting like, just its about abstract theories of game mechanics rather than just number bashing

that was prob a bad example.

@Nurglitch: 2 things.

1. Any good books introducing evolutionary game theory? I spent [too much money] on a college degree and my game theory class didn't even mention it.

2. I'm thinking you should edit the first post to start with: "This thread is NOT about regular mathhammer. This thread is a (very) brief introduction to game theory and explores its application to 40k." Maybe that'll cut down on the irrelevant posts.

I guess my post wasn't clear. I've taken a college-level game theory course. Apparently it was a crappy course, because I've never heard of the evolutionary perspective on game theory. Are there any books on that specifically?

Oh, and if it's just applying evolutionary psychology to game theory, I'm considerably less interested.

I'm asking Nurglitch, really. He mentioned the 'evolutionary approach' in his last post. I don't know anything about it, and I'm curious.

Hesperus wrote:I'm asking Nurglitch, really. He mentioned the 'evolutionary approach' in his last post. I don't know anything about it, and I'm curious.

http://plato.stanford.edu/entries/game-evolutionary/

You're welcome. Google is your friend.

Nurglitch

Thank you for explaining the rational/irrational part again e.g. 2 being better than 1 was do with the overall outcome of the game (win better than lose) rather than the indiviual elements of play. That had cleared it up a lot for me.

Gotta say the whole playing not to lose thing works. I made a skarbrand/slaanesh list counting on the fact that I would have higher initative then my opponent. Turns out however that there are several eldar units which are actually faster on the charge then slaanesh. Realizing this I decided to try for the draw and not the win. Making sure my single base had plenty of defense I ate the incoming eldar units as they advanced on my single base. The game went to turn 6 which gave me time to get a single deep striking unit close enough to his base which had been left mostly undefended due to his aggresive play style. Thanks to playing for the draw I was able to sqeak out a win in a game I should have lost by all rights.

I know nurglitch is going to be working on a model for 40k, but I think that a lot of people are missing some of the underlying principles here, and not just in terms of hawk/dove.

One key principle here is the idea that as rational people we want to maximize the outcome of the game. This is one area where 40k differs from hawk/dove, in that cash result is the only outcome worth measuring in hawk/dove, while 40k can have varying different positive outcomes for players.

Approaching this from the mindset of a competitive player, a goal is probably to win tournaments, than you at least have a defined outcome: position at the end of the tournament. Even then, you need to ask yourself what your true goal is: achieve the highest possible placing, or maximize the chances of finishing first? As tournaments get larger, the two approaches blend into one, but at smaller events avoiding the hardest opponents is more critical to placing highly than winning every game.

Let’s assume you want to maximize your chances of finishing first. If I take anything from hawk/dove, it is that you should try to control your own fate. Taking a list that has great strengths, but huge exploitable weakness is a massive risk. Rather than maximizing the number of armies you can easily table, focusing more on reducing the number of armies that can easily defeat you is more critical.

40k, probably more than most games of skill, does not allow for masterful moves that gain major advantage. Games are won or lost based on exploitation of mistakes, not by brilliant moves. I’m not sure what Nurglitch is going to write, but that’s my message: playing to not lose isn’t about style, but about realizing that the player that makes the fewest negative moves will win. No amount of brilliance can overcome a mistake properly exploited by your opponent.

I know! I know! But I won't answer.

Here's a hint, though: Nurglitch gave it away in his first post.

Polonius:

I'm not saying that the rational person seeks to maximize per se, since the definition of rationality of consistently preferring more to less applies equally well to satisficing as it does to maximizing. We should probably come back to this later once the machinery has been developed a little more, but for now I'll suggest that it's worth keeping in mind we'd need to add special conditions to distinguish these goals by the terms of Hawk-Dove.

Here's the solution to the Dominant Strategy in the Sequentially Iterated Hawk-Dove (5) game.

I'll start again with Hawk-Dove. In Hawk-Dove choosing Hawk is the dominant strategy because it is the best answer to which ever strategy may be played by the opposing player, scoring [3:2],[1:0] in favour of Hawk.

If we consider Hawk-Dove as a game consisting of one iteration, we can extended the Hawk-Dove game some finite number of iterations. This means that we can see the various end-states of the game, and work backwards. In the Hawk-Dove we only have to start from the last iteration and we're done at Hawk. With no reciprocity to consider, merely rationality and common knowledge of the choices and costs involved, the choice is simple at each (and only) iteration.

In the Definitely Iterated Hawk-Dove game, the version lasting five turns, we start at the last turn and work back. In the last turn there is likewise no reciprocity, while rationality and common knowledge holds. The player should play Hawk. On the fourth turn, when one might otherwise be worried about reciprocity of action on the fifth turn, one knows that the next turn the game is over so it'll be Hawk. Knowing that the other player will play Hawk next turn regardless, the turn becomes the Hawk-Dove game. Using backwards induction you work back to turn 1, which is again Hawk for the reasons discussed.

Because the ending is fixed, no reciprocity is available, since to play Dove at any point is to do worse than play Hawk, and the dominant strategy is [H, H, H, H, H].

A strategy of [D, D, D, D, H] would score $1 to $13 in favour of this [H, H, H, H, H]strategy. In fact, the best you can do against it is $5 to $5 using itself. Therefore it is the dominant strategy. The same reason to play H on the last turn applies on each preceding turn because you can work backwards from the fifth iteration, making the dominant strategy known.

Is this thread ever going to get a point where it correlates to 40k?

DarknessEternal:

It will, eventually. We're currently on the business of applying the game theoretic concepts to sequential games having first been applied to simultaneous game.

If people would stay on topic and post about it rather than riding their personal hobby horses, this might go somewhere a little faster.

Now that everyone understands how to derive the dominant strategy in a finite sequential game, it's time to start building in the other concepts of reciprocity, resources, uncertainty, and so on.

Reciprocity is the result of uncertainty with regard to the ending of the game, as knowing when the game ends makes Hawk the dominant strategy for both the Hawk-Dove game and the Iterated Hawk-Dove games. If it is not public knowledge when the game is going to end, and hence the best strategy on the last turn, then players have to go turn by turn instead of using backwards induction to determine the dominant strategy.

But before I go into that, it's important to discuss the concept of the game tree. In the terms of both the Iterated Hawk-Dove game and the Sequentially Iterated Hawk-Dove game. A game tree is essentially a flow-chart describing the options available to game players at each turn or iteration, and allowing players to both look ahead to the consequences of their choices and look back. The game tree for an Iterated Hawk-Dove game of three iterations will have three nodes, with each node having two branches (Hawk and Dove), whereas the Sequentially Iterated Hawk-Dove game of three iteration will have six nodes, with each node having two branches (again, Hawk and Dove).

Making a game tree will help people understand why Hawk is the dominant strategy for Definitely Iterated Hawk-Dove games, and discover the dominant strategy when the number of iterations is not definite. This is important because, as mentioned, standard 5th edition Warhammer 40,000 games end randomly and so indefinitely iterate.

Can anyone tell me how many nodes the game tree of Warhammer 40,000 will have?

The branches are more complex, since each unit in an army has three sets of sequentially oriented choices (Move, Shoot, Assault), but we'll start building in resources (units) and uncertainty (dice) in a bit. Once these things have been discussed, then we'll be able to discuss reciprocity in Warhammer 40,000 in more exact terms.

If I'm reading this right, 40k would have atleast 10 nodes (if we aren't counting deployment as a turn for each player) to a maximum of 14 nodes.

I'm not sure if a node for 40k would be where each unit has a choice, or if it would be for each phase.

Come to think of it, I don't think it would make sense to base the nodes off the units since the game is played sequentially based on phases, therefore:

If the nodes are for each phase, and the branches are choices you can make for each unit, then there would be 3 nodes: Move, Shoot, Assault. The set of branches would be a complex array of units and all their possible actions.

edit: I forgot deployment as above, so that has to be worked in somehow. However, while each of these 3 nodes repeat every player turn, deployment would be singular node that is not repeated. So based on my 3 nodes above, it would be one alternating iteration of 1 node, then an indefinite alternating iteration of 3 nodes.

okay I was wrong!

Darkhound:

I think deployment counts as an iteration/turn since the players make choices that affect the rest of the game.

Excluding that then, you are correct that a game will have between 10 and 14 nodes corresponding to 5 and 7 game turns (10 and 14 player turns). The game ends automatically after 14, and has a chance of ending on a 4+ after 12, and 3+ after 10.

Including deployment, the game will have 12-16 nodes.

This dice-oriented uncertainty makes the game indefinitely iterated, although I'd suggest that we could also treat it as a definitely iterated game with uncertainty of ending sooner.

So its only each turn that counts as a node, but not each phase?

Dracos:

Nodes are equivalent to each turn and reflect game states. Branches are equivalent to the choices that are made affecting the game state of the next turn, and hence link nodes.

Speaking more exactly, a game of Warhammer 40k will have between 12 and 16 sets of nodes, with each set of nodes containing unit states, as well as overall game states.

While uncertainty gets introduced by the dice making an otherwise definite game indefinite, resources are tracked by node, and resources includes units.

Edit: I suppose you could also divide up the nodes by the turn-states, since the turn sequence breaks the turn up into a set of sequential 'turns' that the player gets to take without alternating with the other player.

I thought that dividing it up into phases would have more value (although also more complexity) since each phase has a new board position (or game state).

edit: I guess if we do it this way you would end up with Deployment being 2-4 nodes (Normal deployment, then possibly scouts and infiltrators), then each player turn being 3 nodes. so the game overall would have 32-46 nodes.

Nurglitch wrote:
The plan is not to abstract Warhammer 40,000 to fit game theoretic principles, but to build a model of Warhammer 40,000 using game theoretic principles,

All models are abstractions simplifications and assumptions

Nurglitch wrote:
Incidentally, by 'Hannibal', aren't you referring Pyrrhus? Hannibal didn't win all his battles to lose the war...

Hannibal crushed every army he faced in Italy - his strategy to crush all opponents and therefore force a surrender however was a losing strategy. The Romans would not surrender, instead they waited him out knowing he could beat them in an open field but not in assaulting a city. Eventually he was forced to retreat without every achieving his goals even though he executed (tactics) his strategy perfectly. A pyrrhic victory is the same idea.