AI decision flowchart

[tlongstretch]

I've created a flowchart that represents an AI player decision tree that I believe will create a decent AI opponent. I'm going to start trying to implement in code.

freeserf_ai_flowchart.pdf
freeserf_ai_flowchart_draft.zip

draw.io link

[tlongstretch]

I forgot to include sending geologists. I think that would be under housekeeping tasks... send a geologist to and areas of mountains where few resource flags placed, few geologists active

[tlongstretch]

I've started implementing this. I realized along the way that my map-searching logic isn't looking in the locations I intend, and it isn't obvious why. To help develop this I am now trying to create a new viewport layer to overlay AI search, similar to the debug overlays triggered by the "g" key. Being able to view the resource gathering and expansion logic in realtime in-game will be helpful for developing an effective AI.

[wdigger]

In fact, AI player acts exactly the same way as a live player, i.e. he moves the cursor (accidentally pokes at the map until he enters his territory if he already has a lock), then he concludes that he can build in this place and is this really needed at the moment. This approach works because AI player does this much more often than alive.

[wdigger]

The code for finding out the possibility of construction is already there, for the evaluation of resources when building a castle is the same. For the construction of a lumberjack, a stonecutter, you can estimate the amount of forest / stone around (I can roughly say how to do it properly using existing possibilities). For the construction of mines need to send geologists and intercept the events of finding the ore.

[wdigger]

I want to finish this release (0.3) and deal with the extraction of a separate entity - a PlayerController that will have several implementations - a local player, an AI player, a network player.

[tlongstretch]

I am trying to use as much of the existing code as possible. Because I have little object-oriented programming experience I am struggling with passing variables around. During my initial testing I put my AI code in the interface.cc and triggered the AI actions from a keypress. The logic I was using for the first phase (building sawmill, 2x lumberjacks, stonecutter, 2x knight huts) is this:

• locate AI player's castle (re-using same logic in existing codebase)
• identify six "corner" points four tiles out from castle - south, southeast, northeast, north, northwest, southwest ( new logic I wrote, I hardcoded offsets from centerpoint for each corner)
• count trees and stones within three tiles of each corner (check each map pos from add_spirally and check for Tree0 though Tree7, Stone0 through Stone7)
• starting from corner with most trees, try to place a sawmill (add_spirally from corner pos until can_build_large is true)
• connect sawmill to castle (copied road building logic from the "double-click to autocomplete road" code. Flag position for a given building is always the same offset from building pos, 6 I think)
• place two lumberjacks near corner with most trees (spiral outward from corner pos until can_build_small is true)
• connect lumberjacks to sawmill
• place a stonecutter near corner with most stones, connect to sawmill (same logic as wood placement, except I'm counting the number of stones per pile to determine the richest area)
• build two soldier huts as far from castle as possible, connect huts to castle (pick two opposite corners and spiral outwards and create a list of MapPos where can_build_small && can_build_military true, then try building at the point farthest from castle

[tlongstretch]

Do you and jonls have knowledge of the actual game code? Or are you trying to reverse engineer it based on how the game plays? I cannot tell how the original game AI works. It seems quite primitive, and the character personalities don't behave much differently.

I would like to see Freeserf be a true copy of the original, and then I would like to create an Enhanced version, perhaps with extra features as options with the original game as the default mode. I am working on the AI first because I play this game often enough that the poor AI is the biggest annoyance.

If you would be so kind, please let me know your plans for AI development. If you have no plans to create any AI I will write one and submit my code as-is. If you plan to re-implement the original game AI I will still write my own alternate AI, and then attempt to implement my logic in the new PlayerCharacter class you describe.

[wdigger]

Please write me directly to wicked_digger@mail.ru for more private info ;)

[wdigger]

I fully share your vision of the game :)

We may go from two sides - to realize your AI and at the same time clarify unclear things with the original code.

[tlongstretch]

Sent direct email

[tlongstretch]

After looking over the code I believe I've found a good place to hook the AI in. When mission.cc's GameObject::instantiate function is called, after each player->init_view I can test the player->is_ai() result and create an AI object for AI players. I have a new AI class that stores the AI logic and some small variables the AI uses to store data, though it is mostly stateless and shouldn't require being written to savegames.

