bot experiments

AI discussion, ideas, and SDK help.
Post Reply
attention disorder
Luxer
Posts: 34
Joined: Mon Jun 11, 2007 1:12 am

bot experiments

Post by attention disorder » Tue Aug 21, 2007 3:05 am

in a bit more than a month from now ill finally have time to start looking at how to program a bot. to the AI specialists, i have some questions about feasibility.

- would it be possible to effectively employ a genetic algorithm to optimize parameters (e.g. an attack threshold) of the AI? Having the fitness evaluated after x games, again and again. Such parameters could be optimized for different environments (6x same bot, diverse AIs, human participation, ...). would that be feasible or would it simply be easier (and more promising) to play around with the settings?

- is it possible to have a bot learn through a sequence of games with humans? parameters would be adjusted automatically based on success in hosted games. where would the learning data be stored? a text file the AI reads and writes to on the server? like where does reaper save his blacklist?

btw, my java skills = 0, i am quite good at vba and know the c++ basics thoiugh. so i am eager to learn, i would really like to learn to build some working AI...

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

Re: bot experiments

Post by GregM » Tue Aug 21, 2007 9:59 am

attention disorder wrote:- would it be possible to effectively employ a genetic algorithm to optimize parameters (e.g. an attack threshold) of the AI? Having the fitness evaluated after x games, again and again. Such parameters could be optimized for different environments (6x same bot, diverse AIs, human participation, ...). would that be feasible or would it simply be easier (and more promising) to play around with the settings?
I think Bertrand has used an automated algorithm to tune numerical constants in Reaper.
attention disorder wrote:- is it possible to have a bot learn through a sequence of games with humans? parameters would be adjusted automatically based on success in hosted games. where would the learning data be stored? a text file the AI reads and writes to on the server? like where does reaper save his blacklist?
Bots can store data on the host machine, but as far as I know there's no way for them to store data on a central server. Bots have access to the host file system and there are also some methods in the Lux SDK for storing and retrieving values.

attention disorder
Luxer
Posts: 34
Joined: Mon Jun 11, 2007 1:12 am

Post by attention disorder » Thu Aug 23, 2007 3:29 pm

thx for the info. sounds good!

cant wait to get started... :)

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

Post by Bertrand » Thu Aug 23, 2007 7:15 pm

Genetic learning is worth it: I have improved Reaper's win % by 5 - 8 %, depending on the settings and map. I used it to fine tune numerical constants. Doing it by hand is possible, but it takes lots of time. The most important environments to tune for are the card settings, the continent bonus % increase, and the map size.

When Reaper is in learning mode, I use a file to store the numerical constants. This file is written to whenever a winning mutation is found. When learning is over, I cut and paste the file into Reaper's code to hard-code the values. The name of the file is derived from the map's attributes and the card values, to differentiate the files from each other.

Reaper's blacklist is different: it is stored in persistent storage with the Lux SDK. The blacklist is reset whenever Lux is restarted.

I found that it is not possible for an AI to learn by playing with humans: too many games are required. For example, I consider that a mutation (a set of numerical constants) is good only after it bested the other ones after 250 games. In order to effectively learn, many mutation cycles are necessary. In practice, it takes at least 24 hours of continuous playing at high speed (superfast option) to learn one setting (map-cards).

User avatar
SunTzu
Lux Cartographer
Posts: 1586
Joined: Sat Jan 14, 2006 1:48 am
Location: Maryland

Post by SunTzu » Fri Aug 24, 2007 10:33 am

This sounds really cool!

Are there any resources we can check out that would help explain how to implement genetic learning algorithms?

Will this only work for constants? Or will it also work for functions (such as a function to calculate the benefit of conquering a continent)?

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

Post by GregM » Fri Aug 24, 2007 3:24 pm

SunTzu wrote:This sounds really cool!

Are there any resources we can check out that would help explain how to implement genetic learning algorithms?

Will this only work for constants? Or will it also work for functions (such as a function to calculate the benefit of conquering a continent)?
Googling for "genetic algorithms" gives some decent hits, for example: http://cs.felk.cvut.cz/~xobitko/ga/

"Evolving" a function to perform a task (as opposed to a set of constants) is "genetic programming," and is rather harder.

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

Post by Bertrand » Sun Aug 26, 2007 8:59 am

SunTzu wrote:Are there any resources we can check out that would help explain how to implement genetic learning algorithms?
Genetic learning is a fancy name for something that is essentially very simple. I'll try to explain how I did it.

When designing an AI, you have to go through two very different phases of programming. The first one is straightforward and mechanical: utility routines to kill another player, takeover a continent, pop a continent, sweep the board. You also need methods to evaluate the cost of each of those actions, and find the best, or least costly, target for those actions.

Once your AI can accomplish those actions, then you get to the second phase: deciding if the action should be done or not. In my code, this is done with thresholds: numerical constants that vary from 0 to 100. For example, the AI might decide to take over a continent is the cost is less that 50% of its armies. Or, the AI will terminate another player with 5 cards if the cost is less that 95% of its armies.

Finding the best values for those thresholds is critical. In the beginning, I used a trial and error technique: try something that looks good, play lots of games with the other bots, increase or decrease the value, play more games and keep the modified value if the AI performs better. This has to done for each threshold, and is very labour intensive.

Genetic learning is simply a technique to automate this trial and error process. Instead of using constants in the code, each threshold value is made part of an array, called the base DNA array. Each element in the array is a gene.

The learning occurs in cycles of 250 games between 6 instances of the AI. One of those instances uses the base dna array for its thresholds. Each of the other AI instances uses a modified copy of the base DNA array, called a mutation. The mutation is created by randomly increasing or decreasing each threshold by a small value. After playing 250 games, the AI that won the most games writes its mutated DNA array to to a file: it then becomes the new base DNA for the next cycle. In effect, this genetic algorithm slowly searches for the optimal combination of threshold values.

This learning has to be done for each combination of settings: map size, cards and continent bonus increase. Each settings combination has its own DNA array. At the beginning of the game, a routine determines which DNA array to use depending on the game settings. The more granular your settings combinations are, the better your AI will be, at the cost of more learning time.

Well that's basically it. If you need more info feel free to throw more questions my way. As you can see, I enjoy this stuff.

User avatar
SunTzu
Lux Cartographer
Posts: 1586
Joined: Sat Jan 14, 2006 1:48 am
Location: Maryland

Post by SunTzu » Mon Aug 27, 2007 11:20 am

Thanks for the information Bertrand & GregM!

Post Reply