looks like fun

AI discussion, ideas, and SDK help.
Post Reply
User avatar
varoadstter
Luxer
Posts: 67
Joined: Wed Jan 23, 2008 9:22 am
Location: Raleigh, NC

looks like fun

Post by varoadstter » Wed Jan 23, 2008 9:42 am

Greetings, all.

I'm interested in creating my own bots to play in Lux. I bought the game last night and had a good time playing through several maps against the AI and some live games. Reading through the FAQs and trolling through the message board I have a few questions that I'd be interested in anyone's input on. I have some background in programming game AIs from writing ones to play chess, backgammon, and poker. I find expert systems interesting but I think I would like to go for a full AI implementation here. Would anyone care to reply to the following:

1) I see the standard game turn is set to 30 seconds. Since I'm planning for my bot to evaluate game state using Monte Carlo simulations I wanted to make sure that it's acceptable for my bot to use a lot of it's 30 seconds each turn. Is there an expectation that bots turns complete quickly? Would it be irritating to you as a player playing against my bot if it took all it's available time each turn?

2) Looking through the source code I don't see whether or not a game state model exists - is this available or do I need to construct my own game state model (who owns what, how many armies on each country, etc.)? This will be needed to set the initial state each time I run a Monte Carlo simulation.

3) Is there a seperate ranking system reserved exclusively for bot v. bots play or is the ranking system set up for all players (human and bot)? As my bot moves up (hopefully) the ranking scale I'd like to know which opponents would be best used to measure progress. I'm primarilly interested in having my bots play well against other bots although by extension I would expect them to perform better and better against human opposition as well.

Hope to be contributing to the community soon.

-VAR

User avatar
mbauer
Not A Truck
Posts: 3959
Joined: Mon Jun 28, 2004 3:59 pm
Location: Tallahassee
Contact:

Post by mbauer » Wed Jan 23, 2008 10:38 am

1) As a player who plays mostly offline against all bots I'd have to say that, yes, I would be annoyed if a bot took a long time to complete a turn. I do generally expect my bots to complete their moves very quickly, as do most people I suspect. However, since I play offline I generally have no time limit set. I'm guessing that time limits are mostly an online play phenomenon.

2) I'm not a bot maker so I don't fully understand this question and therefore cannot answer it.

3) It's my understanding that all humans and bots share the same ranking system, that is if you are talking about the online game ranking system. There is a "doctrine" that exists called Bots first which a lot of Luxers play by. Basically, it states that in an online game all bots must be killed before any human is. As a result bots ranks are adversely affected and don't accurately portray their true skill. Lux does have a built in record book, which can help you keep track of your bots stats locally.


Welcome to Lux, we need more bot programmers. Good luck!
MB

User avatar
The Wontrob
Ninja Doughboy
Posts: 2792
Joined: Wed Oct 03, 2007 9:56 pm
Location: The Pan-Holy Church, frollicking
Contact:

Post by The Wontrob » Wed Jan 23, 2008 12:32 pm

Your best bet is probably to send a PM to Bertrand or Preacherman. Bertrand is the programmer of reaper who is by many considered a God among bots. Preacherman programmed Nefarious. Those two could probably help you out most, as far as I know.

User avatar
3DA
Luxtopian
Posts: 1978
Joined: Sat Sep 08, 2007 9:26 am
Location: Big Chicago
Contact:

Post by 3DA » Wed Jan 23, 2008 12:59 pm

Welcome, Varoadsster!

I have never programmed a bot and I cannot answer any of your questions - but I did find your post fascinating. I just read up on Monte Carlo simulations and have some questions about how you'd build this bot. If I follow your post correctly, this is what you're proposing:

1. the bot AI would look at the "game state model" - what player owned what, where army concentrations were, etc.

