Lux <-> Chess

AI discussion, ideas, and SDK help.
Post Reply
User avatar
GregM
Luxer
Posts: 252
Joined: Wed Jun 01, 2005 4:33 pm

Lux <-> Chess

Post by GregM » Sun Apr 29, 2007 1:11 pm

This might be of interest to bot-makers:

Recently Icreated a chess-playing program, and I've been thinking about whether techniques used in chess programming could be applied to Lux.

Here is a simplified outline of a chess program:
First you need a function that will look at a position and evaluate how good it is for you. Then you need a function that will look at a position and give all the possible moves for a position. To decide on the best move in a given position, you simply look at all possible opponent replies to each move you could make, and then all possible replies you could make to that, and then all possible replies he could make to that, and so on until you run out of time. Then you pick the move that forces the most favorable outcome according to your position evaluation function. This algorithm is called minimax. The result is a program that is relatively simple: all you have to do is tell the program what to aim for (with the evaluation function) and it will figure out how to get there.

In comparison, the design of a Lux bot (or at least of BotOfDoom) is very messy. There are all sorts of heuristics saying what to do in certain situations: if x and y are true, do this, if z is true, attack here, and so on. It's hard for the bot to have a unified plan so that its moves are all coordinated and don't get in the way of each other (though Bertrand seems to be putting some planning into Reaper).

So, I imagine a Lux bot that runs like a chess program, simulating all the possibilities before moving. For the bot, a single "move" would be a relatively high-level concept: taking over a continent, killing a player, executing the fortify phase and ending the turn, and so on. And instead of alternating between player and opponent, all moves would be moves by the bot: it would be planning out its strategy for one turn.

Here's a simple example. Suppose it would be advantageous for the bot to take over two adjacent continents. However, the order in which they are taken is important. Taking continent A first will leave the bot's armies in a good position to invade B, but taking B first will strand its armies and it won't be able to take A. So, the program would look at the possibilities, and see that the best sequence of moves is "take A"-"take B", and proceed to execute that plan.

I'm toying with the idea of writing a bot from scratch implementing this architecture.

User avatar
Zogu
Luxer
Posts: 48
Joined: Sun Jan 16, 2005 1:22 am
Location: Le Bic / Rimouski, QC, Canada
Contact:

Re: Lux <-> Chess

Post by Zogu » Sun Apr 29, 2007 1:54 pm

I hope you have used alpha-beta pruning for vastly improving the time performances of your minimax.

Minimax is MUCH harder to program when there is more than 2 players.

It is also extremely tricky to implement in games where:
- moves are reversible, or
- there are large number of possible movement loops, or
- moves involve more than 1 action, or
- the Z function has to be tweaked for strategic or holistic (global) issues

A few years ago, I have implemented minimax in a 4-players "Othello" game (also called "Reversi" or "Cool Spot"). It was quite difficult, even though the board was square and the moves involved only 1 single movement per turn.

The fact that a player can make a large number of movements in a single turn in Lux, and the fact that the turn is made of 3 separate steps (place armies, attack, troop movement) makes things even more difficult.

Let's say that you own 30 countries and you have 15 armies to place. Then, the number of possibilities just for placing armies is given by a Permutation function. Let's say you have "C" countries and "A" armies. Then then number of possibles ways of placing armies, W, is given by a limited sum of Permutation functions:
W(A,C) = Sum{c in 1...C} Perm(A,c)
which is truly a pain in the a** to compute.
But a rough estimate of this sum would be to say that W(A,C) ~ Perm(A,C) ~ C!/(C-A)!
In our case, we get 30!/15! = 202843204931727360000

The true value is most probably higher. And that's only for the placement of armies in a normal case...

Since this number is very high, one would have to first reduce the search space by applying a heuristic for eliminating "non-interesting" possibilities. I'd say the whole thing is an open question.

If I had 100 hours to invest in a very intelligent Bot, I'd go for an improved "expert system" engine instead With multi-level AND-OR-NOT rule systems expressed in XML maybe.

User avatar
GregM
Luxer
Posts: 252
Joined: Wed Jun 01, 2005 4:33 pm

Post by GregM » Sun Apr 29, 2007 3:06 pm

Right: true minimax isn't workable in a game like Lux. I was merely drawing inspiration from chess programming. The search tree would only be for one turn, and it wouldn't be minimax, merely picking sequence of moves that gives the best turn-end position. Like a chess engine, this hypothetical bot would need only a way to generate "moves"--actually plausible sequences of moves--and a way of evaluating a position. In fact it would probably also need handcoded army placement and fortification methods. Or perhaps fortification could be handled elegantly in an automatic way by having the bot create a "goal position" in which all armies are ideally placed and then fortifying armies in such a way as to reduce the difference between the actual position and the goal position.

