Jump to content



Photo

Help with mathswing project


  • Please log in to reply
26 replies to this topic

#1 malladin.ben

malladin.ben

    Member

  • Members
  • 156 posts

Posted 05 August 2014 - 03:06 AM

Hello all,

 

Since starting X-Wing last January I have been fascinated with the maths at the core of the game. As a game designer myself, it I appreciate the elegance with which the system works. WIth a basic level of maths you can work out the average dice rolls and compare the effects of target lock, focus, and a variety of upgrade cards on the attack or defence dice.

 

At times I have found my fascination with the mathematics of the game draw me into the debate over various issues to highlight mathematical issues, such as the problem with expose, and whether opportunist is better than PtL.

 

During one such discussion I was arguing that TL or Focus is better than adding attack dice, but it was suggested that there may be additional benefits of the extra dice when you compare it vs defence dice modified by focus and/or evade tokens.

 

This concept had me intrigued. I had no easy way of proving or disproving whether this was true, or at what point it became true. I realised that to fully calculate the probabilities I would need to work out the probabilities of damage scored after both sets of dice had been rolled and tokens used.

 

So I set out trying to work this out. There may be a proper way of working this out mathematically, but my maths training ended with A Levels at 18. However, what I can do is write a program that will iterate through all the possible combinations and average them out, and that is indeed what I have done. However, the program is taking a while to run. When I try to run it for 5 dice it takes over 24 hours, if I add in a target lock it's probably going to take nearly a fortnight. And I need to run it separately for each different token combination. Some of the problem might be my crappy old laptop, but if I'm going to complete the project before christmas I'll need some help.

 

tl:dr - I've got a program to calculate damage probabilities for attack vs defence dice combinations, but it takes so long to run I'll need help to run it through enough times to calculate all the results.

 

So, if you are willing to help me out, what can you do?

1. If you don't have it already, download Python: https://www.python.org/downloads/

2. Download my python script: https://www.dropbox....nbm30/SWDice.py

3. Choose a combination of tokens you want to try out and post here so that others don't run the same combination.

4. Run the program (set the number of dice to 5, the tokens that you want to include to 1 and those that you don't to 0).

5. copy and paste the results table produced at the end of the program in a reply to this thread.

 

Thanks for your help,

 

Ben



#2 malladin.ben

malladin.ben

    Member

  • Members
  • 156 posts

Posted 05 August 2014 - 03:08 AM

Dice Combinations run:

 

Unmodified Defence Dice vs Unmodified Attack Dice (malladin.ben)

Unmodified Defence Dice vs Target Lock Attack Dice (malladin.ben)

Unmodified Defence Dice vs Focus Attack Dice (malladin.ben)

Unmodified Defence Dice vs Target Lock & Focus Attack Dice (malladin.ben)

 
 

 



#3 Bilisknir

Bilisknir

    Member

  • Members
  • 640 posts

Posted 05 August 2014 - 05:11 AM

Shouldn't take that long to do this sort of analysis. Probably horrendously inefficient code. I have Monte Carlo sims for work in Python doing tens of millions of simulations in 20 minutes, including complex option revaluation.


Bilisknir corrupt ver of Bilskirnir (Old Norse "lightning-crack"). The hall of the god Thor in Norse mythology.

Rebel: 8 X-Wing, 9 A-Wing, 4 Y-Wing, 8 B-Wing, 2 YT-1300, 2 HWK-290, 2 GR-75 Transport, 1 Corellian Corvette, 8 Z-95, 4 E-Wing, 2 YT-2400

Imperials: 9 Tie/ln, 10 Tie Int, 5 Tie Bomber, 3 Tie Adv, 2 Firespray-31, 3 Lambda-Class Shuttle, 4 Tie Defender, 4 Tie Phantom, 2 VT-49 Decimator

Scum & Villany: 4 Most Wanted, 4 StarViper, 6 M3-A Interceptor, 2 IG-2000 (Pre-order)


#4 Vorpal Sword

Vorpal Sword

    O frabjous day!

  • Members
  • 2,904 posts

Posted 05 August 2014 - 06:04 AM

Shouldn't take that long to do this sort of analysis. Probably horrendously inefficient code. I have Monte Carlo sims for work in Python doing tens of millions of simulations in 20 minutes, including complex option revaluation.


Ditto; I've simulated attack and defense rolls for X-wing in SAS (should probably be using Python, and it's on my to-do list after my dissertation is finished), and I can do a few hundred thousand rolls in seconds. There's definitely a problem with your code.

