AI Development Discussion

classic Classic list List threaded Threaded
1250 messages Options
123456 ... 63
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
it depends on how your patch behaves with the existing way the battle calc works for players, so i'd have to see it

worst case, we create a separate btl calc for your AI

the game data copying probably takes as long as maybe ~20 calcs.  you'd have to time it.

another idea would be to, at the start of the phase, initialize ~4 different instance of the battle calc each with its own copy of the game data

then run them all in separate threads

or if that is too difficult (since you have to make sure to do multiple different calculation at the same time), we could make a multi-threaded version of the battle calc, that way you still only have to do one calc at a time, they just complete quicker

something that is initialized at the start of each phase (if we actually have units or stuff to calc), has 2-6 threads in a thread pool, etc etc

we can also think about caching the results somewhere, that way we don't need to re-calc things every time.  
the only problem with caching results, is that Unit Stats change throughout the game.  So for example, caching the result of 4 infantry + 1 artillery vs 5 infantry, will only be valid until the units change (like if we get 'improved artillery', etc).
We'd also need to keep in mind things like whether territory effects are active, whether the battle was amphibious (isMarine units get bonus), and other battle state things.

still, if we figure out a good way to determine when to invalidate cached entries (or the whole cache), this could speed things up significantly.


also, will you be looking into a better way of logging, like i suggested before?
wisconsin's dynamix ai logger is quite nice and you could copy and paste with the modifications to remove all his 'fluff'
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Alright I'll play around with the BattleCalculator then to see what I can do. Just wanted to see what your thoughts on it were.

I think I'll first try to optimize it staying single threaded. If that doesn't do much then I'll think about multi-threading it but if I do that most likely I'll create a new 'AI' version of it so I don't accidentally break anything with the engine. I think using multiple battle calculators would be tough since then I'd pretty much have to multi-thread the whole AI which I'm not ready to dive into that yet :)

Yeah, logging is the one other thing I'm gonna work on. Forgot to add that to the list.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Hey Veq.

I actually just ran some tests. When using a run count of 100, the data clone takes about 50% of the BattleCalculator's time on average. So just cloning the data once per combat move phase saves a significant amount of time already.

Here are some stats on NWO Germany turn 1 (in nano seconds):

CombatMove time: 75,899,696,462
BattleCalculator time:        62,100,797,055
BC copy data time: 27,938,482,770
BC calc time: 33,812,658,527

-----------------------------------

CombatMove time: 51,631,593,393
BattleCalculator time:        36,626,284,061
BC copy data time: 0
BC calc time: 36,004,234,914

So you can see it saves about 25 secs (almost 50%) of the BattleCalculator's time. The CombatMove time also includes moving the units on the map so really the BattleCalculator is probably about 90% of the AI think time.

I'm definitely going to make this change and submit it in the next patch. Going to look into multi-threading the calc portion next and see how it goes.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

captaincrunch
Awesome! Keep up the good work!



Midnight Oil - Power and the Passion;

http://www.youtube.com/watch?v=6pKPNnk-JhE
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
In reply to this post by redrum
anyone who wants to try out redrum's ai can do so by downloading this version:
https://sourceforge.net/projects/tripleamaps/files/TripleA/prerelease/

just download 1.8.0.3 first, then download this new jar file, and copy it over 1.8.0.3's old jar file (in the /bin/ folder)


Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Rolf Larsson
Agreed Captain, Awesome already!

Gave it a short try with Feudal Japan, which really lives from a good AI.

I played the dark red Mori Clan until round 9.

Here is a save, if you want to check redrum:
FJAITEST.tsvg

Sure, game mechanics give AI already some useful boni, but:

- I haven´t seen stupid waste of PUs/Units by attacking MinorClan territories, with good defense.
- Nice frontline shortening and defense
- A nice amphibious assault on an enemy capital
- Nice evacuating of "save" territory

Not sure if the AI would have had build much castles, without the selected boni for it.
Does it take constructions into consideration and the limits/maximum of placement for it?
Does it take into consideration the defense bonus vs. immobility?
Do you plan integrating requirements/limits for production? Would be cool!
Does the AI check the turn order, its phases and which enemies might still attack this round before next placements/movements are possible to increase defense/attack power for next round? I think, when loading the save, Date clan build defense vs. MinorClan, although they have no combat move at all.

Keep up the great work.
We now have custom dice!
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Hey Rolf.

Interesting map, I've actually never played it. Pretty cool, reminds me of Sengoku.

So far I've actually only rewritten the CombatMove phase so all the other phases still use the MooreAI. It looks like most of your questions are regarding what the AI is choosing to purchase and place which haven't changed from the Moore AI implementation (so it still purchases/places rather randomly). Mostly I would be interested in if the AI seemed to make any stupid attacks or didn't attack where it should have (as this is what has changed).

