Battle of attrition?

1.  “Appropriate” and “Gargantua” cannot properly be used in the same sentence.  It’s like a double negative.  “Appropriate” and “Bunnies” you may draw your own conclusions on.

2.  Gargantua seems to know what he/she/it is talking about.  The same is true of many amateur therapists and cooks.  “You don’t need pasteurized eggs!” was advice I received just yesterday, at some length.   :roll:  The lesson is, always beware!  You can’t trust in anyone.  Especially people that say “trust me”.  You can trust me on this.   :wink:

3.  This passive snowball thing generally does not work.  Imagine you are playing Starcraft, and that you have decent micro and your opponent has no micro.  Then yeah, you scout a bit, expand a bit, and you eventually just passive snowball right over your opponent.  Now imagine you are playing Starcraft, and your opponent has better micro than you.  You better have something more than a snowball, or you’ll have a snowball’s chance in h-e- double hockey sticks.

4.  Axis start with more power in the right places than Allies do.  Say you’re playing Starcraft with two allies (total three), and each of you has a normal base startup.  Now say you have only two opponents, but they start with normal base setups plus 20 Marines each.  Now yeah, if you’re against a passive computer AI, the Marines won’t attack you until you invade your opponents’ bases.  But if you’re up against HUMAN players (that don’t suck)?  Hooo ya.

Playing for the money is pretty much the best ‘general strategy’, how you accomplish this is via tactics.   The draw back is that without experience you might not know that you might be winning the battle of attrition but losing the war because of positioning.   For instance, you are winning the war of land attrition battles as the allies because the axis is setting up your atlantic navy for destruction.  You then find yourself doing a turn and realizing in 1 round your navy is toast and there is nothing your successful land battles can do to stop it.

But in general, if you can win the sum of the earnings delta and the attrition delta you are heading in the right direction.

I would add that computer AI is difficult.  I should say, good computer AI is difficult.  The problem is that computers are really really stupid.  They are good at working towards a goal, but that goal is defined by us.  For chess, how does the computer know what is a good board state and bad?  You can add up all the pieces as a measure of ‘fitness’.  If I have all my chess pieces and you have only the king and queen, in general I am in a better position.  Unless of course you have me in checkmate on your move.  I won every battle of attrition in every case because I lost no pieces, yet I lost.  It is very difficult or impossible to pass in two board configurations to a program and have it determine exactly which one is better.  The programmer assigns goals like “win the battle of attrition” and the program it will happily do that every turn until it loses because it was ‘winning’ according to the rules we gave it.

how does the computer know what is a good board state and bad

Ok so I’m not an expert, and I’ve only taken a course or two in programming.  But I HAVE played against computerized chess opponents on a number of occassions and from what I can tell it’s like this…

The longer you allow the computer to calculate the best move, the better that move will be.

Now a chess board is DIFFERENT than an Axis and Allies map, in many ways,  but the same several others.

THE CALCULATION to determine GOOD BOARD STATE / VS BAD seemed to be on a point system, for chess it looks like this:
-what pieces does my piece threaten?
-how many spaces can I move?
-How many squares of the board do I control
-How many squares are around me?
-How many pieces threaten my square?
-How much support do I have for my square, and what is the point value of my units if I trade this square with several units of my opponents
-Do I expose any of my other pieces or my king to attack?

Basically the computer puts values, on ALL that information…  add’s up all the points, and suddenly the most EFFECTIVE scoring location, is now the BEST move.  Kind of like Scrabble, if you had a computer that could decipher for you all of the POSSIBLE word combinations, and applicable locations to place them on the board, it would only be vetted by how long you let it calculate.

I have no idea how TripleA computerized opponents are coded, but if they switched to this kind of system… it might improve them?  No idea.

All that said… the AI willing to gamble factor could be difficult to code in.

I’m actually taking a machine learning course now to finish of my degree.  All those factors are no doubt part of a chess playing program.  The ‘art’ of the system is to assign weights to each of the determining factors in order to come up with your measure of fitness.  How do you know your weights are right, by playing to the end and seeing if you win or not.  The problem is that those inputs often don’t totally capture ‘the game’, its a rough approximation of the game.

