Important Dates

Currently Online

Latest Posts

Topic: AI roads rework

Tibor
Joined: 2009-03-23, 23:24
Posts: 1231
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2019-06-04, 21:37

OK, few comments:

  • AI makes "atomic" decision. It just decides about connecting single building to road network. What will happen with the road, how will it be promoted if ever, or will end up just dead end - it does not consider or predict it.
  • destroying a road is also atomic decision, not connected to anything. So it cannot "straighten up" existing road, because they are two independent actions - dismantling and building new one, AI is not capable of such bundling the logic and actions.
  • When distance to warehouse is only metric, we would end up with many almost pararel roads and wasting a lot of fields. So another metric is length of the road to be built.
  • 3 steps roads - I am not sure if we can find out before placing the road how it can be split by flags. I see the code: map[c].nodecaps() & BUILDCAPS_FLAG but I am not sure if the nodecaps are or are not changed by placing a road. If we can know it before actual placing the road. Moreover, sometimes 3 step roads are probably necessary..
  • pre-building roads in multiple directions - I was thingking about that, what complicated this is that at the same time we have the code that dismantles dead ends without building and this would be the case... but I will thing about that....
Edited: 2019-06-04, 21:41
Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1231
Ranking
One Elder of Players
Posted at: 2019-06-04, 22:52

GunChleoc wrote:

Maybe you could add something that the AI always tries to build roads in all 5 directions coming out of headquarters/warehouses, before placing any buildings near them? And then leave them there, even if the flags are unconnected at first.

this won't do much, but it's a good idea. certainly useful. could be implemented

Tibor wrote:

  • 3 steps roads - I am not sure if we can find out before placing the road how it can be split by flags. I see the code: map[c].nodecaps() & BUILDCAPS_FLAG but I am not sure if the nodecaps are or are not changed by placing a road. If we can know it before actual placing the road. Moreover, sometimes 3 step roads are probably necessary.. [emphasis mine]

that's the crux of the issue. when you have mostlly flat land and a large map, you absolutely want to avoid 3 steps roads. transportation is going to be a nightmare, and you need everything you can to keep it streamlined. It's worth sacrificing a few building spaces for it. And it's definitely worth making a road slightly longer, for example if you have a 3 step distance you make a curved road to have 4 steps and be able to split them in segments of 2.

But, on the other hand, when you have a small map and rugged terrain, then you need every building space you can scrape up, and 3 steps roads aren't an issue, because you don't have enough traffic for it to be a problem.

And if you have large but rugged land, you make a few major highways that are always 2 steps and as straight as possible, and then you make all kinds of smaller roads where you don't care much.

A skilled human would know in advance the rough shape of the map. Even if one went completely blind, one may start with cramped roads, and then once he sees the map is getting bigger and transportation is getting messier he would straighten the roads at the cost of dismantling several buildings.

AI doesn't try a map first, but AI starts with the map scouted. we can use this feature.

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.

Another option is to program the AI to recognize major directions and make major highways. A major direction is the shortest route between two distant large plots of buildable land. On this major direction a major highway will be built, and it will be a road that must be relatively straight and it must not have any 3 steps road. Problem with this is that those are all fuzzy human concepts.

I can play ice wars as bllue and immediatey see that I want a highway going from the middle straigh nort-east, with another NE-SW highway every screen or so, and a series of east-west highways also every screen or so, and a single SE-NW highway in the middle because it takes away space for buildings. And I can also recognize that the best way to make that SE-NW highway is for it to overlap the central mountain, because that way I'll still be able to get all the ores under the road, and i will lose less valuable building space. while on two frontiers I want a single highway going around the island, or maybe two highways, one on the inner and one on the outer side of the ring. But how the hell do I translate this into algorithms?


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

Road building is based on scoring, so I can include in the scoring also if there are any 3steps sections in future road. I can hardcode roads in few directions from starting headquarters. But to recognize the terrain layout - it is too much for AI. It can count buildable spots in radius x - but this is not what you mean. It can walk around starting spot to find out how big territory is achievable, but it has difficulties to recognize if it is really achievable, because you need military sites to cross some terrains and it is complicated for AI. Also usually there is shortage of buildable spots so AI tries to save them so this enforces the tendency to curve the roads....

So it is not easy to find fit-all-possibilities solution...


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 2862
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2019-06-05, 08:48

map[c].nodecaps() & BUILDCAPS_FLAG but I am not sure if the nodecaps are or are not changed by placing a road.

Yes, they are changed, especially for each flag placed on the road.


Busy indexing nil values

Top Quote
JanO
Avatar
Joined: 2015-08-02, 11:56
Posts: 45
Ranking
Pry about Widelands
Posted at: 2019-06-05, 08:52

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.


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

Tibor wrote:

So it is not easy to find fit-all-possibilities solution...

that is the core of all difficulties


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

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.


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

WorldSavior wrote:

GunChleoc wrote:

Maybe you could add something that the AI always tries to build roads in all 5 directions coming out of headquarters/warehouses, before placing any buildings near them? And then leave them there, even if the flags are unconnected at first.

Or even better: Not 5 roads, but just two double-roads of length 2.

I believe that this would not add much benefit as the AI tends to build quite a few warehouses after a while so traffic jams in front of the QH are not the main problem. However we could build them (or the old settlers triangles) at the beginning and see what happens. The problem might be that this might not be possible on some maps. but on the other hand this shouldn't matter that much.
@ 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.


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

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.


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

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?


Top Quote