Dynamix AI Development Thread

classic Classic list List threaded Threaded
441 messages Options
1234 ... 23
Reply | Threaded
Open this post in threaded view
|

Dynamix AI Development Thread

Wisconsin
This post was updated on .
I'm thinking that the best way to create an AI is for the TripleA community to make it together instead of each developer creating their own AI and failing to perfect it. (I have recently attempted to develop an AI myself, and it ended up with a slow, land-unit-only AI that could only win on the one map that was used for its development.)

Here are links to some AI design guides that I found:
http://www.gamasutra.com/view/feature/1535/designing_ai_algorithms_for_.php+strategy+game+ai+design

The next 5 posts are reserved for parts of the AI code that need work. This way anyone else who understands java can help improve it. If you see an improvement that could be made to the AI strategy or you think we should add new logic to the AI, just post a message at the end of this thread, and we will review it and possibly add it to the AI. For those of you who can't code, there are still many things you can help with. Any other assistance you can give will be greatly appreciated.

To make it easier to explain things about the AI's strategy to each other, we can use the following example map scenario:
(Image Removed)

The following posts contain some parts of the AI code that need work: (For the rest of the code, just download the patch files in the AI status posts located in the thread.)
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
This post was updated on .
Hmm... Laziness has destroyed my 'pseudo-code' plans...
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
This post was updated on .
Same here...
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
This post was updated on .
Reserved for AI code...
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
This post was updated on .
Reserved for AI code...
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
This post was updated on .
Reserved for AI code...
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Bung
In reply to this post by Wisconsin
Just some random initial thoughts to add to the brainstorm:

Regarding, "Reduce the score by some other stuff [todo]" .. one of the things i think included here is having the machine calc the battles so they dont send more than necessary.

If we include that, minimizing battles, how will the machine move against someone, by stacking remaining units in a valuable spot that they can actually hold?

Perhaps that's more of a LL thought, in dice you cant always minimize battles and sometimes you dont even want to (leaving a few units in each spot isnt bad in dice)... so perhaps there should be a distinction there as well.
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Pulicat
In reply to this post by Wisconsin
When having the AI considering attacking two weak enemy stacks, is it possible to have the AI run the battles thru the calculator and pick the one with the best expected TUV gain to execute?

puli
how now brown cow?
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

zlefin
In reply to this post by Wisconsin
you're welcome to try but i don't think this will work.  when last i made an ai thread the result was clear: the problem isnt' finding people who can design a good ai (or pseudocode) the problem is finding someone to do the actual coding of the ai.
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
In reply to this post by Bung
Bung wrote
... one of the things i think included here is having the machine calc the battles so they dont send more than necessary.
Yeah, I was thinking that too, that's why I made a method just for it in my AI Utils class. It can calculate a possible battle while the AI is still thinking of moves. Because of how handy this method is, I could make it so that the AI attacks with exactly the right amount of troops to take the territory in one hit, for example.

Bung wrote
If we include that, minimizing battles, how will the machine move against someone, by stacking remaining units in a valuable spot that they can actually hold?
We could do that, and perhaps have the AI only move towards the enemy when it knows it's safe to do so. Things like this are what we should decide together, part of the purpose of this thread.

Pulicat wrote
When having the AI considering attacking two weak enemy stacks, is it possible to have the AI run the battles thru the calculator and pick the one with the best expected TUV gain to execute?
Yes, I already have this in the AI I coded. The problem is that my AI has a very bad strategy base. If we get the strategy base designed well, we can plug in these battle calculation methods to get perfect attacks and moves.

zlefin wrote
...the problem is finding someone to do the actual coding of the ai.
I'm willing to code this new AI myself, if necessary. I know the code enough to make an AI, it's just that I need help constructing the AI strategy and such. Really, if we can get together a good AI strategy, I'll try my best to convert the pseudo-code into real java code and creating the AI. (Splitting the time between the AI and the map creator... I like having two or more projects to switch between to keep things interesting)
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

zlefin
well, then i'll resume planning the strategy for the ai since we have a coder.
i'll review my planning so far and have some preliminary notes tomorrow.
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
Thanks!

