Latest Posts

Topic: AI roads rework

Tibor
Joined: 2009-03-23, 23:24
Posts: 1238
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-05, 10:34

hessenfarmer wrote:

@ Tibor : I believe neither the two double roads of WorldSavior not the settlers triangle design would be recognized as dead end by the algorithm. as there are two roads attached to each node.

Exactly - dead end is a flag with one road and no building attached...

EDIT:

However, AI can decide that one of the roads is not needed that much and dismantle it. Especially if there are no wares on flags...

Edited: 2019-06-05, 10:37
Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 663
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2019-06-05, 10:55

Tibor wrote:

hessenfarmer wrote:

king_of_nowhere wrote:

Perhaps we could have the program count the total amount of buildable space in the map and divide it by the number of players, giving a measure of how much land every player can expect. The higher this number, the more the AI will try to avoid 3 steps roads; the smaller the number, the more the AI will try to salvage as many building sites as possible.

counting them might be possible as we just need to go over the map once and count the buildcaps without taking immovables into account. I implemented this interface lately to count the reachable land for territory win conditions. This might indded be a measure for 3 steps road allowance.

But if AI starts on small island and remote spaces does not matter at all and it has to save as many buildable spots as possible?

That would be a problem currently unmanageable for the AI. AI is currently able to escape the starting island on crossing the horizon in only 60 to 70 % of trials. It simply wastes to many spots with roads but this should be better with your latest fix. I'll give it a try next week. Perhaps you could merge trunk and trigger a merge request to get me some appveyor builds. (compiling lasts about 80 mins on my old machine)


Top Quote
Tibor
Joined: 2009-03-23, 23:24
Posts: 1238
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-05, 11:56

ok, I will clean the code a bit and place formal merge request...


Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 663
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2019-06-05, 12:27

Tibor wrote:

ok, I will clean the code a bit and place formal merge request...

Thanks a lot. I will not be able to test until Tuesday due to a short holiday so take your time.


Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1361
Ranking
One Elder of Players
Posted at: 2019-06-06, 21:04

hessenfarmer wrote:

JanO wrote:

How complicated would it be to give the AI some kind of help for cheating. What I'm thinking of is to add some hints for the AI into the map itself. Important directions to expand or areas that should be handled as independent economies for example.

It would be very complicated and not desirable. Reason is that if we implement a special cheat or even a bunch of them per map the AI on the map would be predictable and this would mean you only need to find out what the Ai will do to develop a counter strategy in an instant. Furthermore these "cheats" would differ from tribe to tribe. This is against the concept of having a map and tribe agnostic AI which works sufficiently (although far from perfect) on every map with every tribe in any circumstance.

not necessarily. Some of those things could be implemented without much hassle and without being a problem. For example, major areas that should be linked by highways. Marking that would simply ensure that the AI tries to keep a straight road without long segments between two such areas. Doesn't make it any more predictable, and the AI can work without that anyway.

But I agree it's probably not worth it.

Tibor wrote:

hessenfarmer wrote:

king_of_nowhere wrote:

Perhaps we could have the program count the total amount of buildable space in the map and divide it by the number of players, giving a measure of how much land every player can expect. The higher this number, the more the AI will try to avoid 3 steps roads; the smaller the number, the more the AI will try to salvage as many building sites as possible.

counting them might be possible as we just need to go over the map once and count the buildcaps without taking immovables into account. I implemented this interface lately to count the reachable land for territory win conditions. This might indded be a measure for 3 steps road allowance.

But if AI starts on small island and remote spaces does not matter at all and it has to save as many buildable spots as possible?

that's just a very rare situation. of course we can't make AI fit for each one of those. a human would have trouble adapting to some without knowing the map in advance.

If the algorithm is coded to save build spaces, and it's not a big hassle to estimate the amount of buildable space on the map, then changing the algorithm so that it adapts the rreciprocal value of straighter roads against conserviing build spaces depending on map size would be a good idea.

Only problem I can think with that is that such a value would need to be codifed for the map. I recall the AI does not save any kind of information, and it would greatly slow the game if the AI had to recalculate the factor every time it makes a road. So the AI should be able to calculate the factor once, store it and keep using it for later.


Top Quote
Tibor
Joined: 2009-03-23, 23:24
Posts: 1238
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-07, 09:57

These are multiple approaches to building roads:

  • save building fields (when making road to specific building/flag)
  • ignore building fields (when making road to specific building/flag)
  • try to make straight roads (when making road to specific building/flag)
  • build longer roads leading nowhere (no building to be connected by them)

The last one is most complicated, but the third option an be actually quite ease to implement, the AI would add some bad bonus for every turn of a possible road - when possible roads are scored. But at the end I am not sure if it would be worth the effort... how big the difference would be. It would not guarantee straight roads, but only increase the chance for them....


Top Quote
Tibor
Joined: 2009-03-23, 23:24
Posts: 1238
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-15, 17:09

There should be builds available now in https://code.launchpad.net/~widelands-dev/widelands/ai_flag_warehouse_distance/+merge/368544


Top Quote
hessenfarmer
Avatar
Joined: 2014-12-11, 23:16
Posts: 663
Ranking
One Elder of Players
Location: Bavaria
Posted at: 2019-07-07, 14:14

I did some compare testing on the maps I normally watch AI games on. (I do this to recognize areas for improvement in the AI) I believe this change is an improvement over current trunk, so I would like to see it going in. Of course it is not perfect but I think a policy of going small steps is better then aiming for a perfect solution which is not achievable probably.


Top Quote