TripleA Logo TripleA Forum
    • TripleA Website
    • Categories
    • Recent
    • Popular
    • Users
    • Groups
    • Tags
    • Register
    • Login

    Development Discussion: Speeding up battle calculator (and thus Hard AI)

    Scheduled Pinned Locked Moved Feature Requests & Ideas
    44 Posts 10 Posters 11.7k Views 10 Watching
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • RoiEXR Offline
      RoiEX Admin @LaFayette
      last edited by

      @LaFayette One addition to your statements regarding game data cloning times:

      IIRC (I believe this was the case the last time I checked but wouldn't bet on it) a "design problem" the current battle calc brings with it is that any simulated battles are not done in batches, so when fighting, each battle round the code removes the battles casualties from the underlying GameData so the next round of battle can re-use hat GameData to run a "new" battle as if nothing had happened.

      This is nice for multiplayer because it updates "real-time" battles on the map by removing casualties, but is really bad for battle simulations because it would require us to have some sort of write-protection-layer on top of a GameData that pretends to pass any changes to the underlying game-data, but actually doesn't. As long as the battles work like this at least partial but still expensive cloning will be mandatory IMO.

      1 Reply Last reply Reply Quote 0
      • T Offline
        Trevan @RoiEX
        last edited by

        I'll take a stab at the ExpectiMiniMax tree. I don't know the code very well so this will be more of a proof of concept. I'll probably miss a lot of the complex parts of the battles.

        Once I get something working, I'll push it on Github.

        1 Reply Last reply Reply Quote 1
        • L Offline
          Lord Bevan
          last edited by

          I will read through the posts above when i have time.

          right now, i just want to point out, for fastest AI, the order should be combat move, combat, then non-combat and finally purchase. this actually reduces the amount of 'thinking' that both humans and AI have to do.

          1 Reply Last reply Reply Quote 0
          • T Offline
            Trevan
            last edited by

            @RoiEX , @LaFayette , I've written up a proof of concept for the tree. It isn't really expectiminimax since it isn't trying to find the best path. It is just calculating the win/lose/tie probabilities but it follows the same general idea.

            I've tested it with some 1940 Global units (that don't give any support) and the probabilities are inline with the battle calculator. I've also done a few small trees by hand to verify the calculations are working.

            You can see the code at https://github.com/trevan/triplea/commit/1658df71e12e8fb13ee09d5e2f6a33d1dc91f6ea. It doesn't do every battle situation (such as AA, supports, two hits, etc). I wrote a test file that mocks out ProData so I can test out the implementation.

            What do you think? Should I create a WIP PR so discussion can happen in github?

            1 Reply Last reply Reply Quote 0
            • RoiEXR Offline
              RoiEX Admin
              last edited by

              @Trevan I must say I'm impressed, the code definitely looks promising.

              I don't really have any objections to create a PR, but I'd rather have a way to actually make use of this class. If it's just gathering dust in the deoths of the repository it would be an unfortunate waste of time.

              I think it would be a good idea to compare the new "IBattleCalculator" implementation with the 2 (technically 3, but whatever) existing implementations to see how close the estimated results are. Data is key here.

              After that we could consider replacing one of the implementations for the AI, or just add an experimental AI in order for people to test this.

              Ideally we get to a point where the "real" simulation results are super close to the estimated results 99% of the time so we're able to use the lightweight code for the hard ai.
              We could also try to set up some custom maps to let your implementation battle it out in simulated games against the current hard ai using different IBattleCalculator implementations each.

              Not sure what @redrum thinks about this, but I think he'll agree that this definitely looks promising

              redrumR T 2 Replies Last reply Reply Quote 0
              • redrumR Offline
                redrum Admin @RoiEX
                last edited by

                @RoiEX Agree. At a minimum if we got a decent implementation that's very fast then could probably replace Fast AI's calc as it just uses a very simple strength formula (low bar here).

                TripleA Developer with a Passion for AI: https://forums.triplea-game.org/topic/105/ai-development-discussion-and-feedback

                1 Reply Last reply Reply Quote 0
                • T Offline
                  Trevan @RoiEX
                  last edited by

                  @RoiEX, I was thinking the PR would be useful just for a place for discussion. But I'm fine with leaving it as is.

                  I decided to test a battle with 100 infantry attacking 100 infantry and it never finished so I need to look into that.

                  I've compared the estimates to the FastOddsEstimator and to the BattleCalculator in the UI (I think that is ConcurrentBattleCalculator). The results are basically the same as what ConcurrentBattleCalculator returns (if you use units that don't support each other).

                  After I've figured out the performance issue, I'll work on adding handling support units so that I can do better comparisons and then I'll post them here.

                  1 Reply Last reply Reply Quote 1
                  • T Offline
                    Trevan
                    last edited by Trevan

                    I've improved the performance and added support handling.

                    I used TestMapGameData.GLOBAL1940 for the comparisons. I got numbers for ConcurrentBattleCalculator with 200 rounds and 2000 rounds. I also used the PerfTimer to calculate how long it took to run:

                    1 infantry, 1 armour vs 2 infantry
                    Hard AI 200 runs: 1984.9 ms, Win: 0.43, Lose: 0.425
                    Hard AI 2000 runs: 1703.1 ms, Win: 0.4931640625, Lose: 0.388671875
                    MiniMax: 39.8 ms, Win: 0.506233909545216, Lose: 0.38491296598075025

                    1 armour, 1 tactical_bomber vs 2 infantry, 1 fighter
                    Hard AI 200 runs: 2031.1 ms, Win: 0.05, Lose: 0.95
                    Hard AI 2000 runs: 1709.8 ms, Win: 0.072265625, Lose: 0.9228515625
                    MiniMax: 56.0 ms, Win: 0.1150459321571266, Lose: 0.7947330200775955

                    1 infantry, 1 artillery vs 2 infantry
                    Hard AI 200 runs: 2091.1 ms, Win: 0.425, Lose: 0.52
                    Hard AI 2000 runs: 1740.2 ms, Win: 0.4521484375, Lose: 0.4580078125
                    MiniMax: 39.1 ms, Win: 0.4574200859119973, Lose: 0.45742008591199734

                    1 destroyer, 1 cruiser vs 1 destroyer, 1 cruiser
                    Hard AI 200 runs: 1832.9 ms, Win: 0.39, Lose: 0.425
                    Hard AI 2000 runs: 1616.8 ms, Win: 0.4228515625, Lose: 0.427734375
                    MiniMax: 36.1 ms, Win: 0.4250031963247701, Lose: 0.4250031963247701

                    1 destroyer, 1 cruiser, 1 battleship vs 1 destroyer, 2 cruiser
                    Hard AI 200 runs: 2019.2 ms, Win: 0.725, Lose: 0.18
                    Hard AI 2000 runs: 1787.6 ms, Win: 0.7939453125, Lose: 0.14453125
                    MiniMax: 39.0 ms, Win: 0.5358330747385637, Lose: 0.34400771480746317

                    1 infantry, 1 fighter vs 1 infantry, 1 aa gun
                    Hard AI 200 runs: 1844.4 ms, Win: 0.395, Lose: 0.605
                    Hard AI 2000 runs: 1727.8 ms, Win: 0.4306640625, Lose: 0.5625
                    MiniMax: 32.2 ms, Win: 0.6961033280443275, Lose: 0.2000276003717069

                    The numbers look pretty close except when AA guns or two hit battleships are used. I don't handle those.

                    redrumR alkexrA 2 Replies Last reply Reply Quote 0
                    • redrumR Offline
                      redrum Admin @Trevan
                      last edited by

                      @Trevan The speed is quite impressive. Do you think adding in additional unit properties like multi-hit units and AA rolls would be achievable? It might also be interesting to compare it to Fast AI as that uses a very simplistic formula but is very fast.

                      TripleA Developer with a Passion for AI: https://forums.triplea-game.org/topic/105/ai-development-discussion-and-feedback

                      T 1 Reply Last reply Reply Quote 0
                      • T Offline
                        Trevan @redrum
                        last edited by

                        @redrum here's the numbers rerun with FastAi's calculator included.

                        1 infantry, 1 armour vs 2 infantry
                        MiniMax: 93.5 ms, Win: 0.506233909545216, Lose: 0.38491296598075025
                        Hard AI 200 runs: 1787.9 ms, Win: 0.47, Lose: 0.435
                        Hard AI 2000 runs: 1471.6 ms, Win: 0.501953125, Lose: 0.388671875
                        FastOdds: 6.8 ms, Win: 0.5

                        1 armour, 1 tactical_bomber vs 2 infantry, 1 fighter
                        MiniMax: 2.2 ms, Win: 0.1150459321571266, Lose: 0.7947330200775955
                        Hard AI 200 runs: 1025.3 ms, Win: 0.085, Lose: 0.91
                        Hard AI 2000 runs: 1194.6 ms, Win: 0.06640625, Lose: 0.9287109375
                        FastOdds: 0.5 ms, Win: 0.34082222539412593

                        1 infantry, 1 artillery vs 2 infantry
                        MiniMax: 2.9 ms, Win: 0.4574200859119973, Lose: 0.45742008591199734
                        Hard AI 200 runs: 1038.0 ms, Win: 0.465, Lose: 0.405
                        Hard AI 2000 runs: 1385.9 ms, Win: 0.4521484375, Lose: 0.4619140625
                        FastOdds: 0.4 ms, Win: 0.5

                        1 cruiser, 1 destroyer vs 1 cruiser, 1 destroyer
                        MiniMax: 1.6 ms, Win: 0.4250031963247701, Lose: 0.4250031963247701
                        Hard AI 200 runs: 1047.1 ms, Win: 0.405, Lose: 0.46
                        Hard AI 2000 runs: 1140.1 ms, Win: 0.412109375, Lose: 0.4345703125
                        FastOdds: 0.7 ms, Win: 0.5

                        1 cruiser, 1 destroyer, 1 battleship vs 2 cruiser, 1 destroyer
                        MiniMax: 3.1 ms, Win: 0.5358330747385637, Lose: 0.34400771480746317
                        Hard AI 200 runs: 1032.0 ms, Win: 0.775, Lose: 0.165
                        Hard AI 2000 runs: 1141.3 ms, Win: 0.8125, Lose: 0.1328125
                        FastOdds: 1.6 ms, Win: 0.6591777746058741

                        1 infantry, 1 fighter vs 1 infantry, 1 aa gun
                        MiniMax: 1.3 ms, Win: 0.6961033280443275, Lose: 0.2000276003717069
                        Hard AI 200 runs: 1138.5 ms, Win: 0.38, Lose: 0.615
                        Hard AI 2000 runs: 1248.8 ms, Win: 0.4130859375, Lose: 0.583984375
                        FastOdds: 0.2 ms, Win: 0.7180577051181194

                        Fast Ai is really fast. Not sure how to compare the win percentage.

                        I have an idea on how to do multi-hit and AA. I'm going to attempt it. I also need to deal with units with multiple rolls. Is there a map in TestMapGameData that has units like that?

                        C 1 Reply Last reply Reply Quote 0
                        • C Offline
                          Cernel Moderators @Trevan
                          last edited by

                          @Trevan said in Development Discussion: Speeding up battle calculator (and thus Hard AI):

                          MiniMax: 93.5 ms, Win: 0.506233909545216, Lose: 0.38491296598075025
                          Hard AI 200 runs: 1787.9 ms, Win: 0.47, Lose: 0.435
                          Hard AI 2000 runs: 1471.6 ms, Win: 0.501953125, Lose: 0.388671875
                          FastOdds: 6.8 ms, Win: 0.5

                          How is 200 runs slower than 2000 runs?

                          1 Reply Last reply Reply Quote 0
                          • alkexrA Offline
                            alkexr @Trevan
                            last edited by

                            @Trevan Unfortunately this sort of algorithm has to be exponentially slow as the number of units increases, by its nature. I'm saying this without even looking at the code. With some cleverness it might be possible to bring this down to exponential with the number of unit types (not units), but will never be able to handle if, say, a hypothetical map had dozens of unit types, many of them targeting each other unpredictably with all sorts of AA attacks, and battles between stacks of 50 happening regularly. But the speed increase is extremely impressive, and even if the AI only used this to simulate smaller battles while keeping the battle calculator for battles that are too large for this algorithm, that's already a massive breakthrough in improving performance.

                            "For the world is changing: I feel it in the water, I feel it in the earth, and I smell it in the air."

                            T 1 Reply Last reply Reply Quote 1
                            • T Offline
                              Trevan @alkexr
                              last edited by Trevan

                              @alkexr here's some numbers of larger groups:

                              10 infantry, 10 artillery vs same
