Does it seem possible to train Civ4 AI with machine learning? I know StarCraft2 does it and IIRC FreeCiv too.
Going by
https://pythonprogramming.net/starcraft-ii-ai-python-sc2-tutorial/, what you'd do is create an environment in python that makes it easy to write an AI. A learning environment. Python 3 I would hope. It would probably be a headless engine exposing some way to control the human player. You'd then write a rule-based AI. Then, replace the decisions with something like deep reinforcement learning, neural networks, CNNs...
Importantly, if you do Machine Learning, you'll want a FAST engine. But on the plus side, you don't need to care about multithreading as you'd just run N games in parallel.
It may also be possible to use MILPs to solve for truly optimal play of some subset of mechanics. Like, maximise the amount of research you can get from an isolated start (don't need to handle AI). But MILP solvers aren't quite there yet. The HiGHS solver is pretty good, but it's single-threaded at the moment. They should be adding parallel solving soon, and that's when it should get really good. Now, if you were really creative, you might be able to craft a custom branch-and-bound algorithm that also minimises the redundant symmetric states. One would hope that would be even faster, in theory, but it's tough to beat MILP solvers. There's also other tactics like decomposing the problem into N-turn blocks, but I wasn't able to make that fast.
Nif Tools perhaps? I can't speak to anything related to editing them, but from other games running the same engine, this seems to be the standard tools to edit them. But that's just my impression from an evening's googling.
Yes, loading NIFs is a solved problem. Should be easy as pie.
Anyway. An actual progress this time. A milestone. Path verification is working, or at least appears to work. Turn 209 of a 1040x640 map:
Code:
FAStar for Barbarian Worker start=[286, 150] goal=[669, 155] result=1 flags=0 numUnits=1 domain=2 1687ms
Generating path 1486 from { [286, 150] with Barbarian Worker } to { [669, 155] } with maxTurns 2147483647
Vectorised path finder took 808.243ms
Path cost matches.
CmdCiv4 log Info void __cdecl MyCvDLLEngineIFace::AutoSave(bool):
Pathfinder reset.
FAStar for Fluffy Warrior start=[690, 69] goal=[690, 68] result=1 flags=4 numUnits=1 domain=2 4.1201ms
Pathfinder reset.
Performed 6 game updates in 45.8825s.
That is full verification. Checks the path cost of the final path, and checks pathCost+pathValid for each step in A*. That's why the vectorised pathfinder is so slow here.
There's still a chance though that there's some higher level bug somewhere causing different paths to be requested. But the way this works is that
all unit pathing requests are passed to an internal FAStar instance if verification is enabled or my pathfinder won't handle it yet. So that's at least minimising the chance of such bugs.
Turning off step verification:
Code:
FAStar for Barbarian Worker start=[285, 149] goal=[669, 155] result=1 flags=0 numUnits=1 domain=2 1587.21ms
Generating path 1485 from { [285, 149] with Barbarian Worker } to { [669, 155] } with maxTurns 2147483647
Vectorised path finder took 5.2291ms
Path cost matches.
Pathfinder reset.
FAStar for Barbarian Worker start=[286, 150] goal=[669, 155] result=1 flags=0 numUnits=1 domain=2 1566.69ms
Generating path 1486 from { [286, 150] with Barbarian Worker } to { [669, 155] } with maxTurns 2147483647
Vectorised path finder took 5.402ms
Path cost matches.
CmdCiv4 log Info void __cdecl MyCvDLLEngineIFace::AutoSave(bool):
Pathfinder reset.
FAStar for Fluffy Warrior start=[690, 69] goal=[690, 68] result=1 flags=4 numUnits=1 domain=2 4.1857ms
Pathfinder reset.
Performed 6 game updates in 37.9029s.
Here's a long path, which goes across the map:
Code:
Pathfinder reset.
FAStar for Barbarian Warrior start=[921, 270] goal=[350, 194] result=1 flags=0 numUnits=1 domain=2 471.223ms
Generating path 1254 from { [921, 270] with Barbarian Warrior } to { [350, 194] city of Carib with Barbarian Warrior } with maxTurns 1
Vectorised path finder took 0.0026ms
FAStar for Barbarian Warrior start=[921, 270] goal=[261, 199] result=1 flags=0 numUnits=1 domain=2 102.758ms
Generating path 1255 from { [921, 270] with Barbarian Warrior } to { [261, 199] city of Tiwanaku with Huayna Capac Archer } with maxTurns 2147483647
Vectorised path finder took 25.4883ms
Path cost matches.
So, 26ms for the longest path. It's okay. Alright. Not as fast as I would like. But I could make it faster if I wanted to by using Block A* without an LDDB, which is actually feasible, but the internal data layout is more complex.
Turn time is ~2.8s with no verification. With 4K barbs running around. Five workers. Some of them are probably building intercontinental barbarian highways.
Current restrictions: Land units only, no unit stacks, AI only.
Landmark locations are computed at startup in ~180ms. This could be done in the background. Landmark distance (cost) fields are computed on-demand, in a background task.
There is a landmark heuristic instance for each "movement type". Combination of: unit MP, movement promotions, team route cost changes.
And a landmark heuristic is optional. It can be computed in parallel, and when it isn't available yet, the pathfinder can just use no heuristic.
The downside of parallel landmark updates is the possibility of non-deterministic pathfinding. This is unlikely as the pathfinder does not use "parent pointers", and only relies on a distance field for path reconstruction, but could still happen if through some fluke of pathing, a plot gets the same path cost with a different number of movement points. This could probably be mitigated by taking the minimum movement points for equal path costs within the pathfinder, or by making landmark updates deterministic.
The heuristic can also be updated by local changes. If a plot changes, you can compute the maximum path cost reduction going through that plot, and subtract it from the heuristic. And I hope that's correct! Then you can have some threshold where you launch another landmark distance field computation task. So in the end, maintaining the landmark distance field has little cost.
Also, to feed the vectorised pathfinder, everything that affects pathCost and pathValid is complied into a per-team bitmap, which is masked by the unit and pathing flags. Thus, calculating pathValid is just a few SIMD instructions, in comparison to the expensive 9x9 loop inside
AI_getPlotDanger. So that means there's also a cache for plot danger. It has a lot of dependencies on various pieces of game state, but it's handleable.
Now, I need to ensure that all the caches get all the game state change events they need, and test with verification on a more typically sized map.
*Ah, yes, use AI autoplay! Capital idea.
*Oh. Turn 46 of a more typical map: A* costs inconsistency. Parent gets improved cost, but because of unit movement points, the adjacent plot gets a worse cost. So even the path costs depend on visit order. And that's why, I guess, FAStar will update descendants of a node, and why
https://github.com/karadoc/Civ4-K-M...5d86608/CvGameCoreDLL/KmodPathFinder.cpp#L451 exists. This makes costs depend on visit order, and thus the heuristic, and so hurts determinism and path verification. The True solution is 3D path coords, but that would be silly for performance. Or change the step cost function.
*Changed path cost verification to only abort if final unit turn/movement points is different.
*Found value cache verification + path verification for a 64x40 map successful. Turn 11 to turn 458 using AI autoplay, debug build, took half an hour.
The found value cache is the other piece of complex machinery. Very bug-prone. I would like to replace the found value cache with another highly optimised cache-friendly SIMD implementation, but I'm not sure if it would be fast. And there's a couple of divisions that SIMD can't do natively. Would be nice if the whole-map loop in
AI_updateFoundValues could be done in 1ms per player assuming all your locally updateable values are up to date.
*1040x640 map from turn 209 to turn 243 verified. Very slow!
