Heuristic for evaluating the strength of a turn


  • I’ve been thinking in the past few games I’ve played what a good heuristic is to judge the turns I’m taking, my opponent’s turns, the current situation of the game, and evaluating the different options I might have on a particular turn. Potentially this would have large implications for AI; particularly a possible approach for writing an AI to play A&A. I’m actually considering trying to write one that would work with PBEM.

    I’ve come to the realization that income at a given point during the game is not nearly as important as I once thought: Position and net worth of land units on the board are a LOT more important. For instance, in my recent game with DM where I was Axis, our total net worth of land units was very even for a good portion of the game, reflecting the fact that it was a very even game for the first 9 turns or so. However, I really began to lose because of bad positioning on my part, which was followed by the fact that my total net worth of land units began to lag behind. On the other hand, in our next game where I was Allies, my net worth of land units increased above DM’s early on and he was never able to catch up. This has also happened in the two games I have been playing with Switch (well the second game isn’t over yet, but that’s my projection anyway).

    So I’m wondering how effective some function of net worth of land unts plus some smaller function of income would be for a heuristic. Obviously it doesn’t take as much reflection on positioning, but that almost has to be handled seperately. Any thoughts?

  • Moderator

    Cool topic.  Too bad Agent wasn’t still around.

    The total land units work, but sometimes you have to take UK/US/Japan with a bit more caution.

    The game basically revolves aroud Germany and Russia, thus most of the action is in the EE-UKR-Kar area, so the reason I said you need to take UK/US/Jap with caution is simply b/c their supply lines are greater.

    It does the Allies no good if US has 60 IPC worth of newly placed units in EUS if Germany can use 2 tanks to defeat 1 inf defending Moscow.

    So the important army totals are Germany and Russia’s.  You obviously need your Allies but they are really secondary.

    That was all more positional and kinda obvious stuff but I wanted to get it out of the way, b/c I do think it is key when looking at army vs army totals.

    Now, on to some of the numbers.  I’m going to exclude battles with less than like 10-12 units b/c the results don’t really solidify till stacks hit about 14-15 units.

    Oh yeah, all assuming LL.

    So, if you are talking about a 1-1 battle you need to spend in about a 4:3 ratio to take.  And of this ratio, I believe the optimum Inf to Tank ratio is about 2:1.  This is some what intuitive b/c what does a 2:1 ratio give you?  5 hit points almost a guarantee hit in LL, while a 3:1 ratio may seem perfect, I believe it leads to too much overkill.  Perhaps that may be the better option when anticipating counter attacks.  But if we are simply talking what is the “safest” cheapest way to win an attack it is approx~ 4:3 ratio.

    Thus, if you have 20 defending if you need to attack with minimum 10 inf, 10 arm to take, however 15 inf, 7 arm yeild a better result, while 20 inf, 4 arm are not even as effective as the 10-10 attack.  All these attacks cost the attacker 80, while the defender spent 60.

    I’m kinda kicking around the numbers for a 1-2 attack, or a 1-2-3 attack, and obviously you don’t need the 4:3 ratio for the first attacker, BUT the overall battle will cost the entire attacking side much more.  From my initial scribllings here you need at least a 2:1 IPC army adv.  So a 1-2-3 punch on Germany with 30 defending inf, the allies (if 3 equal armies attack) would need 180 worth of attacking units.  The greater the number for attacker 1, the lesser the remaining 2 need to be and the cheaper the overall attack will be to the entire attacking side.

    I think when taking into account income, for each side you need a “correction” factor, for example subtract 30 IPC from the UK/US/Jap army totals just to signify that some newly bought units may not be immediately available.  But that maybe like a step 2 or something.

    I hope this is the kinda stuff you were looking for.  I’m still trying to think of a much easier and concise way of working some of this out, but I wanted to get this down while I have the chance.

    Simply speaking the “attacking side” needs to not only equal the defender in terms of army value but do so significantly just because it is much cheaper to defend.


  • Actually, that’s a bit different from what I was going for, but that’s ok. Your post did give me additional food for thought that adds to my ponderings. What I’m thinking of is a computable function that, given the position of every unit on the board, will output a number which is representative of the balance of the game. This sort of function could be used to create an AI player for A&A because the AI player can try to maximize the value of the function at the end of their turn. This sort of algorithm is frequently used in simpler boardgames, such as chess or checkers.

    So with regard to what you said, I’m thinking that one possible function could be:

    The sum over every land unit K on a side of: The cost of K divided by the number of turns it would take for K to reach the “goal” for that unit. Obviously this entails being able to set at least one goal for each unit in the game, which may not be a bad idea, provided that goals can change.

    The goal for most units would be Berlin or Moscow, however alternate destinations might include Africa or east Asia (the latter in the case of Allied units that are just trying to hinder Japan’s advance). Fighters may have multiple goals: the place they are protecting and the place they need to be attacking range of, in which case we should somehow give extra points for being able to meet both goals. We can also quantify the usefulness of Carriers by what fleet they are protecting, and Battleships for the same purpose as well as what they are in shore bombardment range of. Subs can possibly be added on but I’m not sure they’re worth considering. The thing that would seem the hardest though is island hopping: how to quantify the usefulness of Japan taking AUS/NZE/HAW/MAD.


  • OK, so you are thinking somethign like this:

    Land unit adjacent to enemy capital:  value times 4
    (ARM 2 spaces away with clear path also times 4)

    Land unit 2 spaces away from Capital, no intervening forces:  value times 3
    Air unit within range of enemy capital, no AA:  times 3

    Land unit 3 spaces away but on same land mass:  times 2
    Air unit within range of enemy capital, AA: times 2

    Land unit tranportable to within 2 spaces of enemy capital:  Even

    Land unit not on enemy land mass, and not transportable:  zero

    This of course is a highly simplified mental vomit for offensive evaluation.

    Is this more what you had in mind?  At least in terms of evaluating total-game overview?


  • Designing an AI for Axis and Allies will prove to be extrememly challenging.  The challenge will come from doing exactly what you have been mentioning, such as prioritizing land values (not ipc values).

    Creating an AI and creating a good AI are two completely different things, so start just by making an AI, then see about making a good AI.  Don’t worry about the computer making predictable moves, you can throw in a better decision making process later.

    I would even start with a more simple approach and create a simulator for ONLY Germany vs. Russia (minus naval units).  Keep it simple as possible and work on more complicated approaches later.

    This will turn out to be a large project.


  • I wasn’t necessarily going to go through with it; I think about doing a lot of things and I only do a small portion of them :) But I think it’s interesting to ponder anyway and I figure it may help to improve our game along the way. You’re right that it would be a huge task, but the fact is no decent AI exists for A&A: the one for TripleA is horrible and the one for the CD game is at least as bad.


  • I did not think that Triple A even had an AI…


  • AI’s are typically difficult to make and are often augmented by “cheating” on most computer games.  The computer cheats by increasing unit production or speed or increased stamina or all of the above.  There are very few decent AI’s in the world that are competetive by not cheating.

    Neural Networks seem to be most promising, but the care it takes to program one is considerable.  Deep Blue is an excellent example of an AI (playing chess) however it is only as good as the memory of games played in its history.

    Knowing the computer is a neural network means the human can defeat the computer by presenting it with a scenario that it has not seen before (ideally something wild).  The computer will do a substandard guess at the moves since it has not encountered such a move before and it can be taken advantage of at that point.

    Computers have a long way to go before they can hang with the human mind.


  • If you are looking at writing an AI, and you are considering doing one for TripleA, this post might be interesting

    http://maddlinks.com/triplea/index.php?showtopic=966

    A good hueristic for an AI is a really difficult thing, and I am not even sure that devising one will help with writing an AI.  The branching factory for a game like Axis and Allies is so huge that assigning a number to nodes in a search tree (no matter how carefully pruned) doesnt seem like a good idea.

    I think looking for patterns like dead zones, transport bridges, infantry pushes might be a better option.

    But like Octopus said, I think one of the keys is to just write something that works first, then write something that can beat the original ai, and just keep improving.  Trying to start with a human beating ai from the first revision is a real challenge.

  • Moderator

    I agree with everyone who said start simplier and work from that.

    But I think the Rus-Ger dynamic really gives a pretty look at the overall game.  And for an AI, I don’t think looking at units is the best way to start.  I think LL rules  where an
    “aggressive AI” attacks with a remainder of 2
    “mederate AI” attacks with rem of 3
    “defensive AI” attacks with rem of 4

    Would work for combat purposes.  although that can easily be exploited by a human.

    But that kind of goes out the window without a goal in mind, which mean holding specific territories should be priority 1.
    And for that I suggest re-valuing the key ones, similar to concept IPC value but more pronounced and strategic.

    Here are the key territories and my proposed Values:

    Germany
    Ger - 20
    EE - 12
    Ukr - 6
    WE - 6
    SE - 4
    Fin - 2

    Russia
    Mos - 20
    Kar - 12
    Cauc - 6
    Eve - 2
    Novo - 8
    Kaz - 2

    Thus you get 12 territories for a total of 100 pts.  So a calculation at the end of each rd of who holds the most points could be shown to have the lead.

    Ex, Ger lost WE and Fin but holds SE, Ger, EE, Ukr, Japan took Eve and Kaz But Russia holds Novo, Mos, Cauc so the Axis total would be 46 and the Allies would be 54.  Showing the Allies leading the game.  which I think could hold up since post Japan’s turn Russia still holds Novo.

    A secondary equation tied to this that adds up all units within these key territories and calculates their defensive value and offensive value.  Since form all of these territories you can get to Kar, you could probably calculate how many turns of purchases it would take to:
    (for side that does not own kar)
    1)  be able to attack Kar and take
    2)  be able to attack kar and take and HOLD from a counter.
    (side that does own kar)
    3)  continue to be able to hold kar
    4)  find ter with most enemies units, is an attack or strafe benefical (based on LL attack rules)

    Example, If units are equal at 100 Axis and 100 Allies, but Allies earn 80 and Axis earn 60.  It wouldn’t be to hard to say, well in 10 turns the Allies will 900 pts in unit strength vs. 700.  Perhaps that gives the Allies the needed adv to attack and hold.

    I think the first order should be to set up the inital “rally points” or key territories that MUST be held.  But I do think it would be easy for a human to exploit.

    The real adv for the AI would be it could calculate it’s army strength much further down the road provided it was set right.  Which I admit would be very hard.  But I think if you work with some initial parameters you might be able to do a pretty good job.  I’m thinking if you assume all other territories except the initial 12 I laid out are “bonus”, you could then have the AI “assume” it’s income for 5, 6, 7 turns based on the LL playing style you give it.  Yet when their turn actually comes around they maybe able to buy some thing more b/c they hold half of Afr as well.  But for your initial Calcs you don’t really need to take all that stuff into account.  I think Less would be more in this case and would actual build a strong AI.

    I’m just thinking of how I play now and I treat everything but those 12 ter as secondary, and it works for me, Infact I even treat half of those 12 as secondary.  Position I think would be a greater asset for a strong AI, not IPCs or even army strengh (if it is out of position).

Suggested Topics

  • 10
  • 37
  • 21
  • 3
  • 7
  • 10
  • 28
  • 6
Axis & Allies Boardgaming Custom Painted Miniatures

38

Online

17.0k

Users

39.3k

Topics

1.7m

Posts