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.

Draocs:

You'd be right. After all the point of building this model is to have it reflect Warhammer 40,000 in all relevant ways so that players can plug in their armies, missions, and so on, and calculate strategic equilbria.

Ordinary deployment, Infiltration, Scout moves, and so on would be branches since they're the actions that players take to bridge nodes. It's important that each node has an identical set of bridging decisions, and setting actions as nodes would confuse things because actions connect nodes.

The Movement phase bridges a sub-node of any turn to the sub-node representing the Shooting phase though, but the outcome of all of these actions is perpendicular, if you will, to the game state of the next turn.

So: Game (Tree), Player Turn (Node), Actions (Branches).

Node 1 (Player Turn 1)
Unit 1 (resource): Movement (branch) -> Shooting (branch) -> Assaulting (branch) -> Node 2.1, 2.2, 2.3.
Node 2.1
Node 2.2
etc

Even during the phases, actions are made in sequence: Movement is done unit by unit, shooting is unit by unit, and assault is ordered by Initiative.

Node 2.1-2.x are each the state of the board at the start of the next turn, so x is a near infinite number?

Deleted in Compliance with the Moderators

Darkhound:

The number of states of the game will be finite in number, and not really that big as big goes. The Hawk-Dove game is good for demonstrating game theoretic concepts precisely because it is as small as it can possible be and remain a game rather than a decision problem.

Basically if you take the number of game states as being relational rather than absolute, then you can cut them down significantly. In addition, thanks to the sequential ordering of the phases or sub-nodes and their own sequencing, each previous sub-node both affects the game state of the turn and the game state of the next sub-node.

Think of it like handling re-rolls statistically: they don't increase the potential outcome, but they do modify the curve of whether those outcomes can be expected to happen.

In this we're aided by rules limiting units moving infantry from firing heavy weapons, units from shooting more than one target (barring special rules...), and units from charging targets that they didn't shoot.

So shooting wise, we only really need to concern ourselves with three states depending on the unit-resource and its target, nothing, the expected value, and the potential value.

So a unit of twenty Ork Shoota boys could charge a unit of ten Tactical Space Marines, getting 12 Orks attacking, and cause [0, 2.97, 36] casualties if they don't cause more than three casualties via shooting [0, 2.18, 40] and closest the gap between them and the Tactical Marines at least 5" in the movement phase.

That choice to assault will be nested in the choice to shoot (risk shooting them out of charge range), and the choice to move, and will be one of the options to address a different unit in this fashion.

In other words, because assaulting and shooting are directed at a single unit (again barring special rules like Fire Control, Target Locks, and Power of the Machine Spirit) we can reduce the player's choice down from a massive amount of minuitae to the question of whether or not to address another resource in the game.

By 'address' here I mean 'act in relation', so addressing can mean moving in relation, shooting in relation, assaulting in relation, etc.