Edited by Vorpal Sword, 05 August 2014 - 06:05 AM.


#5 malladin.ben

malladin.ben

    Member

  • Members
  • 156 posts

Posted 05 August 2014 - 06:41 AM

feel free to take a look at the code. But by the time you're factoring in 6 attack dice with rerolls for target lock vs 5 defence dice it's 167 trillion iterations to get complete results.

#6 Bilisknir

Bilisknir

    Member

  • Members
  • 640 posts

Posted 05 August 2014 - 07:32 AM

Your calculation is O(8^(Ad+Dd)) it should be no worse than O(8^MAX(Ad,Dd))

In other words you seem to be generating the defence rolls for each and every attack roll. Split the generation of attack and def rolls apart and it should complete a number of orders of magnitude faster.


  • Vorpal Sword likes this

Bilisknir corrupt ver of Bilskirnir (Old Norse "lightning-crack"). The hall of the god Thor in Norse mythology.

Rebel: 8 X-Wing, 9 A-Wing, 4 Y-Wing, 8 B-Wing, 2 YT-1300, 2 HWK-290, 2 GR-75 Transport, 1 Corellian Corvette, 8 Z-95, 4 E-Wing, 2 YT-2400

Imperials: 9 Tie/ln, 10 Tie Int, 5 Tie Bomber, 3 Tie Adv, 2 Firespray-31, 3 Lambda-Class Shuttle, 4 Tie Defender, 4 Tie Phantom, 2 VT-49 Decimator

Scum & Villany: 4 Most Wanted, 4 StarViper, 6 M3-A Interceptor, 2 IG-2000 (Pre-order)


#7 Vorpal Sword

Vorpal Sword

    O frabjous day!

  • Members
  • 2,904 posts

Posted 05 August 2014 - 07:41 AM

feel free to take a look at the code. But by the time you're factoring in 6 attack dice with rerolls for target lock vs 5 defence dice it's 167 trillion iterations to get complete results.


I did it the short way, using convolution sums. This is the total damage for 6 attack dice with target lock versus 5 defense dice, both with and without focus:

6%20Atk%20%2B%20TL%20vs%205%20Agi.jpg

#8 malladin.ben

malladin.ben

    Member

  • Members
  • 156 posts

Posted 05 August 2014 - 08:18 AM

Your calculation is O(8^(Ad+Dd)) it should be no worse than O(8^MAX(Ad,Dd))
In other words you seem to be generating the defence rolls for each and every attack roll. Split the generation of attack and def rolls apart and it should complete a number of orders of magnitude faster.


I think it needs to look at every possible outcome to work out the average accurately, so it does need to calculate every defence dice outcome for every attack dice combo. But people with superior maths skills may know better.

#9 malladin.ben

malladin.ben

    Member

  • Members
  • 156 posts

Posted 05 August 2014 - 08:21 AM

feel free to take a look at the code. But by the time you're factoring in 6 attack dice with rerolls for target lock vs 5 defence dice it's 167 trillion iterations to get complete results.

I did it the short way, using convolution sums. This is the total damage for 6 attack dice with target lock versus 5 defense dice, both with and without focus:6%20Atk%20%2B%20TL%20vs%205%20Agi.jpg

convolution is something I didn't cover on my maths a level. Thanks, I'll look into it.

Ben

#10 Bilisknir

Bilisknir

    Member

  • Members
  • 640 posts

Posted 05 August 2014 - 08:35 AM

 

Your calculation is O(8^(Ad+Dd)) it should be no worse than O(8^MAX(Ad,Dd))
In other words you seem to be generating the defence rolls for each and every attack roll. Split the generation of attack and def rolls apart and it should complete a number of orders of magnitude faster.


I think it needs to look at every possible outcome to work out the average accurately, so it does need to calculate every defence dice outcome for every attack dice combo. But people with superior maths skills may know better.

 

