AI improvements

[Toxic]

AI improvements

There are my ideas how to improve the AI in the KaM. The following improvements are just small adjustments which will "optimalize" already existing algorithm. If you don't want use it, I respect that, it is your creation .

1. TKMayor
   • CheckUnitCount - the adaptive recruitment of serf (it works better than fixed count of serfs per a city):

       Code:

     Output := Max(0, gHands[fOwner].Stats.GetUnitQty(ut_Worker) - gHands[fOwner].Stats.GetUnitQty(ut_Serf)); for I := 0 to p.Units.Count - 1 do if not gHands[fOwner].Units[I].IsDeadOrDying AND (gHands[fOwner].Units[I] is TKMUnitSerf) AND (gHands[fOwner].Units[I].UnitTask = nil) then Exit; Output := Output + 1;

     + check to be sure that we have enough gold left for self-sufficient city (gold for a Metallurgist / Miner) because sometimes get AI stuck;
   • GetMaxPlans - the adaptive addition of plan count (it really helps the AI to build the city faster):

       Code:

     Output := 0; FreeWorkers := 0; for I := 0 to gHands[fOwner].Units.Count - 1 do if not gHands[fOwner].Units[I].IsDeadOrDying AND (gHands[fOwner].Units[I] is TKMUnitWorker) AND (gHands[fOwner].Units[I].UnitTask = nil) then Inc(FreeWorkers); if FreeWorkers <> 0 then Output := Max(1, FreeWorkers >> 3);

2. TKMayorBalance
   • AfterMissionInit - ware distribution: the AI is without gold powerless + everyone in MP does it

       Code:

     gHands[fOwner].Stats.WareDistribution[wt_coal, ht_Metallurgists] := 5;

   • Append - the array of priorities for a specific house (ht_School, ht_Metallurgists, etc.)
   • UpdateBalanceCore - we don't need Inn at the start of the game when it slows down construction and takes resources

       Code:

     INN_TIME_LIMIT := 7000; // ~12 min InnBalance := HouseCount(ht_Inn) - Byte(gGame.GameTickCount > INN_TIME_LIMIT) * P.Stats.GetCitizensCount / 80;

   • UpdateBalanceMaterials - the adaptive variables StoneNeed and WoodNeed depending on the number of workers. For example:

       Code:

     StoneNeed := gHands[fOwner].Stats.GetUnitQty(ut_Worker) / 1.2;

3. TKMCityPlanner
   • Simple Snap function - a sort of "snap" provides already gAIFields.Influences.Ownership. However, there is not consideration of roads and other houses. The solution is really simple - just add the snap function to Bid criterium.

       Code:

     Price := 0; for I := Low(fHousesSurroundings[aHouse].FirstTile) to High(fHousesSurroundings[aHouse].FirstTile) do begin Y := aLoc.Y + fHousesSurroundings[aHouse].FirstTile[I].Y; X := aLoc.X + fHousesSurroundings[aHouse].FirstTile[I].X; // Snap to no-build areas if [tpBuild] * gTerrain.Land[Y,X].Passability = [] then Price := Price + NO_BUILD_PRICE; // Snap to roads if (([tpWalkRoad] * gTerrain.Land[Y,X].Passability <> []) OR (gTerrain.Land[Y, X].TileLock = tlRoadWork)) then Price := Price + ROAD_PRICE; end;

     where fHousesSurroundings is an array of vectors which will move Loc of the specific building to 1 tile from the house plan.
   • BuildWineFields / BuildFarmFields (moved from Mayor) - don't build fields in the avoidBuilding area: gAIFields.Influences.AvoidBuilding[Y,X] = 0. For WineFields there can be used close surrounding tiles around house - it will not waste space.
   • NextToTrees - I reworked it through findNearest method and implemented with MaxMin cluster merging algorithm which will find a center of cluster with specific maximal distance. Woodcutters can now share a forest. I also added the support of the CuttingPoint. Thanks ZblCoder! We love you (or those who will play future versions of KaM)!
   • NextToOre ......
4. TPathFindingRoad
   • IsWalkableTile - you missed tlRoadWork ... when AI makes multiple plan close to each other in one tick it may cause doubled roads.

       Code:

     Result := (([tpMakeRoads, tpWalkRoad] * gTerrain.Land[aY,aX].Passability <> []) or (gTerrain.Land[aY, aX].TileLock = tlRoadWork)) and (gHands[fOwner].BuildList.FieldworksList.HasField(KMPoint(aX, aY)) in [ft_None, ft_Road]) and not gHands[fOwner].BuildList.HousePlanList.HasPlan(KMPoint(aX, aY));

   • MovementCost - the snap to no-build areas (1 tile from house)

       Code:

     if IsRoad then Result := 0 else if ([tpBuild] * gTerrain.Land[aToY, aToX].Passability = []) then Result := 10 else Result := 30;