By phrasing the question as 'resource' it can also address resources such as objectives, and reflexively itself (it can address itself by the player considering what happens if it doesn't address any unit - a unit of Grots going to ground in some ruins would be addressing themselves).

By making the choices a matter of addressing resources, we can parse a mass of detail down to match the choices facing players.

So what's the application for all this?

I like how you guys are attacking the theoretical premise for building the model. Your not even able to prove the premise to be false, but detractors in this thread keep trying to apply the premise directly to 40k when it has been repeated ad nauseum that we (primarily Nurglitch with input from the peanut gallery) are working up to it. Can't you just give it time and let us get there?

If you don't think it will work, then leave the thread alone.

BTW in chess you can't work backwards to make a best move. You have to calculate precisely going forward. You can have a strategy that involves getting pieces into a position, but the actual calculation always must be done forwards.

Strategy is your general plan, the "what". Tactics are how that plan is executed, the "how".

Darkhound:

The application is building a game theoretic model of Warhammer 40,000 to aid in strategic and tactical analysis.

Deleted in Compliance with Moderators

I figured it might help if people had a look at what was being made here.

I'm assuming the model is going to take the uncertainty in 40k into account. The winning strategy will have different moves for each possible outcome. For instance, say part of the strategy is, "Unit X shoots unit Y." You'll then have, "If Y loses 0 models, do A. If Y loses 1 model, do B. If Y loses 2 models, do C...If Y is wiped out do [n]."

The strategy is going to be ridiculously complex, but the theory can accomodate such complexity.

I'm very interested to say how Nurglitch plans to make this practical, though. Any complete strategy is going to be insanely complex: as I suggested, you'll need different tactics based on every possible outcome of every shooting or assault action. You'll also need different sets of tactics for each possible enemy turn, given each of your possible moves.



Let's try an extremely simplified game.
You have 2 units and the enemy has 2 units and you can only move forward or back 6" with your units (and run in the same directions) Say your opponent has first turn, and you have no control over deployment. Pretend you're on a huge table and will never have the opportunity to shoot or assault each other.

How many possible outcomes do we have at the end of the first turn?

With each of his units, your opponent can: (1) not move at all, (2) move forward and run forward 1", (3) move forward and run forward 2",...(7) move forward and run forward 6", (8) move backward and not run, (9) move backward and run backward 1",...(14), move backward and run backward 6". I'll ignore moving forward and running backward, moving backward and running forward, and not moving but running in either direction, because they're unlikely to do those.

So your opponent has 14^2 possible moves. That's 196 possible initial states for you.

You have the same options, so the total possible number of states is 14^4=38,416 possible outcomes.

Let's say the game always ends on the 5th turn. There are 38416^5 possible outcomes after the 5th turn. That's 836.7 septillion outcomes.

How are you going to model a real game of 40k? You'll have googols of possible outcomes.

Deleted in Compliance with the Moderators

So I'd like to take this opportunity to beg people reading this thread:

If you want to be involved in this thread, please make sure you have something accurate and useful to say about the interaction game theory with Warhammer 40,000. If you don't agree with the premises of game theory, or its application to Warhammer 40,000, I'm begging you not to post in this thread.


Automatically Appended Next Post:
Hesperus:

That's a good question (namely: that there's too damn many permutations of absolute game states on any given turn). Particularly when a benefit of game theory is simplifying large sets of information.

Fortunately the game itself already parses these states down to a series of decisions made by players. This means that by following how the elements of the game are stacked one atop the other, we can chart a game tree through those decisions.

In a word, we form information sets from the value of relations in the game.

The decision for Movement for any unit is [direction, distance, points of coherency]. The direction is its address, which can be defined in relation to another resources (units are resources, so are terrain, objectives, and the board edges), the distance is the value in relation to the address, and points of coherency is the value in relation to being addressed by enemy fire while in that formation).

Direction and speed will affect the Shooting phase by
limiting what weapons they can fire, and what targets they can address if they do fire. It will also affect the Assault phase, whether and where the unit will charge opponents. Both the value in shooting and assault is value expressed as the set of worst, average, and best values expressed as casualties inflicted. So this is where traditional mathhammer as statistics goes (as well as all the other instances where dice are used to determine the next step or value).

I hope you'll agree then that the game tree that players will need to be aware of should match exactly with the game tree described by the game rules. The values will range from game to game, given terrain, size of army, etc, but the mechanics are the same (until we plug in Special Rules). The difference being that for the model we tag out the values of player decisions algebraically in order to discuss it with mathematical rigour, and therefore arrive at certifiably valid conclusions about the strategies and tactics available to players.

Here's an example of these concepts applied to Hawk-Dove:

Game Turn 1 Player Turn 1 & Game Turn 1 Player Turn 2
Player 1 & Player 2
DD[2,2]
DH[0,3]
HD[3,0]
HH[1,1]

Player 1 & Player 2 both know the calculation for domination:

If XX[bb] + XY[ba] > YY[aa] + YX[ab] then Domination.

Similarly the decision to shoot at unit a rather than unit b in Warhammer 40,000 may have a dominant strategy to it that we can single out some property or set of properties and set them to one side as 'no-brainers'. This should also winnow the number of conditional decisions and therefore live options facing any player in any game.