I have the map overlay working so I can put colored dots on spaces that the AI is analyzing. However, I want to slow down the AI so I can watch as it analyzes tiles. Slowing it down is more complex than I initially thought it would be - because the game is single threaded I cannot simply "wait" inside the AI code for some ticks/milliseconds as the whole game would pause. I am thinking perhaps I can move the AI loop call into a thread so it can run at a pace slower than the rest of the game. I am playing with this now.

[tlongstretch]

I got threading to work. I can manually kick off AI action loops that run in background. Now I can change the AI pace without having to constantly hook in to the game update functions. Not sure if I will run into issues with the threads, we will see.

[tlongstretch]

Now that I have the ai overlay and threading working I can debug my AI logic. What prompted me to do this is that positions I thought to be North, South, etc. were clearly not correct. I can now easily fix this. Also, this made me notice that I'm only matching deciduous trees, and not pine trees, when counting loggable trees.

[Pyrdacor]

Hey guys. I ported the game to C# and also started to implement the AI. I use a flexible chain of AI states with an idle state that stays at the base and will trigger other states from time to time. Most important states were to decide to build new buildings and where to build them. I added some search methods to the map to do so easily. Rest of the states deal with linking flags, change player settings, craft specific tools or choosing a good castle location. I am not finished yet but it already works quite okay in the beginning. I also added some values like "aggressivity" or "foodFocus" that depend on the character and I also included the intelligence for decision making and timing. I guess in the end the time-consuming part is testing and fine-tuning. You can find the project here: https://github.com/Pyrdacor/freeserf.net

[tlongstretch]

Very nice, Pyrdacor! I just looked at your AI and AI states code. It looks quite complete, especially with character personalities already implemented. I thought about state-machine design but I wasn't sure if it the states would be straightforward enough. I am starting with a rules-based design because it matches the way I personally play the game, so it is easy to translate my play approach into code.

[tlongstretch]

One thought I was to have the AI fork its own copies of the game and accelerate them to predict the result of various actions, like a chess AI. This is probably very excessive for a game as simple as Serf City, though. I suspect there is really only one optimal strategy.

[Pyrdacor]

I think the main problem for an AI is decision making. This is easy for a human player but very hard for an AI. The decision making in my system is mostly based on map information, game time, personality values and RNG and is not really bound to the state machine approach. The state machine is basically exchangeable and doesn't do really much. The main work is done inside the states and most of the work is only done in a few of them. Beside some special cases (like low supply start) I see the main problem in deciding when and where to build buildings. To allow intelligent decisions there must be enough information about the game (and especially the map). This is the reason why I added some functionality like "find in area around x", "count in area around x" or "get spot near x".

I am not satisfied with my current AI implementation though. If I want to handle a whole game, some AI states will become code monsters as long as I won't find clever conditions that scale well till late game.

[Pyrdacor]

As I looked at your chart I remembered a huge problem I still have with my AI. You wrote "expand borders towards borders". This towards is my problem. To find an area with some properties is easy but when I want to find a spot on the map that is inside that area and in a specific location relation to something else, it becomes a bit complex. If you have a handy algorithm to quickly calculate the "towards" property or some ideas about it, I would be glad if you could share it.

[tlongstretch]

I do not have any such algorithm though I suspect it must be a common enough programming need that one can be found online. My naive approach is to divide the map into chunks maybe 9x9 tiles and calculate the resources inside each chunk, then use the existing path finding code in free serf to plot towards the center of that chunk, then try to build a hut near where the desired path exits the players borders. You would have to modify the pathfinder to avoid masses of tiles where huts cannot be built when plotting a course to a distant target

[tlongstretch]

One challenge will be building efficient roads to transport resources. An annoying limitation I believe exists in the original game and freeserf is that destroying flags/roads in the plotted path of some resource being transported by serfs results in the order being cancelled, which is hugely inefficient and discourages ever destroying roads. It seems to me that an “in-flight” resource’s route should be re-evaluated at every flag but that would change the original game behavior and so I would want it to be an option instead of default.

[Pyrdacor]

I also have some ideas to improve the game that would change the game too much. My plan is to add some kind of mod support and add a first mod which exactly contains these changes. The best roads are indeed not easy to find. I now use the closest flag and repeatly check that everything is linked to a castle or stock. But this does not mean that the transportation routes are efficient. At the moment it works quite well but testing late game AI is a very time-consuming task which I couldn't achieve until today. Yesterday I improved the behavior with minimum starting supplies which was also very bad in original game. I'm quite satisfied. The AI will often succeed in building a food source and a coal and iron mine.