2. Using this Monte Carlo method, the bot would "run" a bunch of potential moves to their logical conclusion and see which one would be the most advantageous. For instance, if the bot held 6 countries and had an income of 3 armies, it would play out a handful of scenarios (all 3 armies in one of six countries, 1 army in 3 countries, all out attack, and so on) and see which one would most likely bring it closest to winning - or whatever goal it had at the time (get a card, take a continent).

3. Once it had run a bunch of simuations in its "head," and decided which one had the best probability of success, then it would submit its move to the actual game board, and play would continue.

Is this correct? If not, please explain. If so, then I have a couple of questions:

1. How would the bot "decide" what it's goal was at the time? Ultimately, of course, it's goal is to win - to wipe out all the other armies on the board. But there are interim goals to achieve in the game (depending on the map) that might help the bot win. Those goals can change based on the game state. How would you program the bot to choose one of those interim goals?

2. How far ahead would you allow the bot to play out the possibilities? Three moves in advance? Four? As I understand it, chess AI's and the like play by essentially running the entire game out to its logical conclusion based on the total numbers of possible moves that they and their opponent can make - correct? In this game, though, the amount of potential things that can happen is massive. 5 opponents, each with different incomes and different amounts of countries held ... I cannot imagine that even a computer could calculate all the possibilities of play in any kind of viable time frame.

Is this why you were asking about bots using all their time?

---

Thanks for the interesting post. I look forward to hearing your response. In the meantime, I invite you to play online: check out how the game is played by bunches of humans and join the community. Be forewarned! As with any online community, not everyone is on their best behavior all the time, so you may run into some unpleasantness - especially in your first couple of games, when you're learning the ropes.

Also, I would suggest that you talk with the user Bertrand. He's the guy that's written what most people consider to be the most difficult bot to beat: Reaper.

Again: welcome.

User avatar
varoadstter
Luxer
Posts: 67
Joined: Wed Jan 23, 2008 9:22 am
Location: Raleigh, NC

Post by varoadstter » Wed Jan 23, 2008 1:45 pm

Hi 3DA,

You've captured the spirit of my intention. Since you are interested I will elaborate on my plan. Before I begin, though, let me concede that I am coming at this from the outside. I have played the Risk board game hundreds of times from youth to adulthood and understand the mechanics of the game and have some personal ideas about strategy that work well in my experience. Having said that, I understand that playing Lux involves more than just beating some friends, but rather the best players known to exist. Additionally, Lux offers far more than the standard game and a bot must strive to perform competently in all game modes (although it may also be specialized to one game type, map, etc.).

Now, on to the discussion:

In a Monte Carlo simulation one starts from a known state and progresses through a game as far (or as long) as one chooses to arrive at a game state in the future - this could be as short as one turn or literally until the player is eliminated or wins the game. This future game state is evaluated (scored) and then the initial state rerun X number of times. The sequence of commands that result in the highest score is then used for the actual game.

The game where this approach works the best is backgammon. From a given game state you can literally move all the pieces you have a hundred times and even play those games to conclusion in a fairly short timeframe. Now, of course, there's no guarantee that a game of backgammon will ever look like any of the simulations run (due to the random nature of dice rolls) but the point is to determine which of all possible moves results in the best result over many iterations.

Backgammon is a great analog for Lux from an AI perspective.

There are difficulties, however. Of the top of my head, I will have to deal with the following challenges:
  • Multiple opponents
    Larger decision trees
    Producing a useful scoring for a given game state
    Teaming/Alliances/etc.
Fortunately, however, Lux lends me some assistance. I will be able, at the start of a game, to know which bots I'm playing against (again, I'm really mostly interested in beating a group of bots). Not only that, but I believe I can actually use a method similar to that used by Chimera to use the opponent models to serve as my opponents when I run simulations. By setting the game to some future state and asking a known bot to simulate its turn, I can get a decent approximation of how the game state would change going forward with the specific opponents that I'm up against. Note that this is a significant problem when playing with any number of human opponents.