I just want to come up with a point which may make the prisoners' dilemma (or Hawk-Dove as you call it) seem not suited: In a PD both players don't want to get better pay off than the other player but only the best possible pay off for themselves. (which still allows for the PD as a model in principle anyways, so i guess I'm just a smartass )
If this has come up on the former pages I beg your pardon.
Otherwise I find this a great go at out of game theory for ingame decissionmaking! Desirable work

I think I established that the blunt application of Hawk-Dove to Warhammer 40,000 wasn't going to work on page 1, and that I was using it to illustrate game theoretic concepts. I have since moved on.

It's probably worth noting why I prefer the Hawk-Dove to the Prisoner's Dilemma, for rhetorical reasons. In the Prisoner's Dilemma you have the option to co-operate with your opponent (Dove) or defect from cooperation with your opponent (Hawk). The problem is that sounds a lot like the goodwill and retribution of reciprocity, which happens over a sequence of nodes, not simultaneously within them.

That's why earlier I pointed out that phases can't be nodes; no opportunity for reciprocity despite the opportunity for defection and cooperation, which can lead to people over-generalizing conclusions about single iteration games with multiple iteration games.

In one sense then, tactics in Warhammer 40,000 are a list sequencing the actions of units in the phase that intersects another list sequencing the actions of the same units in the turn. Strategies would be the index of action between an iteration/node and its following iterations/nodes. This sequencing also lets us pair down all the permutations to combinations.

To hazard a conjecture which I'd be very happy to hear some input on, I'd suggest that to some degree that target selection will involve something like the reciprocity mechanism we first noticed in the Indefinitely Iterated Hawk-Dove. I think this is because some moves are trade-offs between exposing oneself to enemy retribution, and gaining the payoff of killing them first.

Nah, I don't think it's a reciprocity mechanism. You're not going to garner goodwill by refraining from killing a guy's Rhino. The fact that you'll expose a unit to enemy fire will just affect the expected value of the move: [value of damage]*[chance of damage] - [value of unit/of part of unit]*[chance of damage to unit].

I think it's moreso the other kind of reciprocity, retaliation, since you're trying to kill the other guy, he's also risking himself to kill you. There's value to shooting first if you get lucky. Also, whether you can lucky or whether you get unlucky, there may be a cost.

I'm not sure why they were deleted, but my last post referenced game theory links to incorporating uncertainty into game theory.

I think instead of deleting or censoring posters, you should respond to your criticism. THis is how how models become better.

Considering that other theorists took nash's equilibrium and added to it the concept of uncertainty...

I think there is no reason why your model shouldn't incorporate such elements.

Also, if I disprove a bunch of your basic premises, it is on you as a model maker to explain why your model is still useful despite its shortcomings, and to acknowledge its shortcomings. No model is perfect. I don't expect it to be...but when I say your model isn't robust enough...and it isn't robust enough to be useful..it's on YOU to fix it. Shoving the criticism under the carpet doesn't make it less true.

? I've never heard of posts being deleted on dakka, it's usually giant red text...

scuddman:

If you have an objections to the premises of this thread, please start your own thread on that subject.

Back on topic: The model does incorporate an account of uncertainty. Three of them, actually. See my post on p.2 that starts with a discussion of Ken Binmore's handy little book.

In terms of uncertainty, the three accounts deal with the (1) random element of dice, (2) the lack of complete information due to the random end-game, and the (3) finitude of resources. Each game node accounts for thus uncertainty by valuating actions by both potential and expected value.

It's probably important to distinguish uncertainty from risk here. Risk here is what you risk, so that being less willing to accept additional risk makes one risk-adverse.

EvilEggCracker wrote:So... Essentially... we should try not to lose?

Withering hail of lasguns > Game Theory.

rofl

Sorry I couldn't help it - it's pretty funny, if you don't take it seriously.

Good Thread Nurgs.

Now that the game nodes are up, I thought I might work backwards a bit and talk about deployment, since deployment affects the game in several important ways.

I'd imagine a similar structure for deployment as the game turn, with normal deployment taking the place of movement, then infiltration deployment, and finally scout moves. The interesting difference being that dice are involved in determining who deploys first, and who has the first turn.

I think we've already seen people subconsciously crunching the numbers for this as we've seen certain strategic equilibria in action: Enemy is entirely contained in Drop Pods? Reserve all your forces to prevent a first strike.

The dice involved in determining who deploys first are complicated because it isn't an automatic: You win, you go first situation. The player who wins the toss gets to decide whether they go first or second. Likewise the player going second can decide to try and seize the initiative. Which means you can have:

(A) Player 1 Deploys 1st, 1st Turn, Player 2 Deploys 2nd, 2nd Turn (5/6)
(B) Player 1 Deploys 1st, 2nd Turn, Player 2 Deploys 2nd, 1st Turn (1/6)

There's something similar going one with Turns 5, 6, and 7 though, as they end on 3-, 2-, and 1+, respectively.

OK,

There's a lot to go through here, so I may have missed something obvious, but I have a bit of a problem with the argument as it's laid out in the first post.

The outcome of 40k is binary; a win or loss. You can't grade it, unless you're playing a campaign or going for the biggest win.

So, taking a hypothetical example:
Dove-Dove = $10 each.
Hawk-Dove = 7$ to hawk, $4 to dove.

Dove-dove is optimal if value is what matters. But, in 40k, value is irrelevant. The hawk strategy wins because 7>4.

To translate to 40k, both players having 2 objectives is fine. But one player having 1 objective, whilst their opponent has none is better for player holding 1.

This is, of course, why 40k is unrealistic. In reality, preserving your own force would obviously be important.


And, if I've missed something really basic, I apologise.

Yes, you're missing the fact that we're not trying to interpret Warhammer 40,000 purely in the context of the Hawk-Dove game, or whatever version you're talking about. The Hawk-Dove game is not the be all and end all of Game Theory. In other words all the posts after the first one.

In fact the Hawk-Dove game is a really bad model for Warhammer 40,000, despite being a nice introduction to game theory. That's why I introduced all the other variants of the Hawk-Dove game, to show how the same concepts applied, but that the results changed, much like arithmetic works the same with different numbers, but the results change.

Also "realism" is irrelevant in this thread since it's about applying one model to another, which is good because it means that, unlike empirical science for example, we can have a complete model of Warhammer 40,000.

At this point I'm busy labeling parts of the 40k game structure with their game theoretic names (game turn = node, for example) so we can have a game tree for Warhammer 40,000 and start discussing particular applications or tactics and strategies.

So, for example, you want to know how any single decision in a game of 40k could be modelled as a node in a decision tree?

doctorludo:

No, not quite. As you may have noticed from reading the thread a node is equal to a single game turn in Warhammer 40,000.

Quite the opposite really, if we can consider game theory has being a top-down perspective on decisions, since I want to model the set of decisions constituting a game of Warhammer 40,000 as a game tree.

I'm a little confused. Are you modeling each player turn as a node, or each opposing player's turn as a node, or what? I don't understand why a player would treat his own turn as a single node, since he makes a sequence of separate decisions during that turn. But maybe I missed something: is it a way to simplify the decisions, so we don't have an inconceivable number of possible outcomes?

Hesperus:

Yes, player turns are interpreted as nodes. The player treats his own turn as a single node because each player turn is made in response to the following player turn.

Remember also that the player turn decisions depend upon each other: you can only assault the unit that you shot at in that Shooting phase, for example. The node is thus broken up by the sequence of the decision, as well as by the units whose actions need deciding.

Nodes are connected by actions, in this case the sets of actions that are decided on during the turn sequence. Since the actions are relational rather than absolute, there's a lot less of them.

But there's a lot of decisions to be made even if decisions are made relationally. So we can construct the following parameters to have the players understand the potential reciprocity their action can prompt in the other player: the upper limit, the lower limit, and the average utility of any action. With these three parameters we can make reasonable inferences about the upper, lower, and average utility parameters of our opponent in the following turn.

Basically the game node considers both player turns,the one in play and the hypothetical one next turn. Because you're indexing potential states of your own choices against the potential states of your opponent's choices in the following turn, you get a much more limited game tree.

In fact, I think it's limited enough to treat the game as a 7x7 payoff grid, corresponding to its maximum 7 game turns.

Edited: Corrected "average utility" for 'expected value'.

Okay, I'm still not sure how you're going to do the estimating, but 7x7 isn't going to work. The turns are sequential, not simultaneous, so to depict the game in normal form you have to have a cell for each combination of choices, right? So if, for example, a player could pick option 1 or option 2 in each turn, you'd need a cell for [1,1,1,1,1,1,1,], [1,1,1,1,1,1,2], 1,1,1,1,1,2,1], and so on. I assume you'll provide more than two options for each player each turn, but even if you don't, you'll need a 49x49 table.