Longer time means a deeper search but the number of ‘game states’ grows exponentially.  With chess on average say there are 16 possible moves.  Looking ahead 1 set of moves, mine then yours means 256 game states to evaluate, 2 moves is 65, 536.  4 moves is 4 billion game states, 8 moves ahead is 16 million trillion game states.

I’ve talked to the folks at tripleA quickly about their AI.  It would make a heck of a masters thesis project I think, a bit more effort than I am willing to give it!

Gambling is easy.  It’s the multi-player long term outlook that is the trick.  Alternating between black and white in chess is one thing, 7 players on 2 teams alternating and co-operating is hard to capture.

Maybe that’s the problem.  Maybe they have been coding “theoretical moves” as independant nations.

Perhaps if the outlook was change to look at the game as just.  AXIS,  ALLIES.  Black and White.  The coding would be easier?

Just imagine the simplicity.  These are all your units, facilities, etc,  and at different stages, you can move different parts of YOUR pieces,  suddenly the computer isn’t thinking of them as a seperate entity, and will make efforts to do things like hold territories, or protect valueable pieces with other ones during other turn phases, based on how it is strategically coded to play - which is the balance of the point system I discussed, linked to a player design plan of HOW to achieve to victory.

Worth a thought?

But billions of hours could be spent coding that AI, and it may still only resonate as mediocre.

Who is most responsible for AI coding anyways?  I would LOVE to help with the theory… if I could be helpful.

What Malachi said.
A&A is a lot like chess.  You may be working hard on the material advantage, and often this will win it for you (in chess you can often win by being just 1 point ahead) but that does not ensure your victory.  For while you are continuing to take turns, and are relishing your material advantage, you may find your opponent increasingly willing to take risks to catch up.
Key difference between chess and A&A - dice.
As in chess, you move from novice to intermediate quickly merely by seeing all immediate possible moves (threats) your opponent can put on you.  In chess, this is when you stop leaving open unprotected pieces for your opponent to pick off.
A&A AI is so much harder than chess to program effectively.  Beating A&A AI is like beating level 1 or 2 on chess AI on a scale of 1-10.
Unlike chess, you need to play human opponents to improve significantly at A&A.  Just playing against yourself (sounds like you are playing on TripleA, so this is not necessary) is a big improvement over playing pathetic AI.

@Gargantua:  Say you’re on a diet.  So you take five regular boxes of donuts, remove the donuts, then you put the donuts into two large boxes.  So far, you’re great.  Because all the donuts are still in boxes, see?   :roll:

But if you do end up eating all the donuts, it won’t matter if they started out in five boxes or two boxes.

Programming for Axis and Allies is like that.

@Gamerman01:  A&A is a lot like chess, in much the same way that a football is like a hamster.  Although both fun to kick and squeak a bit when they are hit, there are differences.  For example, hamsters can be made into effective infiltration type zombies, while footballs cannot be made into zombies at all, as footballs lack an anima to begin with.

These are subtle points, I know.  But important.

