Development Discussion: Speeding up battle calculator (and thus Hard AI)
-
From what I recall in previous measurements the game data copy dominates. Copying only needed data or redefining the input data structure to not need a game data but only the needed battle data would be a win. From another perspective as well the game data copy scales to the size of the map and history. This can cause battle calc to be difficult to use in late stage games on large maps. That implies that AI would grind to a halt as well and is not scaling for that situation.
One tension and problem is direction and focus. To expound, we can have 'fast by design' or 'fast by happenstance'. There is lot of not good code that has been heavily optimized that puts us in a catch-22 situation. You can't update the code because it is complex and optimized, to get it to be simple and fast you need to update the code (which you can't do). The most significant performance gains are from design, architecture, not strategic fixes. For example with code that is so complex it takes 3 hours to understand 30 lines, we're not going to get it to ever be as fast as possible because we won't be able to see how we can get it so the code does not need to be executed.
With that said, I do have a re-write of default casualty selection in flight that is looking to be pretty fast and much simpler. I think we'll want to continue re-writing large chunks of MustFightBattle and related code as it has all snowballed to be incredibly complex.
From another perspective, there are problems/bugs, if we optimize incorrect code, we could be placing ourselves in a very bad situation where we have fast but buggy code. "Get it right, simple, fast, in that order". We kinda skipped the second step a few times in the name of adding more functionality and features and then getting it fast.
From another perspective, we do want to change game data copy/serialization to not be serialization. I was thinking this problem would be mostly solved when we change how game data is saved. We want the save game data to not be serialization so we can sanely control what constitutes a save game breaking change. For now we've been in a good spot since we are not maintaining save game compat, but soon changes will be rejected if they break compat (which could be extremely trivial changes, and again puts us in a place where we can't make the needed changes to fix things because the code becomes just static, complex, and not the best it could be).
Expounding on that more, I've been thinking beyond strategic re-writes of certain code to simplify it and make it faster, the larger problems would be solved by changing save-game serialization (saves) to be to a text format, make that fast, which then solves both a performance issue and the very major problem of save-game compatibility.
To get there it's hopeful too that we can break apart game data so that it is not quite such the god object. To that I was thinking we could move map data to be a sub-project that does not depend on game-core and provide as main output a 'map-data' object that is a java view of the XML data to later be interpretted as attachments etc. This would in turn help decouple some of the hardcoded and brittle aspects found in XML data, relieve some data found in game-data, create a set of immutable data that we would not need to save, which makes for faster copies and smaller save games.
Circling back around, a lot of the deeper fixes to solve multiple problems are quite heavy lifts, doing smaller lifts in the meantime can help but could make some problems worse as well. Overall it is a difficult situation. IMO backing up, adding good testing and then larger re-writes and then following up with sane performance improvements based on fast-by-design is likely to be the winning approach.
-
I don't know if this has been thought of or tried before but what about instead of running simulations, why not do something like expectiminimax (https://en.wikipedia.org/wiki/Expectiminimax)?
You can build out a tree where each level has all the possible losses. The chance nodes would then determine what the probability of the possible losses. You might be able to do this without needing to copy the game data or without running lots of simulations. You also might only need to calculate the order of losses once and use that to build out the tree.
-
That's an interesting idea, the number of leaves on the tree that result in a win divided by the number of total leaves would be the win probability. Each branch would need to have equal probability, so we'd have a tree that is potentially quite large, but perhaps still tractable.
For default casualty selection we cannot do that, we need to know the best next unit to select; AI though arguably should avoid using default casualty selection when simulating battles and is free to use any custom or clever algorithm it can.
-
An expected MiniMax Tree would be an interesting concept to apply here, but while it sounds reasonable in theory, I think the way battles currently work are way to complex right now for a feasibe implementation.
But in the end I'm convinced that from an AI perspective as well as a resource perspective this is a far better approach than "simulating" battles, so if someone has the endurance to give this project a shot I don't have any objections to this approach
-
@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.
-
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.
-
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.
-
@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?
-
@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
-
@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).
-
@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.
-
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.384912965980750251 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.79473302007759551 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.457420085911997341 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.42500319632477011 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.344007714807463171 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.2000276003717069The numbers look pretty close except when AA guns or two hit battleships are used. I don't handle those.
-
@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.
-
@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.51 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.340822225394125931 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.51 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.51 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.65917777460587411 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.7180577051181194Fast 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?
-
@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.5How is 200 runs slower than 2000 runs?
-
@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.
-
@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.0Interesting 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.
-
@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.
-
@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.
-
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.0Now I'll work on multi-hit units.
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