I find extensive form more intuitive for sequential games, but I guess that's just preference.

I agree that the payoff grid is moreso suited for simultaneous games and the game tree for sequential games, but if we think of each actual player turn as a cell, indexing the player's choices against her opponent's potential retaliation, with the game ordered from left to right and up to down so that movement right across the cells towards the last cells of the game favours the player on the x axis (call him player 1), and movement down across the cells towards the last calls of the game favours the player on the y axis (call him player 2).

Think of it like a hybrid of the two, with cell (1, 6) and (6, 1) being something like tabling one's opponent,and cell (6, 6) being a tie. The movement between the cells on the x,y plane is like that of a game-tree, while within the cells, within the nodes, we have something more like a traditional payoff table where a player's potential actions are compared to the other player's potential retaliation.

OK, I'm going to stick my neck out here and say that I think, from one approach, that this is impossible, unless the nodes are simplified into abstraction (e.g. play aggressively, play defensively etc).

But, before you shoot me down, the principles of decision theory have a lot to add to wargaming. I am aware that game theory and decision theory are not one and the same thing, but they share concepts such as a measure of utility, and the use of statistics and probability to model uncertainty.

My problem is this: At the most detailed level, each node would have to take into account what the player does with each model, in terms of movement, shooting, assault positioning etc. Furthermore, it must take into account wound allocation and enemy equipment in order to make sense of this. So, a squad of 5 orks fighting a space marine devastator squad would have to decide whether to get into charge range, whether to shoot, whether to Waaaagh, and the space marine would decide which model to remove. I suspect that even a fairly simple game of 40k would be beyond the processing power of a home computer to model all iterations.