True, but you don't need to recalculate the rolls each time. Calculate once and then compare multiple times.

Also convolution. No need to compare [hit],[miss] and [miss],[hit] to def rolls.


Bilisknir corrupt ver of Bilskirnir (Old Norse "lightning-crack"). The hall of the god Thor in Norse mythology.

Rebel: 8 X-Wing, 9 A-Wing, 4 Y-Wing, 8 B-Wing, 2 YT-1300, 2 HWK-290, 2 GR-75 Transport, 1 Corellian Corvette, 8 Z-95, 4 E-Wing, 2 YT-2400

Imperials: 9 Tie/ln, 10 Tie Int, 5 Tie Bomber, 3 Tie Adv, 2 Firespray-31, 3 Lambda-Class Shuttle, 4 Tie Defender, 4 Tie Phantom, 2 VT-49 Decimator

Scum & Villany: 4 Most Wanted, 4 StarViper, 6 M3-A Interceptor, 2 IG-2000 (Pre-order)


#11 Vorpal Sword

Vorpal Sword

    O frabjous day!

  • Members
  • 2,904 posts

Posted 05 August 2014 - 09:07 AM

convolution is something I didn't cover on my maths a level. Thanks, I'll look into it.

Ben


Sorry--I'm not familiar enough with the UK education system to know what A-level means. (It might help if you could explain by analogy to the O.W.L. and N.E.W.T. tests in Harry Potter.)

Basically, a convolution sum is how you add two distributions together. Technically it's a double integral, but it's relatively easy to compute for a discrete distribution: if you want to know the result of adding two six-sided dice together, for instance, you can look at it like this.

So the First Die has a 1/6 likelihood of coming up with a 1, and the Second Die can be a 1, 2, 3, 4, 5, or 6, each with a likelihood of 1/6. So in the final distribution (which starts off empty), we add a 1/6 * 1/6 = 1/36 chance each of a result of 2, 3, 4, 5, 6, or 7.

Again, the First Die has a 1/6 likelihood of coming up with a 2, so you add to the final distribution a 1/36 chance each of resulting in a 3, 4, 5, 6, 7, or 8. You repeat for the First Die's chance to come up with results of 3, 4, 5, or 6, and you end up with this:

Result | p
-----------
2 | 1/36
3 | 2/36
4 | 3/36
5 | 4/36
6 | 5/36
7 | 6/36
8 | 5/36
9 | 4/36
10 | 3/36
11 | 2/36
12 | 1/36

For X-wing, you build up the attack and defense rolls by convolution sum of individual dice of the appropriate type, then you subtract the defense roll from the attack roll (and of course subtraction is just a kind of sum).

I'm sure Wikipedia and Wolfram Mathworld will be more helpful if you want to learn more.

#12 Hobojebus

Hobojebus

    Tie Defender Ace

  • Members
  • 3,413 posts

Posted 05 August 2014 - 09:10 AM

Cant we just roll coloured dice and make swishing noises as we move our ships.



#13 Aminar

Aminar

    Member

  • Members
  • 3,110 posts

Posted 05 August 2014 - 09:12 AM

Your calculation is O(8^(Ad+Dd)) it should be no worse than O(8^MAX(Ad,Dd))
In other words you seem to be generating the defence rolls for each and every attack roll. Split the generation of attack and def rolls apart and it should complete a number of orders of magnitude faster.


I think it needs to look at every possible outcome to work out the average accurately, so it does need to calculate every defence dice outcome for every attack dice combo. But people with superior maths skills may know better.
You don't need to look at every roll. If you have it calculate out the average and watch until it stops changing(or have a counter that watches for it to not change over a few thousand iterations) that does so as well) you'll find out the average damage. There's an android app that does this to two decimal places out, which is more than plenty.

#14 Vorpal Sword

Vorpal Sword

    O frabjous day!

  • Members
  • 2,904 posts

Posted 05 August 2014 - 09:19 AM

Cant we just roll coloured dice and make swishing noises as we move our ships.


Yes, we can, but math is fun. ("Maths", too, if you live in a part of the world that insists on associating prosthetic esses with its math.  :P)



#15 MajorJuggler