I looked at your save and noticed a few things:
- You got sort of lucky that Urakami attacked north and east instead of west and then they got stomped by Yamana in round 2. This led to a wall of minor clans territories to build up and block you off to the east.
- The new AI is actually written to perform best on team maps since it considers killing enemy units (TUV swing) when deciding what territories to attack. This causes it to probably be overly aggressive on a FFA type map like this. Though maybe this is a good thing since if it played more defensive then you would just slowly march through each one rather than it killing each other to form stronger opponents.

Question:
- How do you think it fared in comparison to the MooreAI on this map?
- Did you notice any AI CombatMove phases where its attacks were sort of stupid?
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
So I did some initial testing on making the battle calculator multi-threaded. Here are the results for NWO Germany turn 1, running each one twice:

10 Threads
-----------------------------------
BattleCalculator time: 20788310055
BattleCalculator time: 19367384677

4 Threads
-----------------------------------
BattleCalculator time: 20524511840
BattleCalculator time: 19867592338

2 Threads
-----------------------------------
BattleCalculator time: 23085626361
BattleCalculator time: 21173778768

1 Thread
-----------------------------------
BattleCalculator time: 30581913279
BattleCalculator time: 36770819625

So I see a significant improvement increasing from 1 to 2 threads but after that there doesn't seem to be much difference which surprised me a little bit. I'm guessing this is because the engine already has at least 1 thread and my laptop only has 2 physical, 4 logical CPUs (i7-620M). I also monitored my CPU usage and at 1 it was ~30%, at 2 it was ~60% and at 4 it was ~90%. I think someone with 4 physical, 8 logical CPUs can probably get it to run in 10-12 secs.

Overall, I think this is still a significant improvement though not as impressive as just copying the data once instead of every time (which was a much easier change). I think I'll probably set number of threads to 10 so that those with better machines hopefully get even better performance. Also besides a little more memory there isn't much drawback to setting it to 10 instead of say 2 or 4.

If anyone knows a lot of concurrent processing in Java, now would be a great time to chime in :)
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
Using more threads than the CPU has available can actually serious slow down the calculation under some circumstances.

I recommend you just use this call to figure out how many threads the CPU can handle, and use that:

                final int availableThreads = Math.max(1, Runtime.getRuntime().availableProcessors());

Most people will have 4 threads available, but I like to make it dynamic with the above statement, because who knows what will be standard in 5-10 years.
(I have a 4 core cpu with hyperthreading, so 8 logical threads.)

Do not worry about the fact that TripleA itself has some threads going.  Those threads are normally suspended or waiting for great periods of time while we are waiting on some user input.  The above call will actually give different results depending on if some of your cpu's threads are currently being used to a great degree.


Also, since it takes time and resources to start up and shutdown threads, I recommend using a thread pool, which you can make static and initialize the first time the calc class is loaded.  Have it call the above method and create a number of threads equal to that.  You can then pass work in to the pool, using either standard threads that are returning work as part of an atomized reference, or using an executor server to return futures.
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Rolf Larsson
In reply to this post by redrum
Haven´t noticed any silly attacks. All attacks were reasonable as far as I can tell. However the TUV alone evaluation may be critical, as you can have upgrades/consume of units and the new unit may consume one or more very high priced units, while the resulting unit itself may be cheap. Next thing is, that it might be easy to trick the ai, when it does not consider counterattacks, but sure you had a lot of thoughts about it already. I suggest one new unit attachment, lets say : "unitvalue"="1-20" just for the ai, a map maker can set it and thereby help your ai to determine what units are good and which are not so good, would also help targetting capitals and production territories, by just placing an invisible/immobile unit with a high unitvalue there.
We now have custom dice!
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Veq - Alright I'll add the method to check for the number of threads. I'm currently using Executor Service and Callables to return futures for the AggregateResults. I'm going to work on adding the logging stuff from dynamix then submit a patch some time this week and you can look over the multi-threaded stuff.

Rolf - so it already considers counter attacks and whether it can hold the territories its attacking. It also adds value for capitals, factories, and how much production a territory has when determining which territories to attack. Mostly likely for games with more than 2 teams, the TUV swing should just be weighted less.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Hey Veq.

Its that time of the week! Here is the latest AI patch: https://sourceforge.net/p/triplea/patches/94/

Its mostly focused on battle calculator optimization and adding the in-game logging window. Let me know if you have any questions or want me to rework anything.

Overall, the battle calculator changes improved performance significantly. On my machine, NWO Germany turn 1 takes about 20 secs now and before it took around 60 secs. Should see even more improvement on machines with more CPUs.

I took the Dynamix settings window and reworked/enhanced it to just have a logging section since I don't have any settings yet. Also cleaned up logging for the Hard combat move AI.

I tested on a few other WWII maps and the AI does alright but definitely needs to consider objectives and some of the more advanced features such as scrambling.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
Questions,

I imagined we would have 3 steps instead of 2:

1. Initialize calc with a pool of x threads.  We keep the calc around for as long as we want, like the lifetime of the ai instance.

2. At start of phase, we set the data in the calc, and set up the workers.

3. When we want to calc, we set up the units, territory, settings, etc, then run the concurrent calc.


It looks like you have combined the first two steps?