User avatar
Zogu
Luxer
Posts: 48
Joined: Sun Jan 16, 2005 1:22 am
Location: Le Bic / Rimouski, QC, Canada
Contact:

Post by Zogu » Sun Apr 29, 2007 4:03 pm

I do agree, GregM.

One thing that could work would be to use a higher-level view of the game, for the minimax. Instead of considering all possible moves, the Bot could simply consider a limited set of "general" strategies for that turn. For instance, these macro-strategies could be: "conquer as much as possible", "wipe other player out", "get continent", "conservative expension", "improve defenses", "merely try to get a card", "pass".

If each of these high-level strategies correspond to a defined set of actions, and if each action is deterministic (ie, the Bot doesn't flip a coin to make choices), then it is possible to implement minimax for one turn.

The same high-level strategies could be used to "simulate" or evaluate the opponents' turn, given that these strategies realistically cover a decent range of possibilities.

However, there is an additional source of headache: the dice. In order to evaluate the outcomes, you much either play the turn multiple times or use a mean-case scenario based on expected loss. You then need a probability table for each dice combination (opponent versus player); such a table isn't hard to build.

User avatar
Bertrand
Reaper Creator
Posts: 568
Joined: Mon Nov 28, 2005 4:35 pm
Location: Montreal

Re: Lux <-> Chess

Post by Bertrand » Sun Apr 29, 2007 5:53 pm

GregM wrote:I'm toying with the idea of writing a bot from scratch implementing this architecture.
Sounds like a good idea. I used a different approach with Reaper, trying to retrofit planning logic into the existing code. It does look like a mess. Starting from a blank slate would surely result in cleaner code.

And I agree with you and Zogu: the "unit of planning" in Reaper is very high level. In fact there are only 3 possibilities:

- Terminate a set of players
- Take over a continent
- Pop a border

All this goes on in the placing armies phase. The planning is done on a copy of the board, made with the getCountriesCopy() method. This routine of mine is now included in the Lux SDK.

What Reaper does is try different combinations of moves on this fake board. He then analyzes the result, and eliminates the moves that did not work as intended.

As Zogu observed, I also had to simulate the dice. I used the simple rule that the attacker needs 5/6 of the defending armies to come out even.

That brings me to the minmax algorithm. I'm not sure it would be effective one move deep. The problem is with the evaluation function: what determines a good position? In chess programs, this problem is called the "horizon effect", and is minimized by analyzing ahead many moves. Clearly, this is not feasible in Risk because the dice introduces randomness that cannot be predicted.

User avatar
GregM
Luxer
Posts: 252
Joined: Wed Jun 01, 2005 4:33 pm

Post by GregM » Sun Apr 29, 2007 8:53 pm

Perhaps the "min" part of minimax could be done in this way: after simulating a sequence of moves, see if any "moves" could be applied successfully to us to result in an improved position for another player. So if, after some series of moves, another player could advantageously kill us off or pop one of our continents, we have to take that into account in the evaluation of that move sequence. If this works, it might help make sure that bot doesn't make stupid moves that leave it open to attack. I guess this is what Zogu is suggesting.

As for the evaluation function: it would take into account numbers like total armies, # of cards, continents held, and positional factors like continent border defense to determine how good a give position is. Probably it would look at each player on the board and give them a strength-value in units of armies, and then return the bots strength as a percentage of the total strength. Or something like that. This would, of course, be a complex thing, but that's as it should be: the evaluation function is the sum total of the bot's knowledge about how to play well.

Another advantage I see is that it may be easier to code ideas that would be difficult to implement other ways. An example from another thread: a player suggested that bots should, like humans, work to minimize the length of their border so as to defend efficiently. It would be very difficult to code something like this into BOD currently; I simply don't know how to write a function to do that. But in this new scheme, you would only have to include a term in the evaluation function that gives a penalty dependent on border length. Then the bot might decide that taking over a negative-bonus continent (like the bridges in Castle Lux) would be a good move because it would consolidate border armies.

Also: a bot made this way might be amenable to tuning using genetic algorithms and stuff like that. With a concrete evaluation function in place, the bot's "genome" could be the weights it assigns to each element of the evaluation. Then by running lots of games it would be possible to evolve better values for these weights. I guess it would depend on how quickly you can play a bot game. How fast do games go with the -superfast flag on?

User avatar
Bertrand
Reaper Creator
Posts: 568
Joined: Mon Nov 28, 2005 4:35 pm
Location: Montreal

Post by Bertrand » Sun Apr 29, 2007 9:47 pm

GregM wrote:If this works, it might help make sure that bot doesn't make stupid moves that leave it open to attack.
Or it could make the bot paranoid, afraid of making risky moves. Trying do determine how the other players will react is very hard, because of the different styles of play, and emotional responses. But I agree that it's worth a try as a filter against obvious bad moves.
GregM wrote:Another advantage I see is that it may be easier to code ideas that would be difficult to implement other ways.
Very true. This is emergent behavior in action. This happens in a limited extent in the new Reaper. He surprised me taking over a continent by reducing half of a defense force with one group of armies, a suicide-like move that I did not explicitly code. He then finished the job with another group from the other side of the map. I thought at first that this was a bug, until I found out that he had combined two different actions to achieve the desired result.

A bot designed from the ground up to work in this fashion would be awesome.
GregM wrote:I guess it would depend on how quickly you can play a bot game. How fast do games go with the -superfast flag on?
I don't use that mode anymore, there were problems with it the last time I tried it. What I do is run 4 games at the same time, and let them cycle all night. You can play many thousands of games this way. One drawback is that Lux often writes to the hard drive, and doing this non-stop for many weeks is probably wearing out my hard disk. Oh well, I need an excuse to buy a new laptop anyway.

User avatar
GregM
Luxer
Posts: 252
Joined: Wed Jun 01, 2005 4:33 pm

Post by GregM » Sun Apr 29, 2007 10:46 pm

Bertrand wrote:I don't use that mode anymore, there were problems with it the last time I tried it. What I do is run 4 games at the same time, and let them cycle all night. You can play many thousands of games this way. One drawback is that Lux often writes to the hard drive, and doing this non-stop for many weeks is probably wearing out my hard disk. Oh well, I need an excuse to buy a new laptop anyway.
I guess if you have a full-fledged Risk implementation, as complete simulation and planning requires, you could use that to run games. With no graphics requirements it should run pretty fast.

User avatar
Bertrand
Reaper Creator
Posts: 568
Joined: Mon Nov 28, 2005 4:35 pm
Location: Montreal

Post by Bertrand » Tue May 01, 2007 8:45 pm

GregM wrote:I guess if you have a full-fledged Risk implementation, as complete simulation and planning requires, you could use that to run games. With no graphics requirements it should run pretty fast.
Good idea, but lots of coding involved.

I retried the -superfast option, and it works with some drawbacks. It basically takes control of my machine, making Windows unresponsive. With that running, it's impossible to do other work, so it has to run on a dedicated machine.

Dustin, I hope you are reading this. In order to see in real-time the lux log, I used to be able to run Lux like this:

java.exe -jar LuxCore.jar

With the latest Lux version I get the following message:

Exception in thread "main" java.lang.NoClassDefFoundError: Lux

How do I make this work?

User avatar
dustin
Lux Creator
Lux Creator
Posts: 10998
Joined: Thu May 15, 2003 2:01 am
Location: Cascadia
Contact:

Post by dustin » Tue May 01, 2007 11:04 pm

Bertrand wrote:With the latest Lux version I get the following message:

Exception in thread "main" java.lang.NoClassDefFoundError: Lux

How do I make this work?
Download Lux now and the new package should work like the old one did.

User avatar
rip
Luxer
Posts: 352
Joined: Wed Mar 31, 2004 10:22 am
Location: Vienna Austria
Contact:

Interesting

Post by rip » Wed May 23, 2007 3:36 am

This thread discusses the genetic algor. idea that the bot places weightings onto a decision matrix about kill-'im, get/fort a continent, pop the border, etc strategies.

This is what Ravitar does, but I never had the time to really focus on "all of it", ie the decision matrix is sub-opt and too many strategies I was trying to implement all at the same time. In a language I wasn't familiar with.

So I split everything out before I left Lux for Kenya (Dustin, can I have a "NUKE THIS COUNTRY, SPRAY A PERSISTANT, BINARY NERVE AGENT OVER THE ENTIRE THING AND THEN SALT WHAT'S LEFT" weapon, so I can take any country called "East Africa" permanently off the board? Please?). Right now I have working bots that snipe players and grab continents. I'm working on a third called Bug (turtle-like, but with other concepts in play). I have one other concept I need to get working, and then I roll it all back into Ravitar for the genetics.

And 0h, I had a group of guys over last night for a CounterStrike evening, and showed them Lux. If you get a bunch of downloads from Nairobi over the next couple of days, that'd be them :>

rip

Post Reply

Who is online

Users browsing this forum: No registered users and 57 guests