MajorJuggler

    MathWinger

  • Members
  • 3,197 posts

Posted 05 August 2014 - 10:02 AM

Hm, first rule of coding: always know what you are coding. You should be able to identify how many loops / iterations your code is running. You did write the code, after all! Understanding the basic probability is also important. You need to be able to do out a couple of examples by hand first before you have any confidence in coding it...

 

For just tracking number of hits for known focus tokens on each side, then as Vorpal said, using convolution is the fastest way to go. Basically:

  1. Build a 1-dimensional array for the probability density function of how many hits you will roll with A attack dice. This obviously changes if you have a focus available to spend. Using convolution and the binomial distribution is the fastest way to do this. You don't need to do 8^A rolls.
  2. Do the same for the D defense dice.
  3. Now you can build your a (A+1) x (D +1) array. The indexes into the array determine the damage done, and the value in each cell represents the probability of it occurring. The sum value of all probabilities must by definition equal 1. For example if you have a 25% chance to roll 2 hits, and you have a 37.5% chance of rolling one evade, then there is a 0.25*0.375 = 9.38% chance of getting 2 hits vs 1 evade = 1 damage.

Edit: You can also get clever as Vorpal pointed out and just use a single 1 dimensional array. Once you are done convolving the attack dice to make the array (probability density function), you can then convolve the defensive dice into the same array. You'll have to keep track of what index into the array equals zero damage. With each defensive dice roll it moves one to the right.

 

Even if you do brute-force calculations comparing every possible scenario, and tracking critical hits, hits, blanks, and the probability of the attacker and defender still having their focus after the attack, it should all be essentially instantaneous if you know how to optimize the problem. I use such a script in MATLAB that calculates damage (with crit tracking) for all possible number of attack and defense dice. It's basically instant.


Edited by MajorJuggler, 05 August 2014 - 10:08 AM.


#16 malladin.ben

malladin.ben

    Member

  • Members
  • 156 posts

Posted 05 August 2014 - 10:26 AM

Surely it's an abbreviation of mathematics, plural, so the abbreviation should be pluralists to :-)

A Levels=NEWTS (taken at 18 as part of a more intensive curriculum between 16 and 18 where you narrow your focus down to 3-4 subjects). That said, that was 20 years ago, so my memory is flakes on the stuff I did cover.

Anyway, the reason why I'm doing it this way is to work out average damage, not just to work out average hits and then subtract average defence.

anyway looks like convolution might help, I just need to get my head around it. Wikipedia is not written for the uninitiated.

Thanks anyway

#17 Hobojebus

Hobojebus

    Tie Defender Ace

  • Members
  • 3,413 posts

Posted 05 August 2014 - 10:31 AM

 

Cant we just roll coloured dice and make swishing noises as we move our ships.


Yes, we can, but math is fun. ("Maths", too, if you live in a part of the world that insists on associating prosthetic esses with its math.  :P)

 

I will have you know sir I do indeed come from that faire isle, great Britain a land that has no equal! *flag unfurls and music starts* 


  • Bilisknir likes this

#18 MajorJuggler

MajorJuggler

    MathWinger

  • Members
  • 3,197 posts

Posted 05 August 2014 - 10:49 AM

anyway looks like convolution might help, I just need to get my head around it. Wikipedia is not written for the uninitiated.

 

Yup and yup.

 

Binomial distribution basically just means that you only have 2 possible outcomes. Hence BI-nomial.

 

Take the example of rolling A attack dice with a focus token. 6 out of the 8 sides have a focus, hit, or a critical hit, and so would be a success. So the binomial distribution of a single attack dice roll is:

 

[ 0.25 0.75 ]

 

Now you just need an array to keep track of the probability of number of hits.

 

The array size is N+1 where N is the number of dice rolled so far. Before you roll anything, you have a 100% chance of rolling zero hits, so the starting array is simply 1.

 

In general, you convolve the Array with [ 0.25 0.75].

 

After the first roll the answer is obviously: [ 0.25 0.75 ].

 

After that, it is:

ARRAY = 0.25*[ ARRAY 0] + 0.75*[0 ARRAY]

 

