following perfect strategies can often lead you into traps when you're playing against human pros.

yeah i meant optimal strategy, a perfect strategy would be the best strategy to adopt knowing all opponent moves, so it isn't really relevant. My point was that the so called "proof" that warlight is unsolvable isn't a proof at all

following perfect strategies can often lead you into traps when you're playing against human pros

this is a non-sens, and you assume that we know the optimal strategy for warlight, wich is far from being the case.

well, there are some common sense formulas atleast. but inevitably it depends on being able to predict the opponents moves on crucial points.

the only thing right about this is that there is no perfect moves. however there is a perfect strategy in theory, wich would consist of mixed & balanced moves. For example, for a given starting map, the perfect strategy could be something like:
-using 50% of the time the "set of picks A"
-using 30% of the time the "set of picks B"
-using 20% of the time the "set of picks C"

Ah, ok. When you add some randomness then my counterexample doesen't work anymore. I thought 'solvable' meant finding this one perfect move just like in chess.

Hm... now things get more difficult. But I guess finding this 'perfect stategy' then has to involve the fact that your opponents may play another strategy far from perfect? I have two concrete players in mind at present. I know that one of those players always attacks even when obviously pointless and the other guy only attacks when he has like tripple your stack. Playing multiple times against them I adapted my moves to exploit their strategy.

@Norman: i argued a lot about this in another thread, but i warn you it will probably be boring to read;)
http://warlight.net/Forum/Thread?ThreadID=32501&Offset=0

what you are describing is an exploiting strategy, but it is not an optimal strategy. Of course an exploiting strategy is better against someone against whom you have some strong reads, you strategy is exploiting (depends on the opponent), and so it is also exploitable (if you use the same strategy against another player, you can be the one being exploited). An optimal strategy is a strategy that can't be exploited, aka that no other strategy can beat on the long run. However, since everyone makes mistakes, an exploiting strategy is usually more efficient than an optimal strategy against a given player (assuming your reads on this player are accurate).

there is 2 major differences betwin chess and warlight imho:
- luck is involved in Warlight(that is to say probabilities are involved), so if you do the same move twice, you can have two different outcomes. What you can do in theory is determine the "expected outcome" for each moves, and chose the strategy that gives you the best expected pay-off
- In chess you can see all opponent moves, while warlight is a game of incomplete information, so in order to determine the optimal strategy you would have to cross all your different possible moves with all of the opponent possible moves, weigh up the expected outcomes for every situations, and determine the overall strategy (most likely a mix of different strategies) that makes you unexploitable

Edited 2014-03-31 22:31:29

@125ch209:

Yes, makes sense what you say. No doubt there is this perfect strategy able to maintain a win rate of >= 50% against every other warlight player and of exactly 50% against myself in the long run.

125ch209 wrote:

luck is involved in Warlight(that is to say probabilities are involved), so if you do the same move twice, you can have two different outcomes. What you can do in theory is determine the "expected outcome" for each moves, and chose the strategy that gives you the best expected pay-off

Is that really the best way to go? Maybe it's better to not (only) look at the "expected" (average) outcome, but to prefer the move where the worst possible outcome is least catastrophic.

Say you've locked up your opponent in Australia and trying to mop up. You can't predict how many armies he will deploy, you can't predict whether or not the opponent will counter-attack and you cannot predict the turn number of the counter-attack if it does happen. Do you really care about the expected value of breaking Australia... or do you care much more about the risk of a counter-attack breaking your (much more valuable) Asia?

@RvW: "expected outcome" or "expected pay-off" doesn't mean "expected income". The expected pay-off of a strategy has to take into account not ony the income you get, but also you relative position on the map, the opponent income, etc.
Say a strategy makes you break autralia 50% of the time, but lose Asia 20% of the time, and 30% of the time your relative position doesn't change. Maybe the risk of losing Asia isn't worth trying to break into australia. Each outcome has to be assigned a "weight". For example, if breaking into australia weight "10" (arbitrary value), and losing asia weight "-50", then the expected pay-off of the strategy "Try to break into australia" would be:
50%*10 + 20%*(-50)= -5. then you compare this number with the expected pay-off of other strategies, and choses the one with the highest expected pay-off. Sometimes 2 strategies can have similar pay-offs, so then you can chose the one more risky or the one more safe. For example if your opponent is really tough, given 2 strategies with similar pay-off, it might be better to chose the riskier one, but if you have an edge over your opponent, a safer strategy is best, so that you can exploit his mistakes later on.

"Say you've locked up your opponent in Australia and trying to mop up. You can't predict how many armies he will deploy, you can't predict whether or not the opponent will counter-attack and you cannot predict the turn number of the counter-attack if it does happen"

You can predict. That's exactly what you must do, even if you don't get it exactly right. I mentioned earlier that the hardest part of writing an AI would be teaching it to see through the fog but you must at least make an effort. The opponent doesn't just deploy a random no. of armies to random locations in Australia. There is a pattern, and therefore a computer can be taught to approximate it and take advantage of it.