5. TPathFindingRoadShortcuts - the snap to houses and no-build areas

     Code:

   if not ([tpBuild] * gTerrain.Land[aToY, aToX].Passability = []) then Inc(Result, 10);

Final improvement

I tested included features in your most favourite only-pro and the best map which was ever made (but seriously I never saw in MP someone who plays with friends against AI except in the CR and special maps so it has its reason + it is not big difference in other maps anyway).

Rules: the same number of workers (20), I did not change weapons demands so the AI produces weapons in booth versions ONLY with 1 weapons workshop and 1 weapon smithy. So the difference between the production is given only by increased speed of building, faster supplying and sort of optimized production.

Old version

New version

Detail of Shared Forest in nobuild array (in the left part of image; in the right top part are chop-only woodcutters)


Another example of shared forest

In protected area:


Old version - soldiers after 60 min

New version - soldiers after 60 min



Criterium of recruited soldiers was counted via script
Old AI: (115+130+110+99+113)/5 = 113.4
New AI: (252+242+204+194+236)/5 = 225.6
The improvement is roughly 98%. There is probably still huge potential ... for example I miss something like Eye / Supervisor class instead of "Blind" searching space for a house plan.

[Rey]

Toxic, great research, as always!

Can you provide PR for that?
It would be easier to track changes and hope @Krom will merge it.

[zombie01]

Amazing man.
Keep improving it

[The Dark Lord]

Awesome. Now the AI is definitely better than the average player.

[Esthlos]

Great job!

Awesome. Now the AI is definitely better than the average player.

... which is why the current AI should be kept around anyway, at least as an option.

(Not everybody is good at KaM, and though I too do crave for a better challenge in single player we still can't demand that casual or beginner players meet too high of a standard to be able to play the game against the AI.)

[The Dark Lord]

Well yes, wouldn't that be great? Difficulty settings? I love difficulty settings.

[Krom]

Great research and improvements!

1. It is unclear what you mean with Output ?

2. Good improvements. I'd just add that Inn is better to be placed near the Store, so some place should be reserved for it ideally.

For testing it's better to use Runner tool - it can simulate many games in a row at fast speed (because no render is used).

[Toxic]

Can you provide PR for that?

Yes, I will send it via Skype. I have only problem with a consistency check in replays (even with current AI) in my version of KaM so don't copy it without check.

Difficulty settings? I love difficulty settings.

Right now it may be represented by EquipRate. However, it is not possible to change it in game menu (only via script Actions.AIEquipRate(...)).

1. It is unclear what you mean with Output ?

In my work we have set of rules which we must follow. For example word Result cannot be in function more than twice - at the begining of the function may be a initial value and at the end must be assignment of a final value. So Output is basicaly result of a function (I did not copy complete functions). You will see it in my code in RMG where for example I don't use standard recursion (it is absolutely forbidden).

I'd just add that Inn is better to be placed near the Store, so some place should be reserved for it ideally.

An inn is not so far (in current version of KaM is also under storehouse). But I think that planing city should be a part of new class.

[Strangelove]

Wow, thats pretty neat! Keep up the good work! Hope the improvements will be merged into the final project! (:

[Lewin]

Nice work Toxic!

I hope we will see these improvements in a new release, along with Rey's improvements and others.

[Toxic]

New combat AI

There are my improvements of combat AI.

First screenshots:

Old combat AI Attack-Closest-Something-Command:




New combat AI:





How it works?

Each group has its own squad class which provides orders (to attack something / move in position). Multiple squads make a platoon which checks the formation and the presence of enemies. Finally, multiple platoons create company which gives global orders (such as: go there, use this road, kill everything in this radius) and plans weighted polygon pathfinding - this provides the performance improvements because there is not need to calculate the pathfinding of all groups in 1 tick (sometimes over the whole map). Groups are moved by small distances because the route is already known and is given by array of polygons. This structure also permits division into different time areas (each platoon could be calculated in following tick).

More examples of weighted polygon pathfinding (2 platoons):


Real map:

[The Dark Lord]

It's great, but implementation would mean that every single mission has be rebalanced.

[Toxic]

It's great, but implementation would mean that every single mission has be rebalanced.

Nope, 1 constant for multiplayer will split this AI and old AI.

[Strangelove]

This is awesome! But i have to agree with TDL. Alot of rebalancing would have to be done to implement that. Maybe mapmakers could enable that with a dynamic script command or something.

EDIT: Too slow i guess :'D

[The Dark Lord]

It's great, but implementation would mean that every single mission has be rebalanced.

Nope, 1 constant for multiplayer will split this AI and old AI.

Then I'm all for it. AI that builds smarter than most humans, and now also fights smarter than most humans. It just keeps getting better.