BUT, that's probably not what you're proposing. We could simplify the grid by giving a certain number of actions: "Close with nearest enemy unit", "move towards nearest cover", "shoot nearest enemy unit" etc. Such simplifications could produce an estimate of optimal decision making in a given situation, sacrificing accuracy for feasibility. There will still be an awful lot of branches in each node, but it would be possible. This is akin to heuristic reasoning in humans.

So, do we need to consider the level of simplification which is necessary? What are the decisions for each node? Can we summarise the table at the end of the preceding turn to influence optimal decisions?

Is this more akin to what you are proposing?

doctorludo:

I became aware of game theory through decision theory (and mainly through the horde of fallacies my Decision Theory prof was making in regard to game theory), so I grok where you're coming from.

I discussed this in private messages with another poster and figure I'll answer by quoting some stuff I wrote in those messages (slightly edited):

Nurglitch wrote:Basically the move is from all possible game states to all possible decision states, parsing by relevance, and from all possible decision states to the most likely, parsing by reliability, and adding the uppermost and lowermost boundaries so players can understand where their decision can be expected to land on the bell curve. A lower bound of 0, and upper bound of 20, and an average utility of 2.33 means that anything above 2.33 is gravy.

Given 2.33 as the average, you can then compute the value of retaliation with 0.66 likelihood of two casualties, and 0.33 likelihood of three casualties.

So basically instead of all possible states of the game, we're only considering the parts that we can reasonably expect while retaining our capacity to resolve further detail.

Take movement, for example. While the number of outcome-states for a moving infantry unit is very large, it can be crunched down into three things: Its relation to other units, its relation to terrain, and its relation to itself.

Fair enough...

My decision theory prof was clear enough, but my experience is with descriptive theories, and a basic understanding of the normative and prescriptive models.

I'm working in healthcare, where the limits of normative/prescriptive approaches are an important part of application.

But we seem to be discussing different subjects; I'll read with interest.

doctorludo:

Let me put it this way, a game tree of the player decisions in the game is going to be much more user-friendly than a game tree of all possible game states. Similarly the game tree is going to be user-friendlier if it accounts for these decisions relationally rather than absolutely. It'll also describe the game more accurately by sorting features by relevance.