As for the large decision trees, I will have to use some expert system concepts to help me prune the decision tree significantly in order to have the simulations complete in a reasonable time frame. I can't just simply allow for every possible move to be tried or it will just take way too long.

Evaluating the game state will be challenging and likely lead to many errors at first. I must come up with a way of assigning a numerical score to each game state (from my bots perspective). Some of this will be fairly straightforward (how many countries do I hold, how big is my border, what's my income, etc). Some of this will be very subjective (am I a likely target, what are my weaknesses, etc). If I score game states badly (or it's just not something that can be abstracted) then all the simulations in the world won't lead to good results.

I think I answered your questions in the response above but if I haven't given you enough or if you have further questions please feel free to ask away.

User avatar
3DA
Luxtopian
Posts: 1978
Joined: Sat Sep 08, 2007 9:26 am
Location: Big Chicago
Contact:

Post by 3DA » Wed Jan 23, 2008 2:30 pm

Thanks! Your response is really interesting and has given me a lot to think about.

It seems to me that the re-evaluation of the game state and the resetting of the criteria that go into making the game score would be critical in building a decent AI opponent. It got me thinking about how many times during an average game that I re-evaluate the board and change tactics - and when I do it, and why, and what my new interim goal becomes.

It also got me thinking about trying to codify a set of goals for the game, and how markedly different those goals are depending on the map and the settings. For example - any game where the continent increase in income is set at 20% and higher becomes a very different game than one that is set at 5%. Holding income - and preventing others from keeping it - becomes more important than the cards very quickly as the bonuses for continents increase. So building a bot that is a good opponent on all boards at all settings would be a herculean task. The amount of variables and the choices based on those variables is staggering.

No further questions come to mind at this point - but I may want to jump back in to the discussion and ask some more questions later. Thanks again! I wish you luck, and look forward to beating the pants off your bot in the future. :) I know you said you're primarily interested in your bot's performance against other bots, but if you need a human playtester please let me know. I would love to play against the bot in various iterations and see how it progresses. Perhaps I can even help you out in building it by suggesting goals and methods of evaluating the game state based on my experiences playing the game. I'm far from the best player here, and far from having played the most games, but I hold my own.

If you're interested, please let me know. Thank again.

User avatar
varoadstter
Luxer
Posts: 67
Joined: Wed Jan 23, 2008 9:22 am
Location: Raleigh, NC

Post by varoadstter » Wed Jan 23, 2008 2:49 pm

3DA wrote:Thanks! Your response is really interesting and has given me a lot to think about.

It seems to me that the re-evaluation of the game state and the resetting of the criteria that go into making the game score would be critical in building a decent AI opponent. It got me thinking about how many times during an average game that I re-evaluate the board and change tactics - and when I do it, and why, and what my new interim goal becomes.

It also got me thinking about trying to codify a set of goals for the game, and how markedly different those goals are depending on the map and the settings. For example - any game where the continent increase in income is set at 20% and higher becomes a very different game than one that is set at 5%. Holding income - and preventing others from keeping it - becomes more important than the cards very quickly as the bonuses for continents increase. So building a bot that is a good opponent on all boards at all settings would be a herculean task. The amount of variables and the choices based on those variables is staggering.

No further questions come to mind at this point - but I may want to jump back in to the discussion and ask some more questions later. Thanks again! I wish you luck, and look forward to beating the pants off your bot in the future. :) I know you said you're primarily interested in your bot's performance against other bots, but if you need a human playtester please let me know. I would love to play against the bot in various iterations and see how it progresses. Perhaps I can even help you out in building it by suggesting goals and methods of evaluating the game state based on my experiences playing the game. I'm far from the best player here, and far from having played the most games, but I hold my own.

If you're interested, please let me know. Thank again.
Thanks for the feedback. I certainly could use the help of a veteran Luxer in coming up with suggestions for expert system methods (goals, as you call them).