[tlongstretch]

I am realizing that because none of my AI functions require any persistent state I should make my AI class entirely static. I am refactoring it as I keep finding simpler ways to do things, especially re-using existing functions that I didn't realize existed.

For example, flag->can_demolish means flag is disconnected, so I can use that to find disconnected flags. Also the pathfinder calculates road lengths so my "connect disconnected flags" function is very short, it gets all flags, if owned by player and can_demolish then use pathfinder to buld potential roads to all other flags, compare length, pick shortest one. I thought I'd have to write more code for this but it,s all there.

[tlongstretch]

oops didn't mean to close

[Pyrdacor]

I would not recommend to use functions of different purpose for such things. Moreover can_demolish checks things you don't need to check. You should split can_demolish and use only the required part. You can also look at my code. The linking of disconnected flags is already there and similar to your description.

[tlongstretch]

Yeah I just noticed that can_demolish requires there be no connected building (which makes sense) so I'll just write a "is_connected" function that does that part.

[tlongstretch]

I updated the ai overlay to draw pathfinding logic as it builds potential road solutions so I can better understand pathfinding decisions and implement more complex road building.

[tlongstretch]

Is there any function to count the "flag distance" between flag MapPos? All functions related to finding resource targets appear to ultimately use FlagSearch::execute which appears to return the first result that meets the callback criteria (ex flag->accepts_inventory if looking for a place to store resource) but I don't see any way to count the flag distance to use for comparing potential roads. The FlagSearch code is difficult for me to understand but it seems to check all dirs for flags connected to the start flag, and follow each dir repeating this process until one of the flags meets the callback test. I believe I could create a modified FlagSearch::execute that returns the flag distance, but because it is called through a chain of other calls it would require creating alternate copies of those functions also. It is doable but I wonder if there is a simpler way I am missing.

[tlongstretch]

It seems like the flag distance be equal to iterator of the FlagSearch::execute loop. I copied the functions to return that number instead of a bool.

[tlongstretch]

Well with this quarantine I guess it is a good time to get back to Freeserf! I've already done all my yardwork for the spring.

[tlongstretch]

I am refactoring my entire AI code to use queued actions in an attempt to reduce the random crash bugs I suspect are caused by blindly modifying map objects from the AI thread without regard to what is going on in the main game thread. Also, now that I have an okay understanding of how to code in C/C++, I am cleaning up some of the ugliness I created when learning.

EDIT - just discovered mutex, this is probably simpler than using a build queue. Trying it out.

[tlongstretch]

I redid the pathfinding/roadbuilding so that Flags* and "fake Flags*" are no longer needed. It turns out Flag* objects aren't really needed to build roads, just the MapPos of where flags are, and get_flag_at_pos calls to confirm. This might cut down on my crash issues.

Also I implemented "good enough" scoring for roads based on how inefficient they are compared to an ideal perfectly straight road that ignores obstacles. The idea is to check only so many potential roads/flags/files/paths before just using the best acceptable solution so far, rather than checking every possible solution.

Finally, I got the AI threads to properly start/stop automatically when games are launched with non-human player faces - no user action is required. Now you can simply start a game with any number of AI opponents and play, just like in the original Settlers/Serf City. A very rudimentary castle placement search will run and build a castle anywhere that has enough wood, stone, and building sites. Eventually I'll make it smarter, but I was getting sick of having to place the AI castle myself every game while testing.

[tlongstretch]

Things are looking pretty solid. While rewriting all the road building code I fixed a bunch of stuff that may have been responsible for some of the crash bugs. I haven't even implemented the mutex locking yet and it seems to be stable enough to play a game at least.

I'm going to do more testing, with multiple AI threads and some longer running games. If it all looks good I will reach out to @wdigger and @jonls about creating a new branch that has the AI included.

I still need to add attack logic, but the rest of the economy logic is pretty much complete.

[tlongstretch]

Discovered a Freeserf bug/incomplete-feature while testing, created #465

[tlongstretch]

After working around #465, and fixing some stray hardcoded player(1)'s in my AI code, I was able to run multiple AIs. I am now running a game with four AIs and no human player, and it seems to be working just fine.

[datatalking]