For anyone interested, here are some of the other AI related threads that have come up over the months:
http://tripleadev.1671093.n2.nabble.com/AI-discussion-td2334319.html
http://tripleadev.1671093.n2.nabble.com/better-AI-td2264242.html
http://tripleadev.1671093.n2.nabble.com/on-making-ai-s-coding-td5652910.html

Hopefully this time we can actually succeed in creating a better AI!

Thanks,
    Wisconsin
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Veqryn
Administrator
In reply to this post by Pulicat
let me caution against using TUV as a good indicator of when to attack for the AI
if you do decide to use TUV as an indicator, please make sure the AI still has a higher than 60% chance of winning before it attacks
currently the moore ai uses TUV to some extent in its calculus, and it ends up making some pretty hair-brained attacks because of it

in my opinion, it should go like this:
1. the AI should first figure out what battles it can possibly win
2. the AI should then decide which of those battles are the most important in forwarding its objectives (whatever those may be, for example: protecting your own capital, closing off any blitzable areas to the interior of its land territory, moving towards an enemy capital, destroying a large number of units for a big TUV swing, a specific multi-turn objective like ferrying troops across the atlantic, etc.)
3. the AI should then figure out what is the minimum number units to commit to the most important battle in order to win it with high percentage (97% minimum if they have extra forces, otherwise the most that can reach the battle).  Then the AI should commit those forces.  
4. Then the AI should loop back and do #1 again.  This is because if you do not loop back, the AI will not know how many forces are left over with after committing enough to win that first battle.  
5. After the AI has no more units left that can reach battles that it CAN win (or it has been thinking about battles for more than 20 minutes straight) it should stop looping and start playing the battles.

Also, i think we should try to keep it relatively simple.  Things like suicide attacks, or more advanced tactics, should be left out.  

And the AI should be generic in nature.  There should be no specific code for America, Germany, Russia, etc.  I would rather go and make a special "AI_hooks.properties" file in each map, than have an ai that works for a nation called "america" but not for a nation called "Island_nation_that_must_ferry_troops".  The same applies to units and maps.  This AI must work with ALL maps and all units, whether that is ww2v3, ww2v4, NWO, 270BC, Napoleonic Empires, etc.

thx for starting this wisc,
veqryn
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: Brand New AI Development Thread

subotai
In reply to this post by Wisconsin
Good initiative, I will just repeat what I've said earlier about TripleA AI: make it competitive, because if it can't win with a $50 bid it won't win with a $100 bid either, it will just take more time to beat the AI. The "overall principle" that applies for human vs human games will also be valid for human vs AI games. A $50 bid in a human vs human game is a joke, and $100 bid in a human vs human game will only make the joke last shorter. If the AI can put up some resistance with a $100 bid, it will be technically the same with a $50 bid.

The main problems with the 2 current AI's, is that even when the AIs get a $100 bid, it takes only a few turns until the human player have much more TUV, even if the AI starts with a substantial advantage. After that, it's only a question of time.
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Daral
In reply to this post by zlefin
The problem with pseudocode is that the quality can be even more variable than real code.  You have to build an efficient and decoupled class structure, otherwise turning the pseudocode into real code will basically require re-architecting it.

The thing that made me hesitant to say I'd help out in the last thread is that pseudocode can be arbitrarily high level, which is basically shoveling more and more work onto whoever translates it into real code.

Anyway, on a broader note, I'm willing to help out also.  I think the first and most important thing to do is to figure out what sort of design to use for building this AI.  That means figuring out 1) the general algorithm, which implies 2) the set of parameters that can be used to alter performance.  (2) is also known as "feature selection", which means choosing the things that are considered important enough in the game for the AI to be worth considering.

Really what you're doing is building an implicit objective function for evaluating the quality of a given game board position.  Just as in an alpha-beta search tree, the quality of your objective function will determine the quality of your AI's play.

IMO, the best way to build an AI for this game is to develop 3 things: first, a search tree algorithm that generates a limited set of search options from each position.  It will use a heuristic to create this limited set of moves.  Second, (and this part is logically simple but technically it can be difficult) a simple function to copy the game board into a new data structure, so that it can be manipulated without affecting the real game (to generate hypotheses).  Third, build an evaluation function (i.e. objective function), which is used to evaluate game boards.