Edited 2014-04-01 12:29:55

125ch209, what I mean is, if you estimate you are currently in a winning position and you see a move with 1% -1000 "positional value" and 99% +11 "positional value". The average is positive, but I would still be hesitant; if you incur that -1000, you might well lose your winning position.
It's similar to (but inverted from) the reason why people play the lottery. The (insanely) small chance of winning the jackpot cannot compensate the big chance of losing a little bit (the price of the ticket); the expected outcome is still negative. But the ticket is cheap and does not really influence your finances all that much; winning the jackpot would.

---

dead piggy, I meant "accurately predict". The problem is the non-linearity of many WL mechanisms. That makes it really hard to meaningfully weigh your decisions. Defeating one army more or less is not just statistical noise, it can break a bonus, causing a ripple effect completely changing all future moves. The Butterfly Effect and reliable predictions don't really mix well.

The opponent doesn't just deploy a random no. of armies to random locations in Australia.

Have you seen some of these bots? :p

@RvW:
a positive or negative payoff isn't really meaningful, you can only compare the payoffs relatively to each other, so in your case, maybe the strategy to "do nothing but place armies" has a higher payoff (considering you positional advantage) than other strategies

RvW a warlight AI would not look more than 1 turn into the future so the butterfly effect would not be a problem. It would not assses the pros and cons of a move. I don't think you would teach the AI to put a % on the chance of a move gaining "positional points". You would simply give it rules to follow. In my head I would do all the calculating about which move to make in situations with certain characteristics then id teach the ai to asses the characteristics. Eg in my head I know that if the opponent has Georgia and I have scand/west Russia/central Russia then I need to clear him from Georgia. Do I deploy all on Murmansk and make a big attack first move? do I try and out delay my opponent and make counters from both Moscow and ufa? well, what is my opponents income and what is mine? Do I have an OP card and does he? Are we fighting elsewhere on the map? I would "hard code" the Ai to ask and answer these questions and use the answers to make the decisions myself.

@125ch209:

version 1044 now.... how about taking a bathroom break from time to time?

You got the heart, have to give you that. Your current second place is quite impressive for someone creating a forum thread named "Coding the PlaceArmiesMoves and AttackTransferMoves in the same method".

finally managed to get my bot not crashing the damn simulator, hope to climb up a few spots during the weekend even though i still haven't implemented all the strategy i was thinking of, i'm still way too passive attacking the enemy. have to clean up a few more bugs. :) wish i had more time for this. :(

@Norman: i learn Java so that i could do this challenge, i never really programmed before exept for some matlab simulations. I'm at version 1044(1052 actually :) ) because every time i change/add one line of code i upload the bot to see if it compile (i don't know how to debug on my computer). And usually for every line there is 2 or 3 errors :D, so 1 line of code represent 2 or 3 version (true story). Until version 960, my bot was crashing a lot and i didn't know why so i was uploading like crazy to try to debug it. But i agree, i'm spending way too much time on this, i was so frustrated that my bot was compiling succesfully yet crashing every 3-4 games without any obvious pattern that i got obsessed. Now that it don't crash anymore (i think it crashed 2 times in 50 games, i can live with that), i'll slowdown ;)
Also i need to thank Odin and Z-Dog, they helped me to get around Java

edit: and if you want a real nooby thread, check this one hahaha
http://stackoverflow.com/questions/22799661/for-loop-inside-else-if-statement

Edited 2014-04-04 22:24:26

I strongly suggest you look into figuring out how to do debugging on your own machine. That will allow you to "trace" through the code (let it execute one line at a time, then inspect the values of variables while it's paused, see which branches are actually taken, which loops get executed and how often, etc, etc, etc).

I strongly suggest you look into figuring out how to do debugging on your own machine. That will allow you to "trace" through the code (let it execute one line at a time, then inspect the values of variables while it's paused, see which branches are actually taken, which loops get executed and how often, etc, etc, etc).

Would help a lot. However, to make this possible you need your own game engine, that gets your code as input. I'm using the (slightly modified) game engine from github to compare different versions of my bot by letting an old version play a couple hundred games against the new version.

Since the game engine is written in Java it should be possible to modifiy it so that it takes Java code as input instead of runnable files. I took a look into it but since I always used the Java StarterBot and never bothered about the actual communication with the game engine I thought it wasn't worth the effort.

inspecting the value of variables would be really awesome and very very helpful, but i can't figure out how to make the game engine work on my computer, if someone could help me do that, that would be great

It just gives you the board updates through standard input and expects you to write orders to standard output? In that case you could automate most of it by simple redirecting stdin from and stdout to files.

Make an input file which contains all the data necessary to initialise (such as board setup). Then run your program with a command line similar to the following (this is assuming you're using Window):

yourprogram.exe < input.txt > output.txt

Afterwards you can open output.txt in your favourite editor to check what moves were generated by your program.

Sure, it will only allow you to debug a single move (since no additional input is generated to tell you the results of your first move), but it should still be much more useful than only running it on the server, where you have no idea what's going on in your program.