This is less of an issue with the code and rather your development process for the Ai decision process, if it is outside the scope of this I am happy to chat via email.

Not knowing all of the Freeserf histories, was there a previous decision tree process established that you adopted and documented or did you develop this process as a whole?

I am building an Ai and this chart answers nearly as many questions as it creates so I wanted to say thank you for sharing this page!

[tlongstretch]

@datatalking, I emailed you

[tlongstretch]

I ended up needing mutex after all, and badly. To try to find all the threading bugs I have been running 4x AIs at maximum speed until it crashes then adding locks around the places where the game or AI iterates over Flags/Serfs/Buildings/Inventories, or any place the AI modifies these objects.

Now I can't get it to crash, but I have mutex spam everywhere. I am going to work on cleaner way to handle locking, might have to modify the core game code. Now that I have a known-stable copy, I can optimize the locking and know that if it becomes unstable again it must be something I changed since then.

[tlongstretch]

I can now consistently get a single AI left alone to produce large amounts of knights and gold when starting from basically nothing. Now I need to refactor yet again to break the one large AI flow loop (mostly represented by that flowchart above) into functions to reduce a lot of early cut & paste while testing.

Then, attacking!

[tlongstretch]

here's the main AI loop breakdown...

do_place_castle();
//do_save_game();
do_clear_reset();
do_locate_military_buildings();
do_get_inventories();
do_get_serfs();
do_debug_building_triggers();

do_promote_serfs_to_knights();
do_connect_disconnected_flags();   // except mines
do_spiderweb_roads();  // road optimization
do_fix_stuck_serfs();  // bug workaround
do_fix_missing_transporters(); // bug workaroudn
do_send_geologists();
do_build_rangers();
do_demolish_unproductive_stonecutters();
do_demolish_unproductive_mines();
do_manage_tool_priorities();
do_manage_mine_food_priorities();
do_balance_sword_shield_priorities();
do_demolish_excess_lumberjacks();

do_attack();  // not implemented yet, just prints offensive capability
do_manage_knight_occupation_levels();

// PLACE MINES EARLY - but do not connect them to roads so they do not actually get built until later
//   this is to secure good placement when resources are found, before the signs fade	
do_place_coal_mines();
do_place_iron_mines();
do_place_gold_mines();

do_build_sawmill_lumberjacks();

// stop here if at least one sawmill and lumberjack are not fully built
//    OR at least until all wood/stone delievered for sawmill and lumberjack fully built
...

// stop here if critically low on planks
...

do_build_stonecutter();

do_create_defensive_buffer();

do_build_toolmaker_steelsmelter(); 

do_build_food_buildings_and_3rd_lumberjack();   // break this up into smaller functions

do_connect_coal_mines();
do_connect_iron_mines();
do_build_steelsmelter();
do_build_blacksmith();

do_build_gold_smelter_and_connect_gold_mines();  // break this up

[tlongstretch]

[tlongstretch]

hah I just discovered why I was getting weird random spots when doing map->pos_add_spirally sometimes... the game uses a pre-generated array for this function and it only has 295 values! I had to add an extended one to check longer distances this way.

EDIT - it turns out to be more complicated than just "extending the array".. there's some math involved in plotting a spiral onto a square grid and I haven't quite figured it out. I'm going to ask a friend who is more educated than me. Worst case I can split the search into smaller hexagonal spirals radiating outward

the question is, how to extend this array, and why does it increase so drastically at the end??
Debug: [map] spiral pattern:
Debug: [map] 0, 0
Debug: [map] 1,0,1,1,0,1,-1,0,-1,-1,0,-1,
Debug: [map] 2,1,1,2,-1,1,-2,-1,-1,-2,1,-1,
Debug: [map] 2,0,2,2,0,2,-2,0,-2,-2,0,-2,
...snip...
Debug: [map] 9,7,2,9,-7,2,-9,-7,-2,-9,7,-2,
Debug: [map] 9,1,8,9,-1,8,-9,-1,-8,-9,1,-8,
Debug: [map] 9,0,9,9,0,9,-9,0,-9,-9,0,-9,
Debug: [map] 16,0,16,16,0,16,-16,0,-16,-16,0,-16,
Debug: [map] 16,8,8,16,-8,8,-16,-8,-8,-16,8,-8,
Debug: [map] 24,0,24,24,0,24,-24,0,-24,-24,0,-24,
Debug: [map] 24,8,16,24,-8,16,-24,-8,-16,-24,8,-16,
Debug: [map] 24,16,8,24,-16,8,-24,-16,-8,-24,16,-8,