The advantage of this technique is that it gives you the maximum flexibility to alter the search algorithm (choosing what moves to consider making) and the evaluation function (determining the quality of a given position after the search algorithm considers it).  These two will be fully decoupled, which allows you to alter them independently and to maximize both.

The basic algorithm works like this:

Consider all the moves I can make (by calling search algo)
          For(each move I can make)
          {
                  Consider each response my opponent can make
                  For(each move opponent can make)
                  {
                        ...recurse indefinitely
                        At end of recursion, Evaluate(final game board)
                        If(evaluation score > max_prev_score)
                            Set max_prev_score = evaluation score
                            Best_board = new_game_board
                   }
          }
Make_Move(best_move)

I'll admit that there are a number of challenges to this approach and it will take some work, but the advantage is (like I said) that it decouples the search algorithm from the evaluation function.  This would allow separate programmers to work on each, and it also grants you additional flexibility for altering either.  This will make it easier to change the feature set that is used for the evaluation function and the search heuristic.

Challenges:
1) develop a heuristic that is sufficiently limited in move selection that you can perform more than 1 ply of search (ideally 2-3 turns).
2) develop an objective function that can reasonably evaluate the game board
3) build the technical infrastructure for copying game boards and connecting between the "Move" (in a formal sense) chosen and the actual delegates that perform the work on effecting your move on the game board.  Since the algorithm is somewhat high level, there will need to be some infrastructure to "implement" your move in the real game interface.
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Daral
Just to be clear, it is definitely possible to make a master-level knowledge system.  It just takes a lot of work because you have to program in all of the tricks and sub-scenarios that it needs to know.  So it requires quite a bit of detail-work.
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
In reply to this post by Veqryn
I really like the AI combat move instructions you mentioned. I'll add it in for the combat move phase pseudo-code.

I agree that we should only add in stuff like suicide attacks after we get the AI working really, really well. If you add it in as you go, the code tends to get very messy becomes almost impossible to debug and improve.

I also agree that none of the AI code should be hard-coded to any unit, maps, or country names. It should be based off of xml data alone...

Thanks for the input,
    Wisconsin
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
In reply to this post by subotai
Yes, you're right, if an AI can't win with 50 it either has bad strategy or makes lots of mistakes, meaning that an increase in bid points will either mean a slower AI defeat, or the AI will win only because it has tons more troops. (If an AI gets like 1000 bid points and it at least places them in okay locations, it can win even with really bad strategy. But yes, it is very boring when the only way you can win against an AI is when you give them ten times as many troops!)

I will try my best to make it competitive, but I should note that this is my second ever attempt at coding an AI, so don't expect it to rival the Moore N' Able any time soon. (Though I do plan on getting it to play well, it will take a lot of time and a lot of trial-and-error)

Thanks,
    Wisconsin
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
In reply to this post by Daral
Yes, for me it's more difficult to use pseudo-code, but I'm willing to use it if it means other people can help develop it. About the work translating it into code, I'm okay with that. I've already spent over 20 hours working on an AI, but because it didn't have good strategy, the AI failed. Even if this AI takes a lot longer than that, I'm willing to try it.

Hmm... Using an alpha-beta like algorithm(first step) would probably give the best results, but if we don't implement it correctly(if we don't develop a good hueristic) it will take very, very long to process the moves. I've never actually used an alpha-beta search tree before, but I think I understand the idea.

I think the second step(copying the game board for testing) will be fairly simple to do, because most of the existing methods take a game data object for it's own use, meaning we can copy the game data object, apply and change, and test it with the existing methods without adding much code.

The third step shouldn't be too hard, but I think we will have trouble getting it to evaluate the game state quickly.

I really like the idea of splitting the AI into these three parts, as it seems like it would be very easy to update and manage. I have spent a lot of time looking through the StrongAI code because it is so complicated. This approach will be easier to make changes to, I think.

Over-all, I think this idea is great! Now that we have the basic direction(I think), we can start increasing the detail of the pseudo-code. I sometimes have trouble writing stuff in pseudo-code, so let me know if something doesn't make sense.

Thanks,
    Wisconsin
Reply | Threaded
Open this post in threaded view
|

Re: Brand New AI Development Thread

Wisconsin
In reply to this post by Daral
Yes, which is why I agree that we shouldn't add in these details until later.
1234 ... 23