I disagree that A&A would be harder to program than chess.  Put in a book of openings, midgames, closings, and conditions for when to shift, plus some build constricts so later play isn’t hampered by early poor builds.  Because of the dice factor, the game conditions cannot be calculated to a high degree of precision in advance, so it’s not as if you need to calculate sixteen turns in advance.  On the other hand, in chess, there are no dice, so moves must be calculated 50 or even 500 moves in advance (the last, see http://en.wikipedia.org/wiki/Chess_endgame#Longest_forced_win).

Now if you wanted to program an A&A AI based on a chess algorithm, that WOULD be pretty f***ed up difficult yeah.

Discussion about chess v. A&A AI has already been discussed at length, elsewhere.  Like you, I thought A&A AI would be easier, but after reading all the arguments, I changed my mind.  For starters, there are waaaay more immediate possibilities in A&A than in chess.  Never mind the whole looking ahead 3 moves part….

Anyway, there’s a reason A&A AI sucks, and it’s not just because fewer programming man-hours have been put into it.

I stand by my chess and A&A comparison.  I have played thousands of games of chess in the past few years, and I’ve played about 200 A&A games.  There are a lot of similarities, and many of the analogies are relevant and worth discussing.

I’d love to read the chess Vs A&A AI threads.  I am rather intrigued about this, so much that I have already mentioned this to my machine learning professor.  But it is not a trivial matter.  More possibilities is actually not a problem at all, it’s just a matter of zeros.    If real AI was just a matter of zeros, we would have sentient computers, they would just think slowly.  In fact, there is no difference in computer power between the first programmable computer at Bletchley Park in 1944 and the fastest supercomputer now, well, the ONLY difference is in the number of zeros after any measure of performance.

Bunnies……When you talk about opening moves, you are ‘hand coding’ specific solutions for specific problems.  There is no generalization which is the holy grail.   Once you can provide for a general solution ie some ‘metric’ for a given ‘game state’ then and only then do you enhance this with specific opening move sequences.

The AI thread with Veqryn
http://www.axisandallies.org/forums/index.php?topic=26221.15

Discussion about chess v. A&A AI has already been discussed at length, elsewhere.

Let every eye negotiate for itself
And trust no agent; for beauty is a witch
Against whose charms faith melteth in blood.

Much Ado About Nothing (II, i, 178-180)

Like you, I thought A&A AI would be easier, but after reading all the arguments, I changed my mind.

You weak minded fool!  He’s using an old Jedi mind trick! - Jabba the Hutt, “The Empire Strikes Back”

I have played thousands of games of chess in the past few years, and I’ve played about 200 A&A games.

If eating M&Ms made me an expert on making them, I would be the mother of all M&Ms.  Or the father, as it were.

There are a lot of similarities, and many of the analogies are relevant and worth discussing.

(Bunnies adjusts soapbox stands on it, and opens a notebook titled “Lecture on Programming”)

Let us suppose you are in a room with a tile floor.  Any given tile may or may not be trapped to fire a steel dart at anything that touches it.  Let us now also suppose that you have a cute furry hamster and a small supply of hallucinogenic drugs.

Now, there are different approaches to programming.

Most people would say “The h*** with this”, leave the room, and go off somewhere nice to use up the supply of hallucinogenic drugs.  This explains the great surge in economics majors in recent years.

Of those that remain -

Those that understand how funding committees work know that it isn’t necessarily actual progress that funds research.  What is required is the perception that work is being done.  So clever budding programmers pump the hamster they have with drugs, and let it loose on the floor.  If the hamster is shot, success!  A trap has been detected!  If the hamster lives, success!  A safe square has been detected!  Of course, with the hamster staggering around, in time, the hamster will almost certainly be shot, but it is a staggering success all the same!  With success comes approval for further funding, which leads to further hamsters and hallucinogens, which feed more test results, which feed more funding, etc. etc.  Then comes the inevitable funneling of hamsters and hallucinogens into black market pet stores and pharmaceutical companies, the reaping of profits, the bribes, the intern set up to take the fall, the convenient accident the intern has before being able to testify in court, the trophy wife, the hot intern with whom an affair is messily covered up, and finally retirement from a happy life of programming, pet stores, and pharmaceuticals, into a respectable life of academia and executive board membership in which no one questions or blinks an eye at twenty thousand dollar “consultation fees”.

Which explains rather a lot about how programming is funded.  But how does programming work in theory?  How do you make it all sound so very impressive to the bright eyed hard bodied young girl or guy who tells you “programming is soooo interesting, why don’t you tell me more about it?”  (For such students, I recommend the Barry White “Can’t Get Enough Of Your Programming Baby” album.  Worked for me seventeen times, until the headboard on my bed broke off and hit the record player.)

Programming, chess programming.  Throw a million hallucinogenic hamsters on a trapped floor, and see which ones survive.  The survivors are picked up and thrown into another trapped room, then another, then another.  Finally, only a couple of dazed and terrified hamsters are left, which we call “Viable Options”.  What is the programming part?  Making sure there is one hallucinating hamster for each tile in each room.  Tracking each hamster.  The ability to tell which hamsters are dead, which are alive, and which are merely passed out / faking dead / apathetic.

There are other methods to programming.

Some programmers attempt to engineer the hallucinogens so they no longer induce random behavior in the hamster.  Instead, exposure to the hallucinogen causes a hamster to act predictably - say after a hamster lands, it always walks straight due north.  Since the point the hamster is dropped is known, and since its path is known, any tile between the tile the hamster was dropped on and that the hamster ended up on (or met its end on) is safe.  With such hallucinogens, there no longer need be a hamster for each tile, so fewer hamsters are needed overall.  Thanks to advances in virtual hamster cloning technology, though, it has been pointed out that developing advanced hallucinogens is far more expensive and time consuming than merely whipping up a batch of a couple billion hamsters.

Some programmers attempt to engineer hamsters.  Daring hamsters with fedoras and whips that can detect traps safely. Such programmers are almost inevitably sneered at by funding committees that demand to know when the hamster is going to get up off its a** and make them a sandwich.  Frustrated programmers that fail to obtain funding often go on to have successful careers writing scripts for movies such as “Indiana Jones and the Temple of Doom”, “Terminator”, and “Planet of the Apes”.

–

As far as comparing and contrasting chess AI and Axis and Allies AI -

There are SOME similarities.  But NOT so much so that you could easily apply one to the other.

First, I would say - is Axis and Allies different from chess?  I think so.  Demonstrably very much so.  No “light tweak” would allow Fritz or Chessmaster to play Axis and Allies with any degree of real “skill”.  Nor would a heavy tweak do.  In fact, I am very much persuaded that nothing short of two cases of Jack Daniels would do the trick.

Second, consider funding.  Funding is proportional to perceived marketability.  Chess is much, much more marketable than Axis and Allies.  Chess is the bucket of funding, Axis and Allies the drop of water.

True, programming techniques applicable to Axis and Allies and not to chess could be developed and sold were Axis and Allies AI to be developed.  But specific programming techniques could just as easily be developed for other projects entirely - other higher-profitability projects, that is.

So what we have so far is - Axis and Allies AI will require significant unique development, and that funding and resources for such development will be very limited.

That means A&A AI must deliberately be developed to be simple.  More complex than is currently available in TripleA, but still very simple.  A programming environment will not be created for the purpose of Axis and Allies programming.  With calculation abilities limited to piggybacking on existing program shells, the program will not have the resources, and therefore should not be written, to encompass all possibilities from each point, because calculation times will be too long.

So the best direction for Axis and Allies AI, considering the real-world resource limitation, is the writing of a framework through which the AI can efficiently execute several different predefined strategy scripts.  With a limited (although still quite wide) number of variables to check, the program can evaluate conditions and select an appropriate stage of an appropriate strategy, and execute a move in a reasonable amount of time.  This should give the Axis and Allies AI reasonable efficiency, but should not be anywhere near as difficult as scratch-building an effective chess AI.

To put it in hallucinogenic hamster terms - instead of throwing mass hamsters (calculation power), re-engineering hallucinogens (complex AI scripts), or re-engineering hamsters (giving an AI the ability to understand the concepts behind the game and the ability to derive principles therefrom), we are instead throwing down a lot of sets of unconnected colored tubes (setting predefined strategy sets that transpose into one another).  All hamsters start in a tube (the opening position for each power can be predicted, although there are many possibilities so many tubes are needed.  From that opening position, the game can be steered along certain “safe” paths).  A certain minimal amount of hamster and hallucinogen engineering is needed to get the hamsters to jump from one tube to another (although much less than if there were no tubes).  There is always a danger that a hamster may wander out of a tube where it will quickly die, but given our limit on hamsters and limited engineering capability, that can’t be helped.

–

As far as Axis and Allies inherently being harder to program than chess -

Even in the 1950s there existed a literature of tens of thousands of good, solid books on chess.  Programmers did not have to figure out how to use rook and king to checkmate a king.  It was in the literature.  They did not have to figure out how to use bishop and knight and king to checkmate a king.  It was in the literature.  They did not have to figure out the deviations fourteen steps deep into a Sicilian Dragon, and how to exploit significant deviations from the line.  It was in the literature.

To my knowledge, Axis and Allies has nothing like that.  Oh, there’s a bit here and a bit there, but it’s mostly fundamentals conceptually equivalent to knowledge of pinning, or the first three moves of the Spanish/Ruy Lopez.  There is nothing THERE.

So in practical terms there is groundwork to be laid, and I think (among other factors) that is one of the major contributing factors to why the competitiveness of Axis and Allies AI does not compare to the competitiveness of chess AI.

But is Axis and Allies inherently harder to program?

First, check conditions (ABCDEFGHIJKLMNOP).  Second, set strategy (X) based on checked conditions.  Use tactical database to evaluate best use of available resources.  Execute.

That’s all there is.

I’ve heard people say that
Too much of anything is not good for you, baby
Oh no
But I don’t know about that
There’s many times that we’ve programmed
We’ve shared programs and made programs
It doesn’t seem to me like it’s enough
There’s just not enough of it
There’s just not enough
Oh oh, babe

There are lots of existing metrics for chess board states.  It’s actually not hard to write a chess playing program, it was a class assignment for a 3rd year course in AI which was a prerequisite for the course I am taking.  Of course I took that course 15 years ago, no chess assignment in that class.  Decision trees were used.

What intrigues me is not hand coding a strategy that is moderately effective but always makes the same ‘mistakes’.  I am intrigued with an actual machine learning system whereby it ‘learns’ how to play and perhaps uncovers hidden strategies.  Such a system would be a benefit to play testing new games and changes to existing games.

TripleA already has a way to dump game histories to an output.  It would be cool if a system could parse this file to see games played and ‘learn’ from them.  A combination of data mining and playing millions of games against itself could provide for an effective AI opponent.

It’s such a nebulous problem it would be hard to determine how much effort would be required.  Easy <problem<infinity.<br>Computational complexity can be addressed with distributed computing.  More users using it should mean a better AI, something like a SETI@home system would be da bomb!</problem<infinity.<br>

Say you’re on a diet.  So you take five regular boxes of donuts, remove the donuts, then you put the donuts into two large boxes.  So far, you’re great.  Because all the donuts are still in boxes, see?

But if you do end up eating all the donuts, it won’t matter if they started out in five boxes or two boxes.

Two boxes are easier to carry, than five.

@MrMalachiCrunch:

Bunnies……There is no . . . holy grail.

http://www.youtube.com/watch?v=XcxKIJTb3Hg

Once you can provide for a general solution ie some ‘metric’ for a given ‘game state’ then and only then do you enhance this with specific opening move sequences.

That is, if I understand you correctly, you are saying the program should be able to look at a board and figure out what to do in a general sense.  Only after the program has this general sense can it be effectively refined to carry out specific strategies.

What I am saying, though, is that the program does NOT require the ability to look at a board and figure out what to do in a general sense.  I am not thinking about actual intelligence, only a reasonable facsimile.  That is, functionally Weizenbaum’s ELIZA approach.  Instead of programming a computer that first understands how to speak, then training it to speak as a Rogerian psychotherapist, simply program the computer to speak similarly to a Rogerian psychotherapist in the first place.

–

So before I posted the above, I found two new replies had been posted.

What intrigues me is not hand coding a strategy that is moderately effective but always makes the same ‘mistakes’.  I am intrigued with an actual machine learning system whereby it ‘learns’ how to play and perhaps uncovers hidden strategies.  Such a system would be a benefit to play testing new games and changes to existing games.

I say whether it intrigues you or not is not the question.  The question is what is the best use of available resources?  If I am correct that resources are extremely limited, then programming will have to be done in the limited fashion that I describe, precluding a general revolution in the state of AI development.

@Gargantua:

Two boxes are easier to carry, than five.

Yes, but would you rather have five boxes of donuts or two boxes of donuts?

It’s just a harmless little bunny….

Whether it intrigues me or not certainly is the question from my perspective if I am to do the project.  Machine learning is my interest, a non-learning game playing algorithm is what is required most likely.

‘General Solutions’ to specific problems should always be the primary objective so your solution can be  re-used in other applications.  It’s not always feasible of course.  Then ‘domain specific’ information can then be added to enhance choices made.  It’s machine learning 101.  You are absolutely correct in that a simpler solution might just work fine.  A game playing algorithm can be simple and effective without ever being able to learn, that is what currently exists.  Before I shoot my mouth off too much, I would need to invest time to see how the existing wheel works before I think too deeply about re-inventing it, assuming I am even capable and able to spend the effort both of which are questionable.

@Bunnies, maybe the programmer is a pervert and if you give him some hallucinogens and a hamster… there’s only one place he’s gonna put him, and it ain’t on any tile.

And I’d rather have a box of donut holes. They’ll be lighter.