Just keep repeating that until you have accounted for all of your attack dice. So you only need a single loop with a couple iterations to generate the probability density function for all possible results of the attack dice. Then you can do the same thing with the defense dice, either:

  1. creating an entirely new array for defense dice as above
  2. piggy-back onto the existing array

If you piggy back onto the existing array, then, for example, the binomial distribution for rolling an evade dice without focus would be: [0.375 0.625]. As I said above, the index for zero hits will increase by 1 for each defense dice you roll. So you have a 62.5% chance that each defense dice will not be an evade, and the PDF moves to the right by one, which corresponds to no change since the index for zero damage also moved to the right one. Conversly, there is a 37.5% chance that an evade is rolled and the PDF stays where it is, which corresponds to 1 less damage being done since the index for zero damage moved to the right. Once you account for all the defense dice, you can't have negative damage, so starting at the zero damage index sum from there going left and consolidate that into a single value. Voila, there's your net damage probability density function. It's just trivial multiplication and adds to get the average damage now.


Edited by MajorJuggler, 05 August 2014 - 10:50 AM.

  • Vorpal Sword likes this

#19 Bilisknir

Bilisknir

    Member

  • Members
  • 640 posts

Posted 05 August 2014 - 10:51 AM

 

 

Your calculation is O(8^(Ad+Dd)) it should be no worse than O(8^MAX(Ad,Dd))
In other words you seem to be generating the defence rolls for each and every attack roll. Split the generation of attack and def rolls apart and it should complete a number of orders of magnitude faster.


I think it needs to look at every possible outcome to work out the average accurately, so it does need to calculate every defence dice outcome for every attack dice combo. But people with superior maths skills may know better.
You don't need to look at every roll. If you have it calculate out the average and watch until it stops changing(or have a counter that watches for it to not change over a few thousand iterations) that does so as well) you'll find out the average damage. There's an android app that does this to two decimal places out, which is more than plenty.

 

He isn't doing random rolls, but calculating every possible roll and every possible def roll against it. Highly inefficient but hey. To each their own :)


Bilisknir corrupt ver of Bilskirnir (Old Norse "lightning-crack"). The hall of the god Thor in Norse mythology.

Rebel: 8 X-Wing, 9 A-Wing, 4 Y-Wing, 8 B-Wing, 2 YT-1300, 2 HWK-290, 2 GR-75 Transport, 1 Corellian Corvette, 8 Z-95, 4 E-Wing, 2 YT-2400

Imperials: 9 Tie/ln, 10 Tie Int, 5 Tie Bomber, 3 Tie Adv, 2 Firespray-31, 3 Lambda-Class Shuttle, 4 Tie Defender, 4 Tie Phantom, 2 VT-49 Decimator

Scum & Villany: 4 Most Wanted, 4 StarViper, 6 M3-A Interceptor, 2 IG-2000 (Pre-order)


#20 InvestFDC

InvestFDC

    Member

  • Members
  • 234 posts

Posted 05 August 2014 - 12:36 PM

 

 

 

Your calculation is O(8^(Ad+Dd)) it should be no worse than O(8^MAX(Ad,Dd))
In other words you seem to be generating the defence rolls for each and every attack roll. Split the generation of attack and def rolls apart and it should complete a number of orders of magnitude faster.


I think it needs to look at every possible outcome to work out the average accurately, so it does need to calculate every defence dice outcome for every attack dice combo. But people with superior maths skills may know better.
You don't need to look at every roll. If you have it calculate out the average and watch until it stops changing(or have a counter that watches for it to not change over a few thousand iterations) that does so as well) you'll find out the average damage. There's an android app that does this to two decimal places out, which is more than plenty.

 

He isn't doing random rolls, but calculating every possible roll and every possible def roll against it. Highly inefficient but hey. To each their own :)

 

 

But it gives a higher degree of accuracy, like the factorials used in statistics. If you have access to Mini-Tab or SPSS then you could get a test model to narrow down the counfounding and increase the resolution.






© 2013 Fantasy Flight Publishing, Inc. Fantasy Flight Games and the FFG logo are ® of Fantasy Flight Publishing, Inc.  All rights reserved.
Privacy Policy | Terms of Use | Contact | User Support | Rules Questions | Help | RSS