I think the key to programming the best bot possible is to make net income the priority - to only break/take bonuses that give you the best income advantage possible over your enemy. Then, code in any exceptions to that rule (combatting the stack instead of pursuing short term advantage) and beasssst over everyone :)

Good Kid wrote:

Millionaire, maybe, bullionaire, no. It wouldn't be "that" hard. Bots can beat legit players in virtually every game in existence.

That highly depends on the complexity of the game:

• Writing an unbeatable tic-tac-toe bot should be an exercise roughly at high school level. A graphics calculator has plenty storage and compute power to run the bot (if written properly; a regular computer could still churn through an inefficient bot in real time).
  
• Writing a bot which plays Yahtzee optimally (which still cannot guarantee victory, due to the influence of random chance) is definitely university level (and either each move will take minutes/hours to calculate, or pre-computing the data to quickly decide the best move will take minutes/hours). This can still be done by a single person on a regular computer.
  
• Writing a bot which plays chess optimally is not a solved problem. Deep Blue beat Kasparov, but it is certainly possible (in theory) to create an even better bot. Note this requires a team of professionals and a supercomputer to run all the calculations.
  
• Writing a bot which plays go / weiqi acceptably is an unsolved problem as well. It's been a while since I read up on progress, but last time I checked, mediocre human players had a fair chance playing against the world's best go bot.
  

Have a look at this chart http://xkcd.com/1002/ if you really believe computers can beat humans in "virtually every game in existence".

Good Kid wrote:

In 1997 Deep Blue beat Kasparov at Chess, computers today are a lot more powerful than they were 17 years ago, the top chess bots today are significantly better than the top human players.

I don't have actual data, but the computer on my desk is still dwarfed by 1997's supercomputers. I wouldn't be surprised if Grandmasters can still routinely beat the best commercially available chess bots.


dead piggy wrote:

Didn't IBM make Deep Blue, and aren't IBM billionaires?

IBM "was a billionaire" way before they created Deep Blue. Having that much money gave them the means to create Deep Blue, not the other way around. While the publicity around and the research (partly reusable on other projects) behind Deep Blue undoubtedly made them some money, I strongly doubt they earned a billion dollar out of it (much less made a billion dollar profit; building Deep Blue must've been expensive).

Edited 3/31/2014 00:55:51

Hey, interesting chart @RvW.

Before anyone is looking again for the perfect warlight playing bot I have to disappoint. Warlight is unsolvable, meaning that there will never be an algorithm showing you the perfect move. This can be proven by creating a counterexample: Let's say in picking stage player A is running his 'perfect move' algorithm. Then player B can run the same 'perfect move' algorithm and put the result into his 'perfect counter' algorithm. That way player A will have a disadvantage after picks (not just by the counter but by revealing all his starting spots) so by definition he didn't play the 'perfect move'.

In games like classic risk or chess you can look for your perfect move.

The best commercially available chess bots are better than grandmasters and have been for a long time now.

I wasn't saying that deep blue was worth a billion dollars. Having the incredibly smart software and hardware engineers necessary to build deep blue earned them a billion dollars. And after that they decided to build deep blue. Odin wasn't saying that a warlight AI would be worth a lot of money he was saying that the skills to do it would be worth a lot of money.

Before anyone is looking again for the perfect warlight playing bot I have to disappoint. Warlight is unsolvable, meaning that there will never be an algorithm showing you the perfect move. This can be proven by creating a counterexample: Let's say in picking stage player A is running his 'perfect move' algorithm. Then player B can run the same 'perfect move' algorithm and put the result into his 'perfect counter' algorithm. That way player A will have a disadvantage after picks (not just by the counter but by revealing all his starting spots) so by definition he didn't play the 'perfect move'.

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"

And this is a picking strategy, perfectly balanced, so that there is no way the opponent can counter you efficiently. So no, warlight is not unsolvable, any game with a limited number of player and a limited number of possible moves is solvable

Edited 3/31/2014 16:28:30

Hobbit, I think you're describing an optimal strategy, not a perfect strategy. There's an important difference between the two.

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 3/31/2014 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 4/1/2014 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".