AI Development Discussion

classic Classic list List threaded Threaded
1250 messages Options
1234 ... 63
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

AI Development Discussion

redrum
Administrator
This post was updated on .
So I decided that I'll keep high level information around the AI development in this first post. Please only post AI related discussion, testing, bugs, and questions in this thread. I may eventually split this thread into several if it becomes to difficult to manage everything in one.

I always need lots of people to help test the new AI on various maps. If you do find a bug or poor AI play when testing please describe the issue and attach the save game in a post.

Download
The latest stable AI is currently released in the stable 1.8.0.9 which can be downloaded from: http://triplea.sourceforge.net/mywiki/TripleA

Latest Development Version (Pre-Release)
Can be downloaded from here: https://github.com/triplea-game/triplea/releases

Status
- Rewritten all core phases (combat move, noncombat move, purchase, place, retreat)
- Most testing has been done on revised maps and v3 maps (WW2 revised, WW2v3, NWO, etc)
- Trying to test stability on all maps and need lots of assistance!

Unimplemented Or Need Improvement Items
1. Add checks for all resources not just PUs to avoid purchase failures (completed)
2. Enemy Turn Order and Defending Against Multiple Attacks (completed)
3. Allied Turn Order and Multiple Attacks to Weaken Then Conquer Territories (completed)
4. Consider attacking with strategic bombing raids (SBR) (completed) 
- Improve Performance on Large Maps
- Consider Purchasing 0 Movement Units (Static Defenses)
- Valuing Objectives
- Consider strafing and defending against strafing
- Consider V3 rule around subs not blocking naval movement
- Consider V3 rule where fighters don't defend against subs
- Rewrite bid purchase/place
- Consider victory city points
- Improve AA gun movement
- Defending capital against multi-turn amphib attacks
- Improve USA purchases on Great War
- Improve unit production consideration to always use TripleAUnit.getProductionPotentialOfTerritory()
- Add per map XML AI configuration
- Add purchase 'value' for resources besides PUs
- Transport mobile factories
- Consider air/naval bases strategic value and purchasing
- Consider value of saving at least 1 land unit when selecting casualties
- Consider capital farming when determining whether to take back an allied capital
- Add support for 'upgrading units' (consuming an existing units)
- Consider interceptions and escorts

Bugs
- (0 known bugs)

---Hard AI Overview---

Summary
- Mostly based on trying to optimize TUV gains and minimize TUV loses based on the battle calculator.
- It does some strategic consideration in regards to where to move units towards and whether to be defensive if threatened.
- It performs pretty well on maps based on revised/V3/V1 rules in that order
- Should not crash on any map that is considered stable

Combat Move
- Check if capital is threatened and if so enable defensive stance (tends to attack less)
- Find max number of my units that can attack each territory
- Prioritize attack territories based on value
- Loop through prioritized attack territories and see how many I can actually attack
- Find max enemy counter attackers for each attack territory
- Determine which attack territories can possibly be held
- Remove any attack territories that aren't worth attacking (neutrals, low value, etc)
- Determine which units to attack each attack territory with
- Determine final sea territories for transports making amphibious assaults
- Determine if I can defend those transports and if not then possibly abort that attack
- Determine if I can hold my capital after attacks and if not then slowly remove attack territories
- Actually send all combat moves to delegate to update game data

Non-Combat Move
- Find list of all allied territories that I can move units to and how many I can move to each one
- Find units in move territories that can't move (allied, no movement, etc)
- Separate out non-combat infra units (mobile factories, AA guns, etc)
- Try to move at least 1 defender to each territory to block blitz attacks
- Find max enemy attackers for each move territory
- Determine which move territories can possibly be held
- Prioritize territories to try to defend
- Determine which units to defend each prioritized territory or if it can't be held
- Determine strategic value for each move territory based mostly on distance to valuable enemy territories
- Determine where to move remaining units to safe territory with highest strategic value
- Determine were to move non-combat infra units
- Actually send all non-combat moves to delegate to update game data

Purchase
- ***Simulate all phases until place is reached***
- Find all purchase options
- Find all territories that units can be placed and how many
- Find max enemy attackers for each place territory
- Prioritize place territories that need defended
- Determine best defender and purchase necessary amount for each prioritized territory
- Determine strategic value for each place territory based mostly on distance to valuable enemy territories
- Prioritize land place territories by strategic value
- Determine whether to purchase AA for any land place territories
- Purchase best land units combinations for prioritized land territories (based on available purchase options and enemy distance)
- Purchase land factory if any 'good' candidates
- Prioritize sea place territories based on strategic value
- Purchase naval defenders, transports, and amphib units for prioritized sea territories
- Purchase high attack and high movement (preferrably air) with any remaining production
- Replace purchased land units with more expensive units with any remaining PUs
- Purchase factory if any 'decent' candidates with any remaining PUs
- Actually send purchase map to delegate to update game data and save map of where to place them