MiniMax: 219.3 ms, Win: 0.497401100632783, Lose: 0.4974011006327829
Hard AI 200 runs: 2092.2 ms, Win: 0.475, Lose: 0.515
Hard AI 2000 runs: 2086.4 ms, Win: 0.4658203125, Lose: 0.5283203125
FastOdds: 8.9 ms, Win: 0.5, Lose: 0.0
20 infantry, 20 artillery vs same
MiniMax: 585.7 ms, Win: 0.49887594912628747, Lose: 0.49887594912628747
Hard AI 200 runs: 2538.8 ms, Win: 0.54, Lose: 0.46
Hard AI 2000 runs: 3255.3 ms, Win: 0.5029296875, Lose: 0.494140625
FastOdds: 14.7 ms, Win: 0.5, Lose: 0.0
30 infantry, 30 artillery vs same
MiniMax: 1244.4 ms, Win: 0.49930484393068525, Lose: 0.49930484393068525
Hard AI 200 runs: 2873.4 ms, Win: 0.5, Lose: 0.5
Hard AI 2000 runs: 3627.7 ms, Win: 0.501953125, Lose: 0.49609375
FastOdds: 15.5 ms, Win: 0.5, Lose: 0.0
40 infantry, 40 artillery vs same
MiniMax: 2032.1 ms, Win: 0.4995101769999315, Lose: 0.4995101769999315
Hard AI 200 runs: 2904.5 ms, Win: 0.505, Lose: 0.49
Hard AI 2000 runs: 4244.6 ms, Win: 0.51171875, Lose: 0.48828125
FastOdds: 16.9 ms, Win: 0.5, Lose: 0.0
50 infantry, 50 artillery vs same
MiniMax: 3366.8 ms, Win: 0.4996227075274397, Lose: 0.4996227075274401
Hard AI 200 runs: 3574.4 ms, Win: 0.49, Lose: 0.51
Hard AI 2000 runs: 4614.9 ms, Win: 0.4853515625, Lose: 0.5146484375
FastOdds: 16.8 ms, Win: 0.5, Lose: 0.0
60 infantry, 60 artillery vs same
MiniMax: 5306.7 ms, Win: 0.4996976675867421, Lose: 0.4996976675867422
Hard AI 200 runs: 3264.8 ms, Win: 0.54, Lose: 0.46
Hard AI 2000 runs: 5255.6 ms, Win: 0.4931640625, Lose: 0.5068359375
FastOdds: 22.5 ms, Win: 0.5, Lose: 0.0
10 infantry, 10 artillery, 10 armour, 10 fighter, 10 tactical_bomber, 10 bomber vs same
MiniMax: 12470.0 ms, Win: 0.8637525783579469, Lose: 0.13152813492843518
Hard AI 200 runs: 2565.5 ms, Win: 0.32, Lose: 0.68
Hard AI 2000 runs: 2721.8 ms, Win: 0.3125, Lose: 0.6875
FastOdds: 23.4 ms, Win: 0.6286565968532855, Lose: 0.0

                              Interesting that the battle with 30 infantry and artillery was a lot faster than the one with 10 of each land type. Both battle has a total of 60 units on both sides but the addition of multiple unit types slowed it down.

                              alkexrA 1 Reply Last reply Reply Quote 2
                              • alkexrA Offline
                                alkexr @Trevan
                                last edited by

                                @Trevan Hmm, right, you can actually do this in cubic (?) time, so long as the order of losses is linear, because the number of casualties already sustained uniquely determines the composition of the remaining army. But I still don't see how you do it in less than (number of units)^(number of target lists * constant) time, where target lists include normal attacks, AA attack types, canNotBeTargetedBy and related mechanics, etc. Because, without assuming something about the order in which units die, technically there are a million different army compositions strictly smaller than "10 of each land type", as opposed to 60 if you assume a linear order of losses.

                                "For the world is changing: I feel it in the water, I feel it in the earth, and I smell it in the air."

                                T 1 Reply Last reply Reply Quote 0
                                • T Offline
                                  Trevan @alkexr
                                  last edited by

                                  @alkexr yes, my algorithm is assuming the order of losses is linear. I believe the time is roughly what you said. Each target group will have its own order of loss.

                                  1 Reply Last reply Reply Quote 0
                                  • T Offline
                                    Trevan
                                    last edited by

                                    AA guns were a lot harder than I expected but I think I got the majority of it working. I did a comparison on the TestMapGameData.TWW data because it had units that could do aa firing with different target groups. I ran a battle between an infantry, tank, and fighter vs an anti-tank gun, mobile artillery, and anti-air gun.

                                    MiniMax: 197.7 ms, Win: 0.5520100874509435, Lose: 0.40334641519178716
                                    Hard AI 200 runs: 2025.6 ms, Win: 0.57, Lose: 0.42
                                    Hard AI 2000 runs: 3222.8 ms, Win: 0.5517578125, Lose: 0.412109375
                                    FastOdds: 7.9 ms, Win: 0.7703534497836491, Lose: 0.0

                                    Now I'll work on multi-hit units.

                                    1 Reply Last reply Reply Quote 0
                                    • S Offline
                                      Swampy
                                      last edited by

                                      Since I play against the AI quite a bit.. would love this project to succeed as Hard AI is ridiculously slow on large maps/lots of units. Would like to contribute.. but have very little coding skill unfortunately. If you need testers or other basic help... let me know.

                                      1 Reply Last reply Reply Quote 0
                                      • T Offline
                                        Trevan
                                        last edited by

                                        @redrum @RoiEX
                                        I think I have a good majority of the battle logic done. I know I'm missing bombardment, some details in sub first strike (order of strikes and destroyers presence), transport handling, amphibious battles, and paratroopers. There's probably other complexities that I missed as well. I've also worked on speeding it up. Here's a bunch of comparisons:

                                        30 infantry, 30 artillery, 30 armour, 30 fighter, 30 tactical_bomber, 30 bomber vs same