SOLUTION - it wasn't as complicated as I thought. I was imagining that the spiral needed to become increasingly round as it grew, but it looks like a plain hexagon spiral is fine. I expanded it to allow up to 24 shells, which seems to be plenty

[Loxodromics]

This looks already very promising! I was curious to try it out and was looking for your code, but as I understand from a previous message, you don't have it publicly in a branch or fork, correct?

[tlongstretch]

I can email it to you if you like. I'm in the middle of a big change to support "multiple economies" basically building warehouses and an entire economy around each one. I can send you the last stable version though.

[Loxodromics]

That would be great, thank you, eMail is in my profile.

[tlongstretch]

I got "multiple economies" working now. That is, once all the necessary buildings are created, the AI will build warehouses far from the castle, and build another whole economy centered around each warehouse. I left a game running at high speed for a couple hours and when I came back the AI had filled the whole map and had hundreds of knights and gold bars.

Now I have to finally add attacking.

[tlongstretch]

I took a break from this for a while to play Jagged Alliance 2. Back to Freeserf AI now. I am trying to catch up to where I was. I'm going to start writing the code to score enemy attack targets now

[tlongstretch]

First AI attack!

Now I'm going to clean up the code and playtest it a bunch.

[tlongstretch]

Ahhh I am so happy. I finally identified and fixed a pathfinding bug that was causing all kinds of annoying problems. That will teach me to mess around with code I don't understand (the iterator heap swap stuff in pathfinder.cc). The pathfinding logic makes my head hurt. The rest of the AI logic is trivial in comparison.

[datatalking]

I’m curious as to your philosophy for the method of analyzing possible attacks to score.

…

Sent from my iPhone

On Aug 14, 2020, at 6:40 PM, tlongstretch ***@***.***> wrote:  I took a break from this for a while to play Jagged Alliance 2. Back to Freeserf AI now. I am trying to catch up to where I was. I'm going to start writing the code to score enemy attack targets now — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[tlongstretch]

It is not well fleshed out, yet. Currently it is scored using the same process used to score potential areas for non-violent expansion by building huts: for a given area count up all of the interesting objects, buildings, tiles and weight them based on current needs. Resources such as trees, stone piles, mountain tiles, mountain tiles with mineral signs, all have their own values. These values are zero'ed out if those resources aren't actually needed, so only remaining needs are valued. So if AI has tons of iron and steel it won't value iron ore signs. When expanding borders the AI's own civilian buildings in the area are valued (they need defense) and any enemy territory is valued (because nearby enemy borders are a threat). When attacking, the enemy's civilian buildings are scored instead of your own, because burning them is valuable.

So, in general, an enemy hut surrounded by mountains, mines, large buildings, and so on will be scored much higher than a bunch of sparse huts near nothing of interest.

Attacks that cut off an enemy's arterial roads, or better yet destroy the roads near their castle are the most crippling. The former is hard to code, but the latter should be quite easy and I intend to add a score for tiles near the enemy castle

I am adding weighting based on attack risk at some point. That is, if the attacking player has a lot of excess knights and high gold-morale it can be more aggressive.

I am still not doing any kind of strategy that looks much beyond the AI player's borders. It is possible, but a lot of work to implement and I'm not convinced it will make a significant difference in the game outcome. Getting really efficient food->mine pipelines seems to be the most important factor, and it relies on having efficient road layout

[JSettler]

Hello tlongstretch!
i'm also interested to playtest your AI, could you publish/upload it somewhere?

[JSettler]

(You could upload it in this SerfCity-dedicated discord: https://discord.gg/m4C9v9DEZK )

[tlongstretch]

I've created a fork that includes the AI and a few other fixes at: https://github.com/tlongstretch/freeserf-with-AI-plus.git

[tlongstretch]

I got freeserf to compile on linux, but when I compile with my AI a bunch of warnings are generated. I'm fixing this stuff now

[tlongstretch]

I got my AI enabled version running on linux now. I had to disable music, but I can figure that out later. Everything else seems to work, at a glance. Now I have to go see if it still compiles on windows since I changed some things to get g++ to compile it.