I also would have preferred separate patches for the calc vs the other changes, but it is ok.
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Hey Veq.

That's correct. It could be divided into 3 steps: create thread pool in constructor, have an initialize data method that would be called at the beginning of each AI phase to set current data, and the method to pass the battle parameters.

I originally had it that way but decided to combine it into just 2 steps for the following reasons:
1. Step 2+3 are where 99.99% of the processing time are so separating step 1 doesn't really gain us much.
2. Simpler. Just need to create the BattleCalculator at the beginning of each phase with current data and pass battle info each time to simulate. Don't need to worry about keeping a reference outside of each phase.
3. Less risk. If the thread pool or threads had any issues it would only affect a single phase since it is recreated each phase.

Let me know if you want me to separate it and I'll do that and resubmit the patch.

In terms of patch content, I have no problem dividing up patches more. At this point, I'm just submitting one a week with all the changes but in the future can divide it up if the changes are related to different areas.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
looking more at this patch, there are some issues

data is not locked before we begin copying it, which wouldn't be a problem since copying locks it, except that it could change between our separate copies (to separate workers)

you never shutdown your executor service.  this results in thousands of threads after many turns, all of them in memory, none of them GC'ed.  also, since your threads are non-daemon, they would stop our exit if we didn't explicitly call system.exit().

the worker class seems sort of superfluous, why not have the main odds calculator class implement callable?

the proai class is creating a new calc with each phase, which seems unneeded.  we should be able to create a single calc per instance, and let your phase methods get it.  with each instance you are creating new threads, which is not needed.

i will work on fixing these things, and also doing some further optimizations

no need to resubmit, i enjoy touching this patch :)
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
Hey Veq.

Comments/questions:

1. Not sure I understand why the data needs locked. What would change the data between making the separate copies? In general, what would change the data while the AI is calculating combat move phase? Do I need to lock the data for the entire combat move phase? If anything changes while I'm calculating what moves to make it could throw the entire calculation off.

2. I didn't think shutdown needs to be called. I thought the callable threads after they are finished will be GC'd. Is that not that case? Maybe I'm miss understanding how ExecutorService works since I haven't done concurrent programming in a while. Did you test and actually see thousands of threads sitting around not be GC'd?

3. I originally did add callable to the OddsCalculator class but decided to create a separate class to minimize changes to OddsCalculator since I know the engine uses it. I have no problem if you want to merge the OddsCalculator and worker classes as that was my original intention.

4. I thought creating a new calc with each phase is simpler and safer than keeping one around for the life of the AI. This is pretty much what I described in the previous post of why I made it 2 steps instead of 3. If you really feel that is better than that is fine with me.

Ok, let me know if you have any other questions and when you merge the patch so I can pull down and look at the changes.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
1. This is more good practice than anything else.  Since your AI is single threaded, nothing could change the game data while you are copying the game data.

* Delegates automatically have a lock on read/write.
* The only things that write to gamedata are delegates.
* Therefore gamedata will not change while delegates are not executing

When the engine calls 'start' for a player (such as your ai), no delegates are executing at all.
Until your AI returns from 'start', no delegates will start executing again.
If your AI calls a delegate method, the delegate may execute some action, but after it returns it has stopped executing.

Therefore, the only one who can change gamedata is your AI, and it would only do so through a delegate method.

So for example, if your AI calls the delegate method to take a "political action", causing it to go to war with some player, then the delegate would make that change.  At that point, the game data has changed, and your AI could still make more political actions, etc.

If you pulled and copied the game data at the start of the political phase, then went to war, your game data that you copied would now be out of date.

This doesn't affect your AI at all yet, and I sort of doubt it would ever affect it.


2. Yes, tons of threads.  The whole point of a thread pool is to avoid creating new threads, or rather, to only create the number you need and keep re-using them instead of making new ones each time.  Also, the executor service doesn't automatically shutdown once it goes out of scope.

3. Will do.

4. Will do.

Lastly, i see that your AI is still outputting to my console.  I thought the logger took care of that?  (it shouldn't be outputting to the console, unless it is an exception being thrown that isn't catched)
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

redrum
Administrator
It is logging to both the new logging window and the normal logger which still logs to the console. This is configured in the LogUtils class. We could remove the normal logger or just change the normal logger's level to WARNING or something like that.
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
lets just remove it, because right now it is throwing a severe message when the game is exited, and i don't want to scare users (it is a 'gameoverexception', which is normal)
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
Reply | Threaded
Open this post in threaded view
|

Re: AI Development Discussion

Veqryn
Administrator
In reply to this post by redrum
Ok so I had a really good look, and liked the patch a lot
but i couldn't help but change some stuff

i am also a little rusty on my concurrency, so if you could review my changes:
https://sourceforge.net/p/triplea/patches/94/
or http://sourceforge.net/p/triplea/code/4189/

i changed your ai to use a static instance of the calc, but feel free to change it to an instance if you want, just make sure to shut them down when you are done (and FYI, the ai's don't get finalized regularly, so you will have to find a different way to make sure it gets shut down once a game is exited)
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
123456 ... 63