MiniMax: 21218.5 ms, Win: 0.9779225005914358, Lose: 0.021637464729431084
BattleCalculator: 1841.4 ms, Win: 0.95, Lose: 0.045
Hard AI 200 runs: 2893.2 ms, Win: 0.955, Lose: 0.045
Hard AI 2000 runs: 7900.4 ms, Win: 0.970703125, Lose: 0.029296875
FastOdds: 29.4 ms, Win: 0.6517051232809282, Lose: 0.0

10 infantry, 10 artillery, 10 armour, 10 fighter, 10 tactical_bomber, 10 bomber vs same
MiniMax: 1342.4 ms, Win: 0.8637259513264075, Lose: 0.131552773090954
BattleCalculator: 459.2 ms, Win: 0.895, Lose: 0.105
Hard AI 200 runs: 1280.3 ms, Win: 0.87, Lose: 0.12
Hard AI 2000 runs: 2414.4 ms, Win: 0.8486328125, Lose: 0.1455078125
FastOdds: 7.4 ms, Win: 0.6286565968532855, Lose: 0.0

1 infantry, 1 armour vs 2 infantry
MiniMax: 1.4 ms, Win: 0.506233909545216, Lose: 0.38491296598075025
BattleCalculator: 74.3 ms, Win: 0.505, Lose: 0.365
Hard AI 200 runs: 987.0 ms, Win: 0.495, Lose: 0.39
Hard AI 2000 runs: 1000.7 ms, Win: 0.501953125, Lose: 0.3974609375
FastOdds: 0.5 ms, Win: 0.5, Lose: 0.0

