Pathfinding: Putting in the yo-yo

[Capt Dizle]

I hope that Soren works on the pathfinding at some point.

Let me try to explain the problem.

Early in the game when the AI has only the tech to travel on coast squares you can easily block the AI's pathfinding by simply putting sea units in place so that the AI would have to travel in sea squares to get where it wants to go.

If you do this you can yo-yo the AI up and down your coast line. Block and watch the AI retreat, open a hole and watch the AI advance.

This is not good.

The same principal exists on land. Create strongpoints across a land mass and the AI will retreat in the face of it. Take care here to understand that the AI has been programed not to attack strongpoints.

Remove a single unit and the AI will advance directly to the hole in your picket line. Plug it, the AI retreats. Yo-yo.

The many ways to exploit this should be clear without further comment.

The above is not speculation, but is gathered by first hand experience. It is CERTAIN.

Had to throw that in for Cyclo....

I can't say right offhand how to fix this but I would love to see pathfinding and combat attack or do not attack routines randomized.

If culture flips can be dealt with in a manner as to yield a percentage per turn chance to occur, perhaps movement and combat inititives can be randomized to some extent. It would be an improvement.

[notyoueither]

re the ships. You mean their galleys won't go around yours even though they can end in coastal tiles on the other side of you?

[Capt Dizle]

edited out....

I am wavering on whether or not you have to block the first sea tile (which you can do in certain circumstances).

[DeepO]

I observed this too, but as there is nothing Soren can do about it, I classified it an AI exploit, and stopped using it.

How I used it: in one of my games, I shared a long, banana shaped continent with English and Germans. As the English we're military stronger, I did not want to provoke a war. So when their side of the banana was fully settled, they wanted to cross my land to get to the area between me and the Germans.

I built a line of warriors from one side of the continent to the other, all in my territory, and so that no foreign troop could cross. So, I captured the English on their territory, as they didn't have galleys yet. But, at first I didn't have enough warriors in place, so wanted to keep those first two settler parties out as well. I formed a line of 4 warriors, and let them dance: move one tile up with the whole line, the settler would go down. Then I'd go down, the shortest way was up for the settler. I kept them dancing until I got the whole line in place -- could have been 50 turns or so, I was in no particular hurry until I was dancing around with 5 different settler parties. That became rather complex

As a result, I growed to 3 times the size of England, keeping a lot of troops occupied. As I was building up my forces to finish England off, Germany(about the size of me) declared war to them. They just discovered map making. I figured it would be nice to keep everyone occupied in the middle of my territory, so I open up the line by removing one warrior, and let the opening dance around. From both sides troops came in, lots of troops. It was rather amusing to have knights, then cavalry, then even infantry dancing around my line of warriors. Meanwhile, I was gaining a big tech lead, and loads of tanks. So at a certain turn, I declared war to both England and Germany at once, mowed everything inside my territory down (used over 200 tanks, which all used up their movement points. Not bad for a standard map), and the next three or four turns were used in taking all of England and Germany. That was of course the easy part, there were only simple defenders left behind, as the AI had no chance of upgrading them with the maintenance for all the units they had running around.

After that, I'm still tempted to use the smaller version (4 warriors yo-yoing), but I try to resist. It is an exploit, no human player would fall for this, but there is no way an AI can counter it. The only possible solution is to attack the warriors to get through, or move everybody back home and ship them to the other side (which they would do if there weren't a gap in the line).

What was rather clever and unexpected, is that later on I tried to build up a full line (no gap this time) in a similar situation. One piece of advice: do not block the Russians when they are out for war. They saw the line, and without any warning declared war on me. And of course, in stead of battling the warriors, they went for my low defended cities... I never recuperated and had to abandon the game

DeepO

[Coracle]

I've seen the "yo-yo" nonsense occur with land units, also.

That has happened all too often with settlers marching into my territory; I block them, and they go south; I block them again and they had back north. We do that dance over and over.

I once did a TEDIOUS BORING dance with a stack of wandering Indian war elephants that kept moving into my territory from one of those stupid isolated towns that the dumb AI built deep in my territory.

[Capt Dizle]

Oh, I used a version of this blocking think in a game in which Caesar was about to be gang banged by about six other civs. I got a ROP agreement with him and sent two transports of outdated cavalry over and build a shield. One by one the AI civs, unable to find a valid path, called off their war.

Saving Caesar.

[DeepO]

