Kull
Posts: 2625
Joined: 7/3/2007
From: El Paso, TX
Status: offline
|
Before someone says that developing an MWIF AI is "impossible", it might help to review what we actually know. Shannon's 10/1/2010 Monthly Report contained a rather detailed description of what's planned, and the state of the AI at that time:
quote:
Artificial Intelligence (AI)
The AIO decisions are primarily made using scripts written in LAIO (Language for Artificial Intelligence Opponent). This is a rule based language which I created for MWIF. LAIO is fully defined and dozens of test scripts have been written by Peter Skoglund, with help from me.
The test scripts are for setting up units for each of the minor countries in the game, from a single unit for Persia to the more complex setups for Poland, Spain, and Turkey. Peter has also created a script for setting up France in the Global War scenario. These scripts are quite sophisticated, taking into consideration which major power declared war on the minor country, the type and location of enemy units, and possible support from allies. For instance, the script for setting up the single Persian unit has logic for threats from land, air (e.g., paradrops), and sea (e.g., amphibious assaults) from all directions.
To convert the LAIO scripts into actions to be taken by MWIF, (on behalf of the AIO), requires a parser. The parser reads a script and generates a set of commands comparable to what a human player enters using the mouse and keyboard. I’ve written about 80% of the parser code, and debugged that much using the scripts created by Peter. I need to finish the last 20%, but more importantly, I need to have the parser ‘recognize’ ~300 function calls. For example, when a script references a unit’s type, the parser has to ‘fetch’ the unit type datum which is stored internally. There are numerous characteristics of units, unit stacks, hexes, and countries which the program already stores internally. For each of them, LAIO needs a symbol/string defined and the parser needs to translate the symbol, when it occurs in a script, into a function that returns the internal value.
There are 143 decision points in the sequence of play where the AIO needs to decide what to do. 122 of these use universal logic, in that they do not depend on which major power is making the decision (e.g., rail moves, strategic bombing, naval interceptions, placing partisans). For the other 21, the logic does depend on which major power is making the decision. Examples of those are: strategic plans, declarations of war, production plans, and trade agreements. I have 200 pages of text describing strategic plans. Each major power has their own section and the plans are well organized. For the French, I’ve started encoding their strategic plan as data.
The AIO makes decisions using either LAIO scripts (preferred) or by using a routine hard coded in Pascal, but data driven. Which is used depends on the expediency of writing the code. For example, there are a lot of unique decisions that do not deserve spending the time to write a LAIO script. USSR territorial claims, US entry option choices, and routing resources to factories can be handled better by Pascal code than by LAIO code. On the other hand, moving units and deciding about attacks are best done using a LAIO script. That way we can add and remove portions of a script while MWIF is executing and immediately test the effect of the changes. MWIF can parse a revised script “on the fly”, which isn’t possible for Pascal code.
For the 122 ‘universal’ decision points, I start by writing plain text that describes how the decision is to be made. I’ve done 73 of them as plain text so far. The second step is to translate the plain text into a LAIO script. All of that work remains to be done.
Once all 143 decision points have either Pascal code or a LAIO script, the AIO can execute autonomously. In practice, we will introduce the AIO decisions one at a time, evaluating how good each decision is and modifying the script/code until we are happy with it.
From that point forward, progress was reported in almost every month of 2011 (including a nice year-end summary). From 2012 through 2014 there wasn't much activity, but things picked up in 2015 (3 substantial progress reports). Since then, not much has been reported. The key point, however, is that a LOT of work has gone into developing and testing a working AI for MWIF.
Anyway, here's every single monthly AI progress report (the ones with comments):
The update on 2/1/2011:
quote:
Artificial Intelligence (AI)
Peter is anxious to write more scripts and test the ones he has already completed. The latter are for setting up minor country units when they enter the war. I think he has a script for each minor country at this point. There are a lot of small decisions in WIF and I’ve set up the AIO decision making so each one is a separate decision point. The task is to work out the process for how the AIO should make each decision and then write it up as a LAIO (Language for an AI Opponent) script.
Matt should be a great help on this. I find that everyone contributes new insights into what needs to be done for the AIO and how to accomplish it.
From Mitchell:
I studied the AIO language and a few of the scripts. Finishing the LAIO parser should not be too difficult but I have yet to coordinate with Rolf to get started - will do so next.
The update on 3/1/2011:
quote:
Artificial Intelligence (AI)
Peter made excellent progress on the geographic breakdown for the AI Opponent. I revised the documentation on the command structure for the AIO so each element of the geography has a corresponding decision maker. There are 16 Theaters of Operation (TOs) that span the global map. Within each TO there is a breakdown for naval units into Sea Area Groups (which contain individual Sea Areas) and for land units into Areas of Operations (which contain Land Regions). The goal here is to provide a hierarchy of decision makers for strategic and operational decisions and a different decision maker for tactical decisions.
For instance, decisions about convoy routes span multiple sea areas and are made higher up in the chain of command, while decisions concerning a specific naval combat are made by the Fleet Admiral responsible for the sea area in which the combat is taking place. Likewise army reinforcements are shipped off to various TOs, whose commander designates which AO gets them; the AO commander designates a Land Region, whose Commanding General then decides in which hex to place the new unit.
What Peter has achieved is a finished geographic breakdown for Western Europe and the Med. He has almost completed the same for Eastern Europe. Those 3 geographic regions encompass the WIF FE European map.
Rolf and Mitchell plan to work together on completing the parser for LAIO (Language for an Artificial Intelligence Opponent) scripts. Peter has been working diligently on LAIO scripts and deserves seeing them in action, making decisions, ASAP.
The update on 4/1/2011:
quote:
Artificial Intelligence (AI)
I changed the fundamental data structure for the map so it can hold additional information on the geographical breakdown for the AIO. This should have zero effect on game play as far as human players are concerned. The change to the Terrain data adds a new field to each land hex to store the Land Region ID #. Along with this I added a new field to the Sea Area data to store the Sea Area Group ID #. And as the final pieces, I created simple Theater of Operation, Area of Operation, Land Region, and Sea Area Group files which hold the details on each of those elements, including cross references. In practice, this means that the AI Opponent code can trace any land hex back to its LR, AO, and TO, and can trace an all-sea hex back to its sea area, SAG, and TO. The AIO uses this data to ‘understand’ the map.
The greatest advantage that a human player has over the AIO is the ability to literally ‘see’ the map. For the AIO it is just a bunch of incohesive data. Using the newly added geographical data, the AIO can assess the strength of the forces on both sides in a land region and decide whether to attack, maneuver, defend, or retreat. The same applies to AOs, SAGs, and TOs. This is my best attempt to mimic a human player simply looking at the map and making a quick assessment of the relative strengths of the two sides.
In order to validate the new data I added a (debug) line under the Main form that shows and updates the TO, AO, LR, and SAG values as the cursor is scrolled across each hex. Peter is maintaining the data for those files, but Patrice has volunteered to do the hard task: entering a LR ID # for each land hex on the map (~20,000). I got this started by entering the data for Iceland (whoop-de-do!). I did that so I could test that the software found the correct LR name for each hex.
Peter continues to made excellent progress on the geographic breakdown for the AI Opponent with advice from Patrice and myself. To date, he has finished 8 of the 16 TOs: Western Europe, Eastern Europe (up to Siberia), Mediterranean, East Africa, West Africa, Middle East, South Asia (i.e., India), East Asia (i.e. China & Japan), and is working on Southeast Asia. The last includes the South China Sea, the Bismarck Sea, the Solomons, and the Marianas.
Rolf has made some progress on completing the parser for LAIO (Language for an Artificial Intelligence Opponent) scripts. That is slow going, which is understandable. There was a good reason why I stopped working on the parser where I did: the next step was really difficult.
The update on 5/1/2011:
quote:
Artificial Intelligence (AI)
Peter continues to made excellent progress on the geographic breakdown for the AI Opponent with advice from Patrice and myself. To date, he has finished 12 of the 16 TOs: Western Europe, Eastern Europe (up to Siberia), Mediterranean, East Africa, West Africa, Middle East, South Asia (i.e., India), East Asia (i.e. China & Japan), Southeast Asia, Oceania (i.e., Australia), Pacific Ocean, and North Asia (i.e., Siberia). All that remains are two TOs in the Americas and two in the Atlantic Ocean.
I still need to pick up the LAIO parser where Rolf left off. But that won’t happen until I kill off the last of the sequence of play bugs.
The update on 6/1/2011:
quote:
Artificial Intelligence (AI)
Peter is close to finishing the geographic breakdown for the AI Opponent. He has just one left to do: Atlantic South America. I still need to pick up the LAIO parser where Rolf left off. But that won’t happen until I kill off the last of the sequence of play bugs.
The update on 7/1/2011:
quote:
Artificial Intelligence (AI)
Peter finished the geographic breakdown for the AI Opponent. It looks great.
I have asked him to look into the Data Structures necessary for AIO strategic plans. I had already done some preliminary work on that. The goal is to design variables for holding all the information necessary to define a strategic plan for a major power. The 3 main elements are: (1) objectives to hold/take, (2) geographical areas to defend/attack, and (3) time lines for declarations of war/offensives, with accompanying production schedules. Some of the data will define conditions for when something should happen (e.g., when to start building garrison units). Defining data structures for conditionals is always difficult, but Peter and I already did some of that when we were working on setup scripts.
The update on 8/1/2011:
quote:
Artificial Intelligence (AI)
Peter continues to work on the data structures for AIO strategic plans. That is slow going because he keeps coming up with questions for me to answer and I haven’t had enough time to be as responsive as I would like. But some progress is being made. It isn’t easy to take all the amorphous advice provided by the forum members and render it into a rigidly structured outline for processing by a computer program.
The update on 9/1/2011:
quote:
Artificial Intelligence (AI)
Peter continues to work on the data structures for AIO strategic plans. Much of this is coming together. For instance, last week he was grinding out the conditions under which France should surrender. I answer his questions from time to time but the bulk of this work is being done by Peter.
The update on 10/1/2011:
quote:
Artificial Intelligence (AI)
Peter sent me his final list of Areas of Operation and Land Regions. I was able to partially review and modify those. Currently there are 126 AOs and 320 LRs. The Sea Area Groups are now complete and Peter is turning his attention back to Strategic Plans for France.
The update on 12/1/2011:
quote:
Artificial Intelligence (AI)
I finished checking the names for the Areas of Operation and Land Regions so they conform to the ‘standard’ I set up. The major task remaining is to change the data file for the terrain, adding a digit to the end of the row of data for each land hex. There are 70,200 hexes, each of which has its own row of data. Mercifully, the all-sea hexes do not need to be edited (they use the default value).
Final Report for 2011:
quote:
Artificial Intelligence (AI)
Peter finished the geographic breakdown for the AI Opponent. To go with that, I revised the documentation on the AIO command structure so each element of the geography has a corresponding decision maker. There are 16 Theaters of Operation (TOs) that span the global map. Within each TO there is a breakdown for naval units into Sea Area Groups (which contain individual Sea Areas) and for land units into Areas of Operations (which contain Land Regions).
I changed the fundamental map data structure to include information on the geographical breakdown. This should have zero effect on game play as far as human players are concerned. The change to the Terrain data adds a new field to each land hex to store the Land Region ID #. Along with this I added a new field to the Sea Area data to store the Sea Area Group ID #. And as the final pieces, I created simple files listing the Theaters of Operation, Areas of Operation, Land Regions, and Sea Area Groups which hold the details on each of those elements, including cross references. In practice, this means that the AI Opponent code can trace any land hex back to its LR, AO, and TO, and can trace an all-sea hex back to its sea area, SAG, and TO. In order to validate the new data I added a (debug) line under the Main form that shows and updates the TO, AO, LR, and SAG values as the cursor is scrolled across each hex.
The 16 TOs are: Western Europe, Eastern Europe (up to Siberia), Mediterranean, East Africa, West Africa, Middle East, North Asia (i.e., Siberia), South Asia (i.e., India), East Asia (i.e. China & Japan), Southeast Asia, Oceania (i.e., Australia), Pacific Ocean (central), Atlantic North America, Atlantic South America, Pacific North America, and Pacific South America. There are 126 AOs and 320 LRs. The major task remaining is to change the data file for the terrain, adding a digit to the end of the row of data for each land hex. There are 70,200 hexes, each of which has its own row of data. Mercifully, the all-sea hexes do not need to be edited (they use the default value).
The greatest advantage that a human player has over the AIO is the ability to literally ‘see’ the map. For the AIO it is just a bunch of incohesive data. Using the geographical data, the AIO can now assess the strength of the forces on both sides in a land region and decide whether to attack, maneuver, defend, or retreat. The same applies to AOs, SAGs, and TOs. This is my best attempt to mimic a human player simply looking at the map and making a quick assessment of the relative strengths of the two sides.
Another goal here was to provide a hierarchy of decision makers for strategic and operational decisions and a different decision maker for tactical decisions. For instance, decisions about convoy routes span multiple sea areas and are made higher up in the chain of command, while decisions concerning a specific naval combat are made by the Fleet Admiral responsible for the sea area in which the combat is taking place. Likewise army reinforcements are shipped off to various TOs, whose commander designates which AO gets them; the AO commander then designates a Land Region, whose Commanding General decides in which hex to place the new unit.
After completing the geographic breakdown of the entire global map (a massive task which required assessing all 70,200 hexes), Peter worked on the data structures for AIO strategic plans. I had already done some preliminary work on that. The goal is to design variables for holding all the information necessary to define a strategic plan for a major power. The 3 main elements are: (1) objectives to hold/take, (2) geographical areas to defend/attack, and (3) time lines for declarations of war/offensives, with accompanying production schedules.
Some of the strategic plan data defines conditions for when something should happen (e.g., when to start building garrison units). Defining data structures for conditionals is always difficult, but Peter and I already did some of that when we were working on setup scripts. It isn’t easy to take the amorphous advice provided by the forum members and render it into a rigidly structured outline for processing by a computer program. For instance, late in the year he was grinding out the precise conditions under which France should surrender.
Rolf made some progress on completing the parser for LAIO (Language for an Artificial Intelligence Opponent) scripts.
The update on 5/1/2012:
quote:
Artificial Intelligence (AI)
In making changes to support NetPlay I reviewed, and made a couple of changes to, the code determining which major powers are decision makers (I was able to reduce the code from over 1000 lines to 825). The important thing was to enable a player, who currently has no decisions to make, to have full access to the map, units, and various forms to review the status of his position vis-a-vis his opponent.
Another change I made for NetPlay, that has direct bearing on the AI Opponent code, was that I created a separate thread to run some code “in the background”. It is a minor technicality but I am happy to now have a working example of how to code background threads using Delphi. Virtually all the AIO code will execute in separate (i.e., background) threads. The intent is to have the AIO figure out what to do, while its human opponent is moving and clicking the mouse and using the keyboard. When the time comes for the AIO to decide something, it should be able to do so quickly.
The update on 8/1/2013:
quote:
Artificial Intelligence (AI)
Nothing new. But Peter S. is anxious to get back to work on this - as am I.
The update on 9/1/2013:
quote:
Artificial Intelligence (AI)
Nothing substantially new. Peter S. has been working on the strategic plans for Italy and I added a comment or three from time to time.
The update on 1/1/2014:
quote:
AI Opponent
I’m not suppose to be working on this yet but I’ve found a necessary task that is undemanding and serves as a break from debugging. I take 20-40 minutes a day typing in the land region IDs for land hexes. All sea hexes already have their Sea Area IDs which can be used by the AIO when making decisions involving movement and control of all sea hexes. For the land hexes, Peter S. and myself have worked out 321 different land regions. Those are grouped into Areas of Operations, which are grouped in turn into Theater of Operations. But that information has to be communicated to the AIO so it can ‘think’ in terms of “defending western France from invasions”, or “advancing into the Ukraine.” To do that I am editing the TER data file, adding a land region ID to the end of each line of data: one line per hex. So far I’ve completed all of Europe, from Iceland to the Canary Islands, from Karelia to Suez. I’m going to do the USSR next, up to Sverdlovsk, which should be enough for the AIO to ‘play’ Barbarossa. There are a lot of hexes in the USSR and each one of them needs their own little Land Region ID number.
The update on 2/1/2014:
quote:
AI Opponent
This mostly dropped off my radar in January, but I expect to be able to get back to assigning Land Region IDs to Africa in February. One of the reasons I stopped was that I had achieved my first goal: assigning land regions to every hex in the European Theater of Operations, which means the basic data necessary for the AIO to play Barbarossa is in place. Getting the AIO to play both sides of Barbarossa will be the first ‘actual’ game for testing the AIO. Concurrent with that, we will be testing the scripts for setting up units in the other scenarios. There are a lot of scenarios and a lot of major powers, plus all the minor countries, so creating and testing the scripts for simply setting up units is a non-trivial task in coding the AIO.
Oh, as I have mentioned before and should repeat again now, Barbarossa, Guadalcanal, Global War, and Fascist Tide will be the scenarios we will primarily focus on for the AIO. These 4 scenarios are the ones most players want to play, so they sit at the forefront for the AIO to learn to play well.
The update on 2/4/2015:
quote:
AI Opponent
I took a couple of hours to review the Land Regions the AI Opponent will use when playing Barbarossa. The basic design for the AIO dealing with land and naval operations is to divide the world into 16 Theater of Operations (TOs), such as Western Europe, Eastern Europe, Mediterranean, Southeast Asia, etc. Within each TO there are varying number of Areas of Operation (AOs). The picture below shows four of the nine AOs in Eastern Europe: Central Western USSR, Southwestern USSR, Central European USSR, and Southeastern USSR.
Within each AO there are Land Regions. In the picture you can see the dotted lines that define the three land regions in the Southwestern USSR AO: Kiev, Kharkov, and Crimea. For Barbarossa, the AIO will use just the Eastern European TO, with some of its AOs excluded: Sweden, Turkey, and half of the Balkans.
All of the above work was done 2 or 3 years ago, with the vast majority of it done by Peter S.
In January Peter started to work on the formulae the AIO will need to set up the USSR at the start of the Barbarossa scenario. I was only able to spend a couple of hours helping him, but the beta testers have been reviewing and critiquing what he has done so far. The focus is on scrapping units and making decisions about which air units receive pilots (or the equivalent when not using the optional rule). For scrapping, we’ll just have several predefined scrap lists for the AIO to choose from. To assign pilots the process is more sophisticated.
What Peter has been working on is a formula for setting the absolute Combat Value (CV) for air units. Units with a higher CV will be given pilots before those with a lower CV. Obviously, for fighters the air-to-air factor is most important. How to differentiate based on other factors, such as range, is more subjective. But we want the AIO to have one formula for the absolute CV.
When choosing which units to build, the CV will be very important, but divided by the BP cost, so if everything else is equal, the AIO will build a 2 BP fighter before a 3 BP fighter. Similarly, when having to decide which unit to commit to a risky air-to-air combat, the AIO will prefer to send a less expensive unit.
But the relative CV for units is also situationally dependent. At times it will be better to send a more expensive fighter into a naval air engagement simply because it can reach a higher sea area section box. Clearly numerous other factors also influence those decisions.
Once the CV calculations are in place, the AIO will be able to assign pilots for each major power at the start of every scenario. Peter will then start work on deciding which units are assigned to each Land Region and then where those units should be placed within a land region. But that will just be for the USSR in Barbarossa.
The update on 3/5/2015:
quote:
AI Opponent (AIO)
Peter S. has pretty much completed the formulae for setting the absolute Combat Value (CV) for air units. Units with a higher CV will be given pilots before those with a lower CV. Obviously, for fighters the air-to-air factor is most important. How to differentiate based on other factors, such as range, is more subjective. But we want the AIO to have one formula for the absolute CV for each unit in the game.
What he is working on now is the decision making process for choosing in which hexes the USSR units should be placed at the start of the Barbarossa scenario. He wants to have several variation (i.e., strategies) for how the USSR sets up its units. I am more concerned with choosing the best setup possible every time. A good case can be made for both sides.
Another aspect of choosing where to place units is to take into consideration the USSR reserves and reinforcements, especially those that arrive at the beginning of the second turn. Of course that means calculating how many build points will be available for the USSR at the end of the first turn. Following that logic path, the AI Opponent must be able to estimate the number of factories and resources the USSR will hold at the end of the first turn.
I’m not spending more than a couple of hours a month on this - commenting on what Peter is doing and providing some advice. Peter has already written a little script (in LAIO - Language for AI Opponent) for choosing setup hexes for the USSR.
The update on 4/5/2015:
quote:
AI Opponent (AIO)
Peter S. and I worked out good starting locations for the USSR units in Barbarossa. That includes which units to scrap. We’ll probably want to add some variations to the starting setup locations for the USSR, but I really would prefer to have the best setup possible, rather than have the AIO give itself known weaknesses from the very beginning of the game. Because the scenario is only 5 turns long, there are only 4 Production opportunities and the last two have severe limitations of what can be produced, since the game ends so quickly. Peter has written some logic as to what unit types should be built by the USSR based on how well/poorly the Germans are doing in capturing Russian cities. That all looks quite reasonable to me.
The update on 1/4/2016:
quote:
AI Opponent (AIO)
Nothing new in December. However, any changes made for NetPlay also apply to making the AI Opponent operational, since both modes of play require informing human players about moves made by other players.
_____________________________
|
Printable Version
STILL no AI? - 
So not buried and hidden away like some of their other games. 
New Messages
No New Messages
Hot Topic w/ New Messages
Hot Topic w/o New Messages
Locked w/ New Messages
Locked w/o New Messages
Post New Thread