1 armour, 1 tactical_bomber vs 2 infantry, 1 fighter
MiniMax: 1.2 ms, Win: 0.11504593215712659, Lose: 0.7947330200775955
BattleCalculator: 99.8 ms, Win: 0.115, Lose: 0.775
Hard AI 200 runs: 1156.5 ms, Win: 0.175, Lose: 0.75
Hard AI 2000 runs: 1244.3 ms, Win: 0.1201171875, Lose: 0.7958984375
FastOdds: 0.2 ms, Win: 0.34082222539412593, Lose: 0.0

1 infantry, 1 artillery vs 2 infantry
MiniMax: 1.0 ms, Win: 0.4574200859119973, Lose: 0.45742008591199734
BattleCalculator: 84.5 ms, Win: 0.49, Lose: 0.44
Hard AI 200 runs: 1095.0 ms, Win: 0.51, Lose: 0.41
Hard AI 2000 runs: 1231.1 ms, Win: 0.4619140625, Lose: 0.443359375
FastOdds: 0.2 ms, Win: 0.5, Lose: 0.0

1 cruiser, 1 destroyer vs 1 cruiser, 1 destroyer
MiniMax: 2.2 ms, Win: 0.4250031963247701, Lose: 0.4250031963247701
BattleCalculator: 86.0 ms, Win: 0.395, Lose: 0.44
Hard AI 200 runs: 1076.7 ms, Win: 0.405, Lose: 0.465
Hard AI 2000 runs: 1213.1 ms, Win: 0.4306640625, Lose: 0.4189453125
FastOdds: 0.4 ms, Win: 0.5, Lose: 0.0