While normal blocking (so without a gap, or dancing) could be considered a tactic (albeit a cheap one), I strongly feel the dancing should be viewed as an exploit. Of course, if you want to cheat in your game, go right ahead, but it creates an unfair advantage over the AI.

And as said above, there is very little improvement that could be made to the AI; it requires another level of metaknowledge which is far too complex. The only acceptable solution would be that if it takes a certain amount of time (say 5 turns of yo-yoing) the AI would attack what is blocking them. But once a human player figures something like that out, it could become an exploit in itself (get the spearman with the settler underneath to attack another spearman, while archers lure).

Only one solution: self-discipline

DeepO

[player1]

AI should be chaged in that way that it should PREFER to use ships instead of enemy land to get through.

And in case of war, it should attack checkpoints.

[star mouse]

I used the 4-unit blockade to great effect to avert a likely war with the French in one game. The French suddenly crossed my border near a weak city with 94 assorted units - infantry, riflemen, a few musketeers and swordsmen. I put up the blockade between them and the city, cancelled the Right of Passage with them and renegotiated peace. They left and never returned.

[nato]

I do wish the AI would attack strongpoints a little more.

I have seen some very nice AI armies! I think it must have been very difficult to program the AI to build and concentrate all those units so well. But then instead of attacking my front line or even second line cities (which do have walls and some defenders) they parade past, trying to get to my inner, less defended cities. But they never make it! Often I make peace, and see the same impressive parade marching back home.

I think they might do better to just take a shot attacking. Just seems like it must have been harder to get the AI to build well and get the troops in a usable mass than to program it to attack with them.

[Apocalypse]

You can only improve pathfinding so much. It takes up a lot of RAM.

[DeepO]

Player1, I think that the path finding does prefer ships to get through instead of land. But, when an army has a land path of 3 moves to get to the other side of a small, 4 unit blockade, it will of course never walk 15 moves to a harbor, take a ship, and sail another 5 moves to get behind the line.

The fooling happens when a human player yo-yos, so that each turn the AI thinks the shortest landpath is 3 moves. But as you adjust the situation each turn, it stays 3 moves, instead of diminishing like in a normal path finding routine. That is the exploit, as said, in a static situation (blocking, and keeping put) the pathfinding algorithm will find a better solution, and if it can it will use ships to go around the blockade.

star mouse, if you had a static line instead of a moving one, that is just a tactic you could use, even in MP. After all, you just created a second line of defense, which is fine. It's when you start dancing, occupying the AI for a long time that it becomes an exploit.

Apocalypse: I think the path finding is quite good, given a static situation. The problem is that path finding is a relatively independent part of AI, which doesn't take into account the larger (political) situation. Therefore it doesn't notice that you are deliberately fooling it by changing the static situation each turn so that he has to yo-yo back and forth. You can do this in each TBS I know, and even in RTSes, although it is more difficult to perform there.

DeepO

[Apocalypse]

I know the Civ 3 pathfinding is good. It is far better than in many other games I've played. I'm just stating that it can take a lot of system resources for it to be really good.

[DeepO]

I thought you implied that, and I agree, but the way I see it the pathfinding is more or less perfect. Adding additional ram wouldn't improve it, in order to avoid the yo-yoing it would require a whole other understanding of the situation, and interaction between different parts of the AI. And that is something which is largely limited by coding extra routines, not by system resources. It's a matter of cost-return: you don't program an extra year on the path finding, only to have it perform better in some very specific situations when there are more important AI routines that need attention.

DeepO

[Arrian]

Originally posted by nato
I do wish the AI would attack strongpoints a little more.

I have seen some very nice AI armies! I think it must have been very difficult to program the AI to build and concentrate all those units so well. But then instead of attacking my front line or even second line cities (which do have walls and some defenders) they parade past, trying to get to my inner, less defended cities. But they never make it! Often I make peace, and see the same impressive parade marching back home.

I think they might do better to just take a shot attacking. Just seems like it must have been harder to get the AI to build well and get the troops in a usable mass than to program it to attack with them.

I concur. There have been several instances where an all-out assault on a key strongpoint of mine would have worked, and caused my great difficulty, but the AI refused to attack it, preferring to try and march around. Meanwhile, I was able to strengthen my defense, and start whittling away at their monster stack of troops.

The AI has got force concentration down pretty well. What it needs now is the killer instinct. I also think the AI needs a small tweak to redress the 1-move unit overkill it presently has. If the AI comes at me with 50 riflemen, I'm worried. If it came at me with 40 Cavalry and 10 riflemen, I'm terrified (unless, of course, I've got infantry )

-Arrian