True Attacking Odds.

AI discussion, ideas, and SDK help.
Post Reply
Houndy
Lux Newbie
Posts: 5
Joined: Thu Oct 27, 2011 1:26 pm

True Attacking Odds.

Post by Houndy » Wed Feb 29, 2012 8:30 am

As part of my bot I am trying to calculate the true attacking odds, but am slightly confused as to how Lux deals with attacking. I've searched aroudn the forums quite abit but still dont quite understand:

I know that it rolls 3 dice for each army for an attacker and 2 dice for each army for a defender.

However, when you click attack in the game how many armies attack at once?

for example if you had 50 defenders and 50 attackers it couldn't be 150 dice vs 100 dice cause chacnes are there will always be a 6 rolled and they
would draw and the defender would win.

So does it take a maximum of 4 armies at once for example?

Also does it take the top two or three dice and compare them?

Furthermore is it based on a dice so 1/6 chance per value or is it slightly different?

I would be very grateful for an answer

Houndy
Lux Newbie
Posts: 5
Joined: Thu Oct 27, 2011 1:26 pm

Post by Houndy » Wed Feb 29, 2012 9:08 pm

Ok. So Ive created a program to calculate the odds of battle.

It uses the following odds from http://www.plainsboro.com/~lemke/risk/:

Attacker: one die; Defender: one die:

Attacker wins 15 out of 36 (41.67 %)
Defender wins 21 out of 36 (58.33 %)


Attacker: two dice; Defender: one die:

Attacker wins 125 out of 216 (57.87 %)
Defender wins 91 out of 216 (42.13 %)


Attacker: three dice; Defender: one die:

Attacker wins 855 out of 1296 (65.97 %)
Defender wins 441 out of 1296 (34.03 %)


Attacker: one die; Defender: two dice:

Attacker wins 55 out of 216 (25.46 %)
Defender wins 161 out of 216 (74.54 %)


Attacker: two dice; Defender: two dice:

Attacker wins both: 295 out of 1296 (22.76 %)
Defender wins both: 581 out of 1296 (44.83 %)
Both win one: 420 out of 1296 (32.41 %)


Attacker: three dice; Defender: two dice:

Attacker wins both: 2890 out of 7776 (37.17 %)
Defender wins both: 2275 out of 7776 (29.26 %)
Both win one: 2611 out of 7776 (33.58 %)

(I changed 33.58 to 33.57 as atm its greater than 100% )

*taken code out for now, so many things I need to change will upload tomorrow.


Now theres a few things to note. Firstly I created this relatively quickly and therefore it doesnt make best use of some structures.


ATM the code has a limit of 999 v 999 (Code includes 0 v 0 etc but doesnt use it but just makes it easier to read as code (poor practice I know, you can change this). Can easily be changed in the oddsLUT file by changing the array size. (e.g. [2000][2000] gives limit of 1999 vs 1999 armies).

Its written to work stand alone atm. I have not integrated it into Lux SDK. This is fairly easy to adapt (note that you wont need to pass the LUT table around in the methods). I will be implementing it into Lux but im not gonna post that.

Hope this helps some people. Please warn me if I have got the odds wrong.

Just to clarify this is the odds that you win the battle (it doesnt take into account how many you have left just that you have at least 2 left.). It also assumes you cant attack with just 1 army (as in the one you are using to occupy the country, which I think ties in with the Lux rules).

Next i'm gonna create something which will let you take into account how many armies you want left. Or how many armies you want the enemy to have left.

User avatar
Lantern
Lux Superhero
Posts: 4072
Joined: Sat Jul 07, 2007 12:18 am
Location: Floating down the river
Contact:

Post by Lantern » Wed Feb 29, 2012 10:56 pm

Lantern wants to know where you took para and what you have done to him!

J/k

Houndy I am impressed with your digging into maps and bot making. Keep it up! Alas I am no help with these things but I am sure para can give you a hand.

User avatar
Drifter
Semiholy Rambler
Posts: 6770
Joined: Sun Nov 20, 2005 5:06 pm
Location: An undisclosed location... for reasons of security, and therefore... insecurity...
Contact:

Post by Drifter » Wed Feb 29, 2012 11:27 pm

I'm impressed as well Lantern... but you and I are old farts who still speak analog.

User avatar
paranoiarodeo
Semiholy Tyrant
Posts: 10421
Joined: Sun Jul 17, 2005 5:30 pm

Post by paranoiarodeo » Wed Feb 29, 2012 11:38 pm

Houndy wrote:Please warn me if I have got the odds wrong.
Your odds are fine. It's basic math, after all. The bigger challenge here are your confidence intervals. Obviously, if you attack 20 versus 20, one thousand times, you'll see a range of results, some successful and some not. It's not just a matter of how many armies you want left over, but rather how often you wanna win. 50%? 67%? 75%? 90%? 95%? 99%? And that's just for single country battles. The probability chain gets much more complicated when you start considering multiple country attacks, and those requiring you to split your armies along separate paths.

(Bloody good fun though, if you're into this sorta thing.)

Houndy
Lux Newbie
Posts: 5
Joined: Thu Oct 27, 2011 1:26 pm

Post by Houndy » Thu Mar 01, 2012 7:28 am

paranoiarodeo wrote:
Houndy wrote:Please warn me if I have got the odds wrong.
Your odds are fine. It's basic math, after all. The bigger challenge here are your confidence intervals. Obviously, if you attack 20 versus 20, one thousand times, you'll see a range of results, some successful and some not. It's not just a matter of how many armies you want left over, but rather how often you wanna win. 50%? 67%? 75%? 90%? 95%? 99%? And that's just for single country battles. The probability chain gets much more complicated when you start considering multiple country attacks, and those requiring you to split your armies along separate paths.

(Bloody good fun though, if you're into this sorta thing.)
I see what you mean for the branching factor but for single battles its quite simple is it not? If you attack 20 vs 20 there is a 59.239544 .... % chance of winning according to my program. so if you did 1000 games you would expect to win about 592 times.

RE the branching, I'm hoping that my neural network will sort that out for me. Ill provide it with state of the board and when attacking let it know the percentage of winning particular battles and hopefully after a lot of training it will choose the right decisions for me.

Aleph
Lux Newbie
Posts: 1
Joined: Sat Jul 07, 2012 3:42 pm
Location: United Kingdom

Post by Aleph » Sat Jul 07, 2012 4:16 pm

I'd love to know the outcome of the neural network you designed. In my opinion, I thought the choice of variables and formulae for back propagation would require me to spend too much time thinking about the game so I ended up going for a route planning algorithm.

In retrospect, calculating statistics for winning a series of games was far too complex in terms of the time it took to calculate the odds. (complexity-wise it is infeasible). But for 3 or 4 countries it seemed to do the trick.

By the sounds of your restrictions you're trying to store all the odds in a table to look up at a later date. Have you thought about calculating the odds at runtime? I'd recommend researching markov decision processes. There are some interesting proofs concerning whether markov decision games have optimal solutions as well as calculations for expected outcomes without having to store them in tables.

Post Reply