Latest Posts

Topic: News about AI

Tibor

Topic Opener
Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2016-10-17, 23:29

Hi


While we are waiting for new release I started working on re-work of AI (again). After a lot of thinking I decided to try to use some AI approach - and after some digging on net I settled on what is called genetic algorithm.

For some cool videos about this branch of AI look at:

https://www.youtube.com/watch?v=pgaEE27nsQw
https://www.youtube.com/watch?v=lPQnVEnFTgY

and many many more.


I already have something working, this branch:

  bzr branch lp:~widelands-dev/widelands/ai-post-b19


I dont insist that it will be ever merged to trunk, but at least for me it is very interesting private project. Bottom line is that parameters inside AI (and there is A LOT of them) are tweaked on trial and error principle. It works, though is not working good enough yet. There are four points to mention:

  • Training is automated - after each "round" the "genes" in code are replaced and code recompiled - so some human intervention is still needed to allow AI to 'learn'
  • It is (the training/"natural selection") SLOW. Especially due to fact that one map can have only 8 players. And I have only home PC that of course does not run 24/7. So I cannot claim the AI is good enough now.
  • Or rather is is too unbalanced - because of high mutation rate sometimes the generated AI is good, sometimes mediocare. Of course this needs to be stabilized before being ready.
  • This does not imply, that there is no coding needed. This is not true, coding as needed as before, only tweaking of parameters is done automatically (saving my time from endless observation and small tweaks in code)


I googled a lot, but it seems that genetic algorithm is not much used for games like this - at least not on in open. I presume that a lot commercial games are using this already though.


I also started a blog about this: http://tiborb.blogspot.sk/2016/08/developing-widelandss-strategic-game-ai.html


Well, this I write just as information for all fans of game. If you are curious, just ask. And any ideas are welcome.


PS: if you are curious how such 'DNA' looks see here: http://bazaar.launchpad.net/~widelands-dev/widelands/ai-post-b19/view/head:/src/ai/ai_help_structs.cc#L487. The code contains DNA of 4 'players' identified by map names in code. Bottom line is that the coder does not need to understand what the numbers means - though if needed it is easy to find out.

Edited: 2016-10-17, 23:53

Top Quote
DragonAtma
Avatar
Joined: 2014-09-14, 01:54
Posts: 351
Ranking
Tribe Member
Posted at: 2016-10-18, 03:10

I've looked at AI before; even for simple games, the AI is terrifyingly complicated. >_>

That said, how hard would it be to raise the max number of players? If there's a private branch just for teaching the AI, then having 100 AIs and having them flow off the bottom of the monitor would not be an issue unless it crashes the game.


Top Quote
Tibor

Topic Opener
Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2016-10-18, 19:38

DragonAtma wrote:

That said, how hard would it be to raise the max number of players?

I tried it, but it seemed as a chain of "fix here and it will backfire elsewhere" work, I was not able to estimate how long it would take. F.e. there are a lot of windows that expect 8 players, additional player colors must be added and probably other issues....

I circumvented the limitation the way that I run multiple games within one "round" and pick one AI that performed best and recompile and start new round (we can say generation of AI). But if you consider that some AI simulations (f.e. shown on videos on youtube) have 1000 individuals and a generation lifetime is 5 minutes - the widelands cannot compete with that...


Top Quote
toptopple
Avatar
Joined: 2013-10-30, 08:11
Posts: 156
Ranking
At home in WL-forums
Posted at: 2016-10-19, 05:34

What is the strategy of applying this type of genetic AI? As I understand this AI would tweak parameters of the player AI, which is a different thing. In what context would any results of the genetic generations be available to the game? Would it be a fix result for a package release or would the genetic be running on each user's installation with individual results?

Then also of interest: how do you calculate / what are the criteria for Fitness in the generations?

Edited: 2016-10-19, 06:03

Top Quote
DragonAtma
Avatar
Joined: 2014-09-14, 01:54
Posts: 351
Ranking
Tribe Member
Posted at: 2016-10-19, 06:17

The idea is that the AI would slowly improve so it's not at the point where many people can win a 1vs7 against them.

As for "fitness" that presumably comes down to "which AI wins the game?".


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2016-10-19, 12:17

I guess that there are some problems to solve:

  1. long time of "learning" the AI (one game = 0,5 hours at least)
  2. how can we choose "best AI" if all of them died? (player win)

There are many factors and probably there is no easy solution.

For example we can provide part of widelands server to download "latest version" of AI and upload game results (if the player accept that!) but there should be a mechanism that will pick best factors. There is no easy solution for that (I can't see it now). But practising the AI will be much faster...


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
DragonAtma
Avatar
Joined: 2014-09-14, 01:54
Posts: 351
Ranking
Tribe Member
Posted at: 2016-10-19, 16:03

I'm sure the testing will be AIs only.

I do have a question, though: which game type(s) will you be using? An AI that does well in Wood Gnome may fare poorly in Endless Game, and one with revealed map may not do so well with fog of war.


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 3324
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2016-10-19, 17:35

I have created a branch that allows 16 players, with repeating player colors:

https://code.launchpad.net/~widelands-dev/widelands/max_players

The engine can handle up to 31 players, but there isn't enough UI space to set them all up as AIs. If you only start from command line, you could add more though.


Busy indexing nil values

Top Quote
Tibor

Topic Opener
Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2016-10-19, 19:17

> *toptopple wrote:*
>
> What is the strategy of applying this type of genetic AI? As I understand this AI would tweak parameters of the player AI, which is a different thing. In what context would any results of the genetic generations be available to the game? Would it be a fix result for a package release or would the genetic be running on each user's installation with individual results?
>
> Then also of interest: how do you calculate / what are the criteria for Fitness in the generations?

Very good questions!

AI is not able to learn during the game (all variables are static) and are not even able to learn on a user's box - all variables are hardcoded in source files. So the learning is that I copy/paste DNA of best player into cc file and recompile.
However as by now, when AI player is initialized some small mutations are applied to DNA - for me it is needed for "evolution" and is planned to be used for difficulty levels - the weaker AI the higher mutation.

Fitness function is about:
land size + land difference to average land size of players + strength difference to average difference of all players + 100 points if player ever attacked

I have changed fitnesses few time - it is not easy to come up with good one


Top Quote
Tibor

Topic Opener
Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2016-10-19, 19:41

> *DragonAtma wrote:*

> As for "fitness" that presumably comes down to "which AI wins the game?".

No, this way we would lost information. How do you evaluate that in 5 games there were 5 winners? The issue here is low number of participated players to pick from.

So contrary to it, I read "score" in appropriate moment, f.e. for Crater it is 1:40m. This is time that the best AI ever is able to destroy the oponent - so far this has not happened yet I think - but sometimes it is close.

I am attaching a screenshot from a test on Crater map:


Top Quote