As to your point regarding cards and increasing value - yes, that is obviously going to be something that must be included in evaluating game state. I'm going to goto this at the beginning with the (naive?) belief that by producing a good scoring system I can develop a bot that will, indeed, perform very well for all the game types it knows how to play.

Some of the things that excite me about how these kinds of systems come together is that the bot very well could develop a line of strategy that is completely beyond consideration by human players but yet proves to be more effective than all other options.

Thanks, again, for your interest and especially your offer of assistance. Once I have the time to put some framework together, you can rest assured I will be asking for your input.

-VAR

User avatar
3DA
Luxtopian
Posts: 1978
Joined: Sat Sep 08, 2007 9:26 am
Location: Big Chicago
Contact:

Post by 3DA » Wed Jan 23, 2008 3:23 pm

:smt023

Count me in, Var. You've piqued my interest. I'm sure I'll learn a lot.

I don't think it's naive to assume that building a sound tool for evaluating the game state is the basis for a strong bot. I think I can start helping in this process by trying to compile a list of measurable criteria that are important to track in any game - and deciding how important those things are at various points in the game.

The more I think about this, the more excited I am about it.

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

Post by GregM » Wed Jan 23, 2008 8:32 pm


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

Post by Bertrand » Wed Jan 23, 2008 8:36 pm

Welcome varoadstter, AI programming in Lux is lots of fun and a great challenge. As for your questions:

1) I would not let an AI work for 30 seconds each turn, for many reasons. In fact speed is essential, ideally less than a few seconds per turn. Human players would be quickly irritated by this. If you scan the threads here this subject has come up often.

Some players have slower machines that can barely run Lux. A CPU intensive AI would not be able to run on those machines.

Some of the maps in Lux are quite large, and the possibilities for each move rise exponentially. Your AI might work on the Classic map, but be unplayable on the larger maps.

Finally, such an AI would be untestable. When I try something in Reaper, I need a minimum of 250 games, and preferably 1000 games, to find out if the change is good or bad. That translates to one or two hours of play with the -superfast option. At 30 seconds per move, this would take more than a day.

2) The game state is contained in the countries array. This array can be copied, and used to perform simulations. The Board class contains all the methods used by the game engine. If you want to simulate stuff, you will have to front-end some of those methods to avoid modifying the real game board state.

I successfully perform simulations in Reaper, but only for his turn. I used simulations to plan continent takeovers, and player kills. I did not attempt to simulate the other players. If you use the Monte Carlo technique, just simulating the AI's turn should take quite a while because of the enormous number of possibilities.



The Wontrob wrote:Your best bet is probably to send a PM to Bertrand or Preacherman. Bertrand is the programmer of reaper who is by many considered a God among bots. Preacherman programmed Nefarious. Those two could probably help you out most, as far as I know.
Don't forget GregM, the author of BotOfDoom, and Dustin, the creator of all the built-in bots.

User avatar
varoadstter
Luxer
Posts: 67
Joined: Wed Jan 23, 2008 9:22 am
Location: Raleigh, NC

Post by varoadstter » Sat Jan 26, 2008 10:41 pm

So I've stated to get my utility classses together and I think things are going very well so far. I would consider allowing a bot developer a chance to look over my source code if they wanted to (via email I suppose). Here's some output from my Monte Carlo simulator:

Code: Select all

Monte Carlo attack simulations
Started at: Sat Jan 26 22:35:38 EST 2008
Ended at: Sat Jan 26 22:35:48 EST 2008
Ran 10000 simulations
Attacker used a total of 4963830 armies
Defender used a total of 5021112 armies
Attack was successful 56% of the time
Attack failed 44% of the time
Average attacker losses: 303
Average defender losses: 355
----------------------------------------------
My simulations are set up to randomly assign the attacker and defender from 0-1000 armies each and them run the attack to either success or total defeat for the attacker. If I ran it a million times or so it would probably give me a fantastic rule of thumb value for the ratio of attacking armies to defending armies needed for success.

Post Reply