1 cruiser, 1 destroyer, 1 battleship vs 2 cruiser, 1 destroyer
MiniMax: 3.9 ms, Win: 0.7898869382202083, Lose: 0.14239504638191994
BattleCalculator: 122.6 ms, Win: 0.76, Lose: 0.125
Hard AI 200 runs: 1076.1 ms, Win: 0.79, Lose: 0.15
Hard AI 2000 runs: 1188.0 ms, Win: 0.79296875, Lose: 0.1474609375
FastOdds: 0.7 ms, Win: 0.6591777746058741, Lose: 0.0

1 infantry, 1 fighter vs 1 infantry, 1 aa gun
MiniMax: 11.1 ms, Win: 0.5600126123377998, Lose: 0.35180777879589964
BattleCalculator: 189.6 ms, Win: 0.585, Lose: 0.315
Hard AI 200 runs: 1127.4 ms, Win: 0.595, Lose: 0.335
Hard AI 2000 runs: 1410.4 ms, Win: 0.5869140625, Lose: 0.3203125
FastOdds: 0.3 ms, Win: 0.7180577051181194, Lose: 0.0

                                        All of the win percentages are pretty darn close. The 30 of each unit type battle was slower than the original calculator (21 seconds vs 3 seconds) but the 10 of each unit type battle was about the same (1.34 seconds vs 1.28 seconds). The rest of the battles I did were small so it was a lot faster.

                                        What would you like me to do now? Can I make this available to others (such @Swampy) so they can test it out?

                                        1 Reply Last reply Reply Quote 0
                                        • RoiEXR Offline
                                          RoiEX Admin
                                          last edited by

                                          I'm not 100% sure what @redrum's opinion on this is, but I'd really like to see this as an experimental Ai in the game.
                                          But for now hide it behind the test flag?

                                          1 Reply Last reply Reply Quote 0
                                          • Alexei SvitkineA Offline
                                            Alexei Svitkine
                                            last edited by

                                            Perhaps it could be added as a checkbox in the battle calculator for now as well?

                                            Otherwise, I think the two things it needs is a heuristic for when it should be used (e.g. if too many units or when there are unsupported cases, it should do the usual battle calculator instead) and some kind of way to find cases where it disagrees with battle calculator. For example, maybe run some percentage of simulations using both and send error reports when the results disagree too much? Or perhaps we can have an experimental AI that always runs both so we can use it to validate it and find cases where it's incorrect?

                                            1 Reply Last reply Reply Quote 0

                                            Hello! It looks like you're interested in this conversation, but you don't have an account yet.

                                            Getting fed up of having to scroll through the same posts each visit? When you register for an account, you'll always come back to exactly where you were before, and choose to be notified of new replies (either via email, or push notification). You'll also be able to save bookmarks and upvote posts to show your appreciation to other community members.

                                            With your input, this post could be even better 💗

                                            Register Login
                                            • 1
                                            • 2
                                            • 3
                                            • 2 / 3
                                            • First post
                                              Last post
                                            Copyright © 2016-2018 TripleA-Devs | Powered by NodeBB Forums