Place
- Place units based on purchase phase result or if no purchase map then try to place in best possible territories

Code Organization
- games.strategy.triplea.ai.proAI.ProAI - main AI class which extends AbstractAI and overrides many of the methods, orchestrates the 'Hard AI'
- games.strategy.triplea.ai.proAI - has core AI phases and data containers
- games.strategy.triplea.ai.proAI.logging - has logging utils and UI
- games.strategy.triplea.ai.proAI.simulate - has simulate utils used to simulate combat move, battle, and non-combat move for purchases
- games.strategy.triplea.ai.proAI.util - lots of utilities, matches, etc
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
do you have any kind of chat program, or are you ever in the online lobby?
i'd certainly like to talk

here is my suggestion:

the #1 problem with the existing AI's, especially with Dynamix AI (which had a ton of potential and a very smart coder behind it), is that they were made to beat AI's

in order to test their creations, moore ai was played again easy ai for many turns, and dynamix was played against moore ai for many turns

the result are AIs that are slightly better than old AIs, but still make millions of stupid decisions and over all just suck


DO NOT TEST AGAINST OTHER AI's

make the ai to beat humans

you do not need to do more testing, and it will not take more time, than testing against other AI's

instead, pick out a selection of "situations" from a variety of maps.  save the game at that point, and let the AI play just 1 turn.  evaluate what a human would have done in that situation, and see why the AI made the wrong or sub-optimal choices.

that single turn, or even that single phase, will tell you more about how your AI is performing than a thousand games against the other AIs will

an example would be:
take Russia turn 1 on Revised map.  save the game right before combat move, and see what your AI does for combat move and non-combat move.  There really is only 1 optimal set of moves for this turn (hitting ukraine with almost everything that can reach, and then hitting western russia with everything else).  

another good spot to test is germany and/or japan turn 1, on world war II v3 (aa50).  this is a good example of having a lot of opportunities, and being able to take almost all of them.


Also, i would suggest using Weak AI as the tool to learn from, and maybe start by extending weak AI's code and then just doing a phase at a time from there
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
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Hey Veq, I'm pretty much always on gchat: ron.murhammer@gmail.com. I'm never on the online lobby but might consider it if you think many of the developers usually are.

You make a very good point. I guess maybe I shouldn't have mentioned the beating of the AI at the end of my last post. This is mostly just my initial goal and something that is easy to measure whether I've reached. It is harder to measure that one AI is better than another AI against human players until it is way better.

I don't think its possible to program an AI that would actually beat the expert players on tripleaWarClub without some small bonuses. There is just so many possibilities and I'm not looking to take a brute force of simulating several turns as that will become too slow (chess approach). That being said programming an AI to beat average players or at least survive for awhile against expert players is the true goal.

I totally agree about testing a single turn scenario and seeing how close to optimal it plays. Just need to make sure that I test enough different scenarios. Just because it makes the optimal move in revised turn 1 Russia doesn't mean it does very well in revised turn 1 Germany, etc.

FYI: In terms of optimal revised turn 1 Russia (low luck), it actually might be better to also attack Belorussia in a no bid game or if the bid isn't placed in eastern Germany :) But I understand your point.

I haven't played or looked at weak AI's code much so not sure if that might be better to extend. Either way if I just rewrite a phase at a time, I could technically extend each of them by just replacing the existing phase with the new phase.

Thanks for the excellent feedback.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
i'd jump on the lobby, as this is where pulicat, rolf, and several others find each other to talk
otherwise you can also email me (especially for more detailed things that we need to write down, like at patch time)

i certainly don't mean scripting an ai to play certain turns, but creating a rather general AI then evaluating it in very specific situations, or evaluating its play against a human while looking for big mistakes

obviously you are never going to beat expert players.  but every time moore ai and dynamix ai decide to give up the caucasus round 1 on revised i just cringe.


i should also mention another reason why i don't want you to play test again the AI: it will create the wrong incentives and wrong ideas for your ai

case in point: wisconsin never considered that most battles in a game are actually very small fights, what would be called "trades", fought to kill TUV and/or claim some income and/or get in a better position
because he was playtesting against moore ai and his own ai, he came to believe that the main thing he was coding for was large battles.  he never realized that if at any point the battle calc says my force will lose, i will just move 1 step back and reinforce (with obvious exceptions).


play testing against a human for a single phase or turn also has another huge advantage for you: it lets you focus on just that phase

too much time is spent trying to make an AI that does everything well.  wisconsin (who coded dynamix) burned himself out trying to make an AI that did everything.

by starting the game after the purchase phase, you can make an AI that just does combat move and non-combat move well.

take a bunch of your game saves, or grab a bunch of game saves from online games, and throw the AI into a variety of situations.  

include a lot of logging of what the AI is doing, and spend some time in the debugger watching it think, and I guarantee that your AI will be performing better the the other AI's against real humans, very quickly
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
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Totally agree. I would rather focus on making an AI that makes optimal combat moves and not worry about the other phases. So pretty much just testing different scenarios starting at the beginning of the combat move is perfect.

I guess my question is there anyway to test the AI in a batch mode or without launching the graphical interface. Say I want to test just a single combat move turn 100 times to see how the combat move AI does. Or say I want to run it through a set of combat move scenarios and just see the results.

Otherwise I have to actually launch the game select the game and go into the graphical display to see how it does.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
no way currently

unless you are heavily randomizing stuff, your ai will be fairly deterministic, so only 1 run through should be enough

you can always start with a deterministic ai and then add in randomizing later
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
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Well since I'm using the battle calculator it will be some what random so seeing the average of at least a few results would be better.

Unless you have something to simulate battles better and provide an average TUVswing, units left, win percentage that isn't random and runs faster?

Since it is some what random, several results help to make sure there are no bugs.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
I have created a new github repo for developing the new AI: https://github.com/ron-murhammer/TripleA

This is were I will develop the new AI and eventually push the changes back to SVN.

If you are interested in contributing just let me know.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

blumb
In reply to this post by redrum
You could make a mini map xml that spawns the units at the begining of the round and clears the map at the end of the round, then look through the history after 10 rounds or so of the "repeated turn".

That might suit your purpose.

2nd thought a slightly larger map (the Belgian one?) or a big one might work better.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Interesting idea. I think that is why I'm looking for. Just be able to run through multiple scenarios and just see the results. Though I think I would still need to at least launch the GUI for that.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

blumb
You said you've been using the b/c.
I don't know but, the battle calc should have a log of the simulations.
Perhaps running fewer simulation counts and reading the log might be easier.
You might be able to free yourself from using the GUI that way with a little code.

Not so sure why you don't want the GUI as it seems the easiest way to change units.
Maybe a closed circit bot running the b/c GUI without a map and puts the log in a folder/open window?

Just thoughts, I have no idea what the java looks like... how easy things are, ect.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
In reply to this post by redrum
I wouldn't get hung up on creating utilities, it will just be a waste of time.


I also would not use the battle calculator, at least not at first.


Here is a good formula that is correct 99% of the time.  It is really only inaccurate when the battle is very close to 50/50, and even then it is not inaccurate by much.


Total Strength = (2 * Hitpoints) + (Power * 6 / DiceSides)

In my own testing, this function is VERY accurate, and very quick.
If one side has a larger total strength (by this formula) than the other side, it will win.  You can determine just how well it will win, by the % that the number is larger than the enemy's number.


You could make a static function for this:


final int myHP= BattleCalculator.getTotalHitpoints(mySideUnits);
final int myPower = DiceRoll.getTotalPowerAndRolls(DiceRoll.getUnitPowerAndRollsForNormalBattles(mySideUnits, mySideUnitsAndAnyoneElseOnMySide, enemySideUnits, amIAttacking, false, myPlayer, gameData, battleLocation, territoryEffects, isAmphibiousBattle, (isAmphibiousBattle && amIAttacking ? mySideUnits: new ArrayList<Unit>())), m_gameData).getFirst();
return (2 * myHP) + (myPower * 6 / gameData.getDiceSides());
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
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Hey Veq. Thanks for the formula though I'm already doing something similar where I'm eliminating battles that aren't close by checking if one side has both more hitpoints and power.

I don't think using just that formula is enough though as I also need to figure out average TUV swing and average units remaining. Why do you recommend not using the battle calculator?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
Just because it is slow as hell.  You will be surprised at just how many battles you need to calc every phase.  I recommend storing information between phases so you don't have to recalc everything for each phase (but make sure you can handle if i load a game at any point).

I also recommend making your ai multi-threaded if possible, as the smarter it gets the slower it will get too.
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
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Yeah it is pretty slow but using a lower run count can help to mitigate that (currently I'm using 20). Also do you think there is anyway to improve the BattleCalculator's speed?

Trying to store as much information as possible and going multi-threaded are both things I would like to do but I want to focus on making it make good decisions first even if it is a little slow. Then look into improving speed. And by slow I mean keeping it within reason (maximum of a minute per turn).
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Hey Veq. I just submitted a patch with the initial version of the AI (just rewriting the combat move AI). Let me know if you have any questions or if there are any issues with it. Link: https://sourceforge.net/p/triplea/patches/87/
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
This post was updated on .
I thought about making the battle calc itself multi-threaded, but haven't really gotten around to it.  Also not sure if it is worth it.

I would also not use 20 count for the calc, but at least 100 count.  When you have such a small count, one of the main drags on time will actually by copying over the game data (when the calc is initialized).  So increasing the count to 100 will not seriously affect the total run time I think.

Another good way to limit the time spent is to be really smart about when you use the battle calc at all.  I know as a human I rarely use the calc at all, and can skip using it for several rounds.  I only really have to when there are really close battles.


edit:
About the patch, I think we should give your AI a silly name, to continue the tradition of silly names.  Give me some suggestions...
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
|  
Report Content as Inappropriate

Re: AI Development Discussion

redrum
Administrator
Hey Veq. I think improving the battle calc's performance is definitely something I would eventually like to look into unless I replace it with something else to determine the average battle outcome as this appears to be by far the slowest component.

Ok, I haven't looked at the battle calc's code so thought the the number of runs was the way to try to speed it up. I'll do some testing to see how much longer 100 runs vs 20 runs take for an AI turn.

Also, if the copying of data is done when the calc is initialized, then could I just initialize the calc once and keep reusing it during the combat move phase?

Yeah, I know trying to minimize the battle calc's use is definitely a good idea but there are things that a human can work out by just looking at the map and an attack that the AI can't. Usually when trying to determine how many units to attack each territory with is when I find myself needing the battle calc the most. I can use different formulas to decide when I can win but by how much and whether I should attack with 1 more unit is difficult without actually simulating it.

I don't really have any naming suggestions but you can call it pretty much whatever in the AI selection display though you may want to add an alpha or beta tag next to the name. I honestly just picked "Pro" because it was short so makes the variable names in the code shorter :)
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

ubernaut
i do like the idea of modularizing the various stages of the turn i think this would facilitate eventually getting to the point where there could be "personality" variables for AI.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AI Development Discussion

Veqryn
Administrator
In reply to this post by redrum
I committed your patch.

A few comments:

1. did you know that SVN 1.8 and later use a single .svn file in the root directory of the project, rather than a .svn file in every directory?  just curious, since i saw you deleted all the .svn files, when this should not have been necessary

2. i would recommend having your main class be called "ProAI", and then farming out the different phase calls to new classes, such as "CombatMove", "Purchase", etc.

3. I do not plan on reviewing or testing any code changes within .../ai/proAI/*
At some point I'll have time to look stuff over, but for the most part I'm going to leave it up to you unless you specifically ask for my help.
Anything changing any other part of the engine, I will be carefully reviewing of course.

Do not be afraid to fix bugs or improve other parts of the engine though.  If you see something you want to use and improve, there is no sense in copying and pasting it into your AI package, just so you can work on it.  Instead improve the original and leave it there.


4. I haven't looked at your AI yet to really see if you are doing this or not, so please disregard if you are already doing this: Please make your AI not hardcoded to a specific map or even a specific genre of maps.

Here are some good examples of different maps you could test on:
270bc
Napoleonic Empires
New World Order
Great War
Lord of the Rings
World War II Classic
World War II Revised
World War II v3 1941 (aa50)
and some Free for All map, such as Capture the Flag or Napoleonic 5 player FFA

Obviously your AI can be better at some maps, such as AA50, than others.  
But it shouldn't lock up or refuse to recognize that units exist when they are called "spearmen" instead of "infantry", or when they have unit stats that don't match the profile of typical A&A games.
It also means that movement validation and combat are slightly different depending on the rules sets: most famous being that transports can not be taken casualty first in v3 and later games.


thanks,
veqryn
Please contribute to the TripleA 2013 donation drive:
http://tripleadev.1671093.n2.nabble.com/2013-TripleA-Donation-Drive-tp7583455.html
1234 ... 63
Loading...