Under Development: VARbot

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

Under Development: VARbot

Post by varoadstter » Sat Feb 09, 2008 2:10 am

So, I've started to build out the underlying infrastructure of my bot and am enjoying the progress I'm making. To date, I have a full attack simulator built and I have two big parts of my scoring system finished - the Country Scoring and Player Statistics.

Here's the output from my player statistics class taken in the middle of a game. The numbers represent various statistically important bits of information that I will use to determine my bots overall standing within the game (which will be used to drive certain strategies).

Key:

mpi = Maximum Power Index, the largest power index of any player
a = total armies
ti = total income, comprised of the values, continent income, territory income, and card income (the value of the players cards at the next cash) divided by 3
bs = base score which is just the sum of armies and total income
pi = power index which is the log base 2 of the base score. This is useful in understanding in relative terms how much stronger one player is than another. If one player's pi is 1 and the other's is 2, then player 2 is twice as strong as player 1.
pi% = the percentage of the maximum pi for a player

Code: Select all

Total Player Stats
-----------------------------------------------------------------
mpi = 6.44
Hero : a(40) ti(23=20:3:0) bs(63) pi(5.98) pi%(92.77)
Bad Mutha : a(58) ti(29=13:5:11) bs(87) pi(6.44) pi%(100.00)
Tourette : a(25) ti(16=13:3:0) bs(41) pi(5.36) pi%(83.15)
VARoadstter : a(31) ti(31=26:3:2) bs(62) pi(5.95) pi%(92.41)
Pig Pen : a(34) ti(11=6:3:2) bs(45) pi(5.49) pi%(85.24)

Below is the output of my Country Score logic on the Classic map during the first turn (in later turns values go up as continent bonuses increase). In general, the higher the score, the more "desirable" my program will consider the country for ownership. It does not consider border countries for each country, only the borders of the continents so each country within a continent will have the same Country Score. There's a follow on class that I will get to soon concerning the scoring of clusters which will care about the borders of each country seperately. Anyway, here's the numbers at the start of the game:

Code: Select all

Total Country Score
Australia(Eastern Australia) = 0.500
Australia(New Guinea) = 0.500
Australia(Western Australia) = 0.500
Australia(Indonesia) = 0.500
South America(Argentina) = 0.250
South America(Brazil) = 0.250
South America(Peru) = 0.250
South America(Venezuela) = 0.250
Africa(South Africa) = 0.167
Africa(Congo) = 0.167
Africa(East Africa) = 0.167
Africa(Madagascar) = 0.167
Africa(North Africa) = 0.167
Africa(Egypt) = 0.167
North America(Central America) = 0.185
North America(Western United States) = 0.185
North America(Eastern United States) = 0.185
North America(Western Canada) = 0.185
North America(Ontario) = 0.185
North America(Quebec) = 0.185
North America(Alaska) = 0.185
North America(Northwest Territory) = 0.185
North America(Greenland - Nunavut) = 0.185
Europe(Iceland) = 0.179
Europe(Scandinavia) = 0.179
Europe(Great Britain) = 0.179
Europe(Western Europe) = 0.179
Europe(Northern Europe) = 0.179
Europe(Southern Europe) = 0.179
Europe(Ukraine) = 0.179
Asia(Middle East) = 0.117
Asia(India) = 0.117
Asia(Siam) = 0.117
Asia(Afghanistan) = 0.117
Asia(China) = 0.117
Asia(Ural) = 0.117
Asia(Siberia) = 0.117
Asia(Mongolia) = 0.117
Asia(Japan) = 0.117
Asia(Irkutsk) = 0.117
Asia(Kamchatka) = 0.117
Asia(Yakutsk) = 0.117
Here are the numbers for Classic Part Deux:

Code: Select all

Total Country Score
Australasia(Eastern Australia) = 0.600
Australasia(New Guinea) = 0.600
Australasia(Western Australia) = 0.600
Australasia(Indonesia) = 0.600
Australasia(Siam) = 0.600
South America(Argentina) = 0.500
South America(Brazil) = 0.500
South America(Peru) = 0.500
South America(Venezuela) = 0.500
Africa(South Africa) = 0.333
Africa(Congo) = 0.333
Africa(East Africa) = 0.333
Africa(Madagascar) = 0.333
Africa(North Africa) = 0.333
Africa(Egypt) = 0.333
Central America(Central America) = 1.000
USA(Western United States) = 0.444
USA(Eastern United States) = 0.444
USA(Alaska) = 0.444
Canada(Alberta) = 0.200
Canada(Ontario) = 0.200
Canada(Quebec) = 0.200
Canada(Northwest Territory) = 0.200
Canada(Newfoundland) = 0.200
Scandinavia(Greenland) = 0.333
Scandinavia(Iceland) = 0.333
Scandinavia(Scandinavia) = 0.333
Europe(Great Britain) = 0.240
Europe(Western Europe) = 0.240
Europe(Northern Europe) = 0.240
Europe(Southern Europe) = 0.240
Europe(Ukraine) = 0.240
Middle East(Middle East) = 0.750
Middle East(Afghanistan) = 0.750
India(India) = 1.000
Far East(China) = 0.556
Far East(Mongolia) = 0.556
Far East(Japan) = 0.556
Russia(Ural) = 0.350
Russia(Siberia) = 0.350
Russia(Irkutsk) = 0.350
Russia(Kamchatka) = 0.350
Russia(Yakutsk) = 0.350

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

Post by Bertrand » Sat Feb 09, 2008 8:03 am

Interesting. I especially like your pi. The math I use to compare players is definitively not as elegant.

We do not use the same logic to compare continents. Reaper's continent desirability index is, basically, the ratio between continent income and the number of borders. For example he considers North America to be the second most desirable continent, after Australia.

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

Post by 3DA » Sat Feb 09, 2008 11:12 am

Fascinating! It's great to be a fly on the wall for this process.

Bertrand - I find it really interesting that reaper rates NA over other continents. On paper, it makes sense. However, I think that from a Classic gameplay standpoint, NA is a deathtrap. I'd take ANY other continent over NA. Give me a nice setup in South America any day of the week.

Var - I love the math! Nice work!

Question for the both of you: when considering a continent, do your respective bots look at how many armies the other players have there? The general rule of strategy/etiquette is that if you outnumber each player individually in one continent, then you've got a legitimate shot at it. For example: if I have 4 armies in one country in SA, and one opponent has two, one has two, and another has one, I am "controlling" the continent in an etiquette/strategic sense, though I am outnumbered by the collective. Does that make sense?

Just trying to be helpful and lend some assistance from the gameplay world of humans. :)

User avatar
Scad
Lux Elder
Posts: 2521
Joined: Sun Aug 13, 2006 6:53 am
Location: Walking through the woods on a snowy evening
Contact:

Post by Scad » Sat Feb 09, 2008 11:17 am

I have only one objection:

It needs a cooler name.

Something like... TotalStomperOfAllThingsHumanAndDigital would be cool.

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

Post by varoadstter » Sat Feb 09, 2008 1:53 pm

Bertrand wrote:Interesting. I especially like your pi. The math I use to compare players is definitively not as elegant.

We do not use the same logic to compare continents. Reaper's continent desirability index is, basically, the ratio between continent income and the number of borders. For example he considers North America to be the second most desirable continent, after Australia.
Mine is nearly the exact same thing. I also divide the continent income for each country by the number of countries in the continent, since you have to own them all in order to get the income. This is only one way I will score countries though. When I write the custom logic for pickCountry() I will add in modifiers for the number of countries left, how many of the countries are owned by me, and other relevant bits to get the best pick I can.

Thanks for taking a look, everyone.

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

Post by Bertrand » Sat Feb 09, 2008 7:02 pm

3DA wrote:Bertrand - I find it really interesting that reaper rates NA over other continents. On paper, it makes sense. However, I think that from a Classic gameplay standpoint, NA is a deathtrap. I'd take ANY other continent over NA.
What's wrong with NA? I'm not a very good player, so to me NA looks like a good deal: only 3 borders, and lots of income. What's not to like?

Beware: any information you give me might be incorporated in a hypothetical future version of Reaper. You will be considered a traitor by the other humans.
3DA wrote:when considering a continent, do your respective bots look at how many armies the other players have there? The general rule of strategy/etiquette is that if you outnumber each player individually in one continent, then you've got a legitimate shot at it. For example: if I have 4 armies in one country in SA, and one opponent has two, one has two, and another has one, I am "controlling" the continent in an etiquette/strategic sense, though I am outnumbered by the collective. Does that make sense?
Reaper doesn't think like that. He doesn't care if the armies in a target continent belong to many, or one player. As long as he has the numbers to take it over and defend it, he will go for it if it makes strategic sense. Hmmm, is this what you humans call asshatish behavior?

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

Post by varoadstter » Sat Feb 09, 2008 11:44 pm

Bertrand wrote:
3DA wrote:when considering a continent, do your respective bots look at how many armies the other players have there? The general rule of strategy/etiquette is that if you outnumber each player individually in one continent, then you've got a legitimate shot at it. For example: if I have 4 armies in one country in SA, and one opponent has two, one has two, and another has one, I am "controlling" the continent in an etiquette/strategic sense, though I am outnumbered by the collective. Does that make sense?
Reaper doesn't think like that. He doesn't care if the armies in a target continent belong to many, or one player. As long as he has the numbers to take it over and defend it, he will go for it if it makes strategic sense. Hmmm, is this what you humans call asshatish behavior?
It's strategic elements such as this that make me look forward to working with 3DA (others?) on this once the base strategy is in place. I can see that from a human player's standpoint bots don't play the way they'd "like" them to play. There are certain ethical and defacto game rules that are part of playing with other people that simplay aren't backed up in a purely numerical sense. Untimately, it may be impossible to have a bot both a) play as humans play and b) win a lot. From a bots perspective, suboptimal is a recipie for death.

User avatar
guest
Luxer
Posts: 189
Joined: Fri Dec 17, 2004 9:17 pm
Location: Southern NH
Contact:

Post by guest » Sun Feb 10, 2008 1:34 am

Actually there is a huge advantage to participating in the suboptimal social / mind tricks that users do. The lack of this is part of what drives bot-first.
Until the bot makers know what players do, there's no way for the bot to respond appropriately.

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

Post by Bertrand » Sun Feb 10, 2008 7:40 am

You've got a good point there, guest.

When I train Reaper, I always use other bots and previous versions of Reaper. Bots don't have any sense of revenge, so the right strategy is to use the numerically optimal move in all cases.

This strategy falls apart when playing against many humans, because they remember and hold grudges. By pursuing the optimal moves, Reaper probably makes too many enemies, and ultimately that is counter-productive.

I'll put this in my to-do list for the hypothetical next version. I could make him a little less aggressive in games with multiple humans.

User avatar
guest
Luxer
Posts: 189
Joined: Fri Dec 17, 2004 9:17 pm
Location: Southern NH
Contact:

Post by guest » Sun Feb 10, 2008 12:04 pm

As an example of a situation, There two weak players which one do you kill, the weakest or the one who attacked the weakest last turn?

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

Post by 3DA » Mon Feb 11, 2008 11:45 am

Boy, this is a great thread. So much to reply to! I don't know where to start! :)

To Bertrand, about North America: statistically it looks good. In practice ... let me see if I can enumerate some points why it doesn't work. It's hard to sum up, because I feel like I play the game a lot by feel and instinct and, though those things may be connected to statistics and facts, I have a hard time making those connections. This is why this conversation is so good for my game, actually: I'm learning how to quantify winning strategy. :)

1. It's nearly impossible, in a game of classic, to take North America in a timely enough fashion to make you a contender. There are just too many countries, and, for other players, there is only one exit: through Alaska. 9 times out of 10 you do not have enough armies to take the whole continent by force and still be in the game. So you have to wait until everyone else farms out/exits the continent. They cannot leave through SA because someone has taken that, and they cannot exit through EU because someone has taken that: the only way to get out is through Alaska to Asia.

2. It usually takes all your armies (and sometimes your first cash) to take North America. This leaves you without a satellite in Asia, thus leaving you without A) a weapon to hit other players B) a strong force outside of the continent you're holding, making you more difficult to kill for pathing/distribution reasons.

3. The players in Europe and SA have two ways to hit you: through Alaska with their main satellite force, and through their adjoining countries. It makes you really easy to kill for either of those players.

4. Because NA commands a lot of income, other players don't really like someone holding it for an extended amount of time. And, because it's so sprawling, it is really hard to defend. Europe, though it has more borders technically, is much easier to hold because the countries all border one another: if someone pops a border somewhere, it's easy to have reinforcements on hand to retailiate/retake.

Does all this make sense? These are just some reasons.

SO MUCH MORE TO WRITE ABOUT!! I'll be coming back to this thread to talk more about strategy. Thanks guys!

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

Post by varoadstter » Thu Feb 14, 2008 12:12 am

Ok. I think my infrastructure classes are now finished. I have just completed and tested my Shape Scoring (referred to as Clusters in the API) and Board Scoring. Now that I can objectively evaluate when one "shape" is superior to another I have an idea of how to improve my efficiency when expanding my territory. Add to that the ability to score a board instance and I've got the Holy Grail of metrics needed to run various scenarios through Monte Carlo simulations to determine which course of action yields the best results. Here's the output from the new code as taken from one turn playin on the Roman Empire map:

Code: Select all

Total Shape Scores = 2.000
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Egypt VI code:16 continent:19 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Bostra code:23 continent:20 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Africa V code:33 continent:24 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 2.000
Average country score bonus = 0.000

	-CountryCluster size:2 countries:
	-Country name:Caesariensis I code:49 continent:5 owner:0 armies:1-
	-Country name:Tingis code:51 continent:5 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Emerita Aug. code:56 continent:1 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Bracara code:58 continent:3 owner:0 armies:1- end of cluster-
================================================
Shape(score = 1.333)
Border size = 9.000
Average country score bonus = 0.111

	-CountryCluster size:12 countries:
	-Country name:Narbonensis code:74 continent:7 owner:0 armies:1-
	-Country name:Massilia code:75 continent:7 owner:0 armies:3-
	-Country name:Lugdunum code:76 continent:10 owner:0 armies:1-
	-Country name:Alpine Prov. code:100 continent:11 owner:0 armies:3-
	-Country name:Upper Germania code:90 continent:13 owner:0 armies:9-
	-Country name:Genua code:101 continent:0 owner:0 armies:3-
	-Country name:Augustodunum code:77 continent:10 owner:0 armies:1-
	-Country name:Raetia code:118 continent:11 owner:0 armies:2-
	-Country name:Lutetia code:78 continent:10 owner:0 armies:5-
	-Country name:Lower Germania code:89 continent:13 owner:0 armies:1-
	-Country name:Bononia code:105 continent:0 owner:0 armies:3-
	-Country name:Mediolanum code:103 continent:0 owner:0 armies:3- end of cluster-
================================================
Shape(score = 0.333)
Border size = 1.000
Average country score bonus = 0.167

	-CountryCluster size:2 countries:
	-Country name:Scandia I code:92 continent:15 owner:0 armies:1-
	-Country name:Scandia Isle I code:187 continent:15 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.333)
Border size = 2.000
Average country score bonus = 0.111

	-CountryCluster size:3 countries:
	-Country name:Capua code:109 continent:0 owner:0 armies:8-
	-Country name:Neapolis code:110 continent:0 owner:0 armies:3-
	-Country name:Tarentum code:111 continent:0 owner:0 armies:3- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Arabis II code:115 continent:18 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 2.000
Average country score bonus = 0.000

	-CountryCluster size:2 countries:
	-Country name:Sardis code:142 continent:16 owner:0 armies:1-
	-Country name:Lycia code:147 continent:16 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Trapezus code:152 continent:16 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Panticapaeum code:158 continent:15 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Albania code:159 continent:15 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Tyana code:169 continent:16 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Dura Europus code:171 continent:23 owner:0 armies:1- end of cluster-
================================================
Shape(score = 0.000)
Border size = 1.000
Average country score bonus = 0.000

	-CountryCluster size:1 countries:
	-Country name:Balearic Isles II code:180 continent:3 owner:0 armies:1- end of cluster-
================================================

BoardScore = 6.073
The next step is to build modules that efficiently execute tactical moves (kill player, take continent, etc).

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

Post by 3DA » Thu Feb 14, 2008 2:12 pm

varoadstter wrote:Ok. I think my infrastructure classes are now finished. I have just completed and tested my Shape Scoring (referred to as Clusters in the API) and Board Scoring. Now that I can objectively evaluate when one "shape" is superior to another I have an idea of how to improve my efficiency when expanding my territory. Add to that the ability to score a board instance and I've got the Holy Grail of metrics needed to run various scenarios through Monte Carlo simulations to determine which course of action yields the best results.
Sounds very cool, Varo!

Could you explain to me this idea of "shape scoring?" What is it exactly about shape that is being evaluated? What's a "better" shape?

What I'm trying to get a handle on is how the AI will go through the process of "seeing" the board and "deciding" where and how to expand and place. The AI cannot look at the board and see that some places are dead ends and thus good places to try and hole up, and some places are out in the middle of nowhere and are thus strategically almost useless. Can it?

I'm trying to think of how I go about starting a game; what criteria I use to place and attack, and how much of that is based on quantifiable data that a bot can understand. The idea of a "cluster" with a "shape" I understand, in that if I have a lot of contiguous countries at start it's something significant that I may be able to use to my advantage, but there are so many variables about that it's hard for me to say anything about what I'd do without looking at the rest of the board. It may be that the only thing a "cluster" is good for is to consolidate all the armies in that cluster into one group and just leave it there while you concentrate on taking some other portion of the board entirely. For instance, on the classic map, it's good to have a big chunk of men in Asia. They will not be useful until round 4 or 5, really, though, so you have to let them sit there while you concentrate on trying to take a continent.

I hope this is not making more work for you! I'm just really intrigued with the process of building an AI and would like to know more. And I would be proud to help construct a bot that is as formidable as Reaper, and so that's motivating me, too. :)

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

Post by varoadstter » Thu Feb 14, 2008 4:05 pm

In my code, one shape is superior to another for one of two reasons:

it contains countries that have no hostile borders
it wholly contains a continent (that provides a bonus)

To assert the validity of this, consider an example game with these rules (to eliminate other considerations):

Map consists of a 9x9 grid of squares. Each 3x3 square is considered a continent with a bonus of 3.

Obviously, a shape that encompases an entire continent is more desirable than one equally "shaped" that does not due to the fact that it provides a boost to income.

The "shape" in the very middle of the map is less desirable than one on an edge which is less desirable than one in a corner because the amount of exposed border.

Center square, border size = 8
Side square, border size = 7
Corner square, bordersize = 5

The continents in the corner require fewer defensive armies in general since the are less exposed. My shape scoring algorithm attempts to provide a score which quantifies these things.

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

Post by 3DA » Thu Feb 14, 2008 5:36 pm

Brilliant! So the AI is, in fact, able to sense the "edges" of the map. Also, the AI will be able to "sense" how large and area it's holding and how exposed it is.

So this, coupled with the statistic that rates continents based on the amount of income they could potentially generate, creates a "desirability" number based on vulnerability vs. reward. Then the AI can compare that number to its ability to take/hold that area and make a "decision" to go for it or not. Yes?

I like it.

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

Post by varoadstter » Thu Feb 14, 2008 9:06 pm

3DA wrote:Brilliant! So the AI is, in fact, able to sense the "edges" of the map. Also, the AI will be able to "sense" how large and area it's holding and how exposed it is.

So this, coupled with the statistic that rates continents based on the amount of income they could potentially generate, creates a "desirability" number based on vulnerability vs. reward. Then the AI can compare that number to its ability to take/hold that area and make a "decision" to go for it or not. Yes?

I like it.
Yes, I think you've got the idea.

Now, to take it a step further, my bot can decide it's actions one of two ways:
1 - it decides on tactics based on preprogrammed behaviors
2 - it runs simulated scenarios and compares the board score of each after completion and does the one that scores highest

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

Post by Bertrand » Thu Feb 14, 2008 9:51 pm

3DA wrote:To Bertrand, about North America: statistically it looks good. In practice ...
1. It's nearly impossible, in a game of classic, to take North America in a timely enough fashion to make you a contender.
... snip ...
Does all this make sense? These are just some reasons.
It does make sense. In fact, this probably explains why, while testing Reaper I found that it was not worth it to try to get continents in classic 4-6-8-10-15 0% games. This is true for all continents, not just NA.

I never did find a way for Reaper to participate in the elaborate dance humans perform in the beginning moves, attributing continents and farming out of the way. So in high cards games, Reaper remains a nomad, waiting for a victim to kill. This strategy works pretty well, but it is not quite good enough to compete with the best players.

Reaper does like NA however, when the continent bonus increase is 10% or more.

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

Post by 3DA » Fri Feb 15, 2008 1:01 am

Bertrand wrote:This strategy works pretty well, but it is not quite good enough to compete with the best players.
It works well enough, man - on almost any map.

It's funny - I take a kind of perverse pleasure in watching people play with Reaper for the first time. I warn them: "Reaper has income," or "Reaper's going to win if you let it set up like that." Of course, they don't listen: they think, the bot doesn't have any income, it's just one pile of armies, how can it win? Then, after the bot cashes and kills three of them and the board is 85% black, there is this stunned silence in chat. Then someone goes, "damn, what happened?" :)

When I train on classic or for a MOTW offline, I always play with at least two teaming Reapers.

I think there is a way to replicate that give and take at the beginning of the game in an AI. The decisions are, at heart, based on quantitative evidence. The real trick would be getting the humans in the game to recognize that the bot was trying to farm for them, and getting it to respect it the same way they would another human player. You might actually be able to do something with chat posts when/if the bot did actually farm. I know there is one bot that asks humans to farm: is it Nef? I wonder if Preach has programmed the bot to remember whether a player farmed for it or not.

Interesting discussion! Again, thanks for letting me participate.

User avatar
Scad
Lux Elder
Posts: 2521
Joined: Sun Aug 13, 2006 6:53 am
Location: Walking through the woods on a snowy evening
Contact:

Post by Scad » Fri Feb 15, 2008 8:40 am

BotOfDoom asks for farming. I'm pretty sure it can't remember. But if someone can figure out a bot to participate in the "early game dance" that Bertrand describes, it could be VERY interesting.

User avatar
guest
Luxer
Posts: 189
Joined: Fri Dec 17, 2004 9:17 pm
Location: Southern NH
Contact:

Post by guest » Fri Feb 15, 2008 5:32 pm

The only way now to check for farming would b take a snapshot (copy the country list) of the map then when its the bots turn take another and compare them to look for changes. I was actually thinking about doing this only it won't show any thing if one player takes over a county thats already been taken over. Not sure how to handle that. Its the closest I can come to the bot seeing what's going on. Maybe use the message function as a trigger to take a snapshot. To be really useful snapshot would be taken before after placing armies and before & after fortify.

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

Post by varoadstter » Wed Feb 20, 2008 11:22 pm

Finished up the "boring" part of this today. Next is tactics and strategy.

I wanted to develop a way to have placeArmies, attackPhase, and fortifyPhase be controlled in a coordinated manner. To do this I preplan my bot's entire turn during the cardsPhase. I implemented a CommandQueue as a means of storing individual commands for placing my armies, attacking countries, and fortifying when those phases commence. In the event that I earn another cash, the process starts over from the beginning. This may be good or not good but I don't really know yet. I'll game test it and find out if it's a good idea.

Since I now have basically all the plumbing I wanted to make my bot conduct its turns, I will probably work towards my alpha release of the bot sometime around the first of March. Even though I have written absolutely none of the planning logic yet, I am confident that the combination of infrastructure, available metrics, and common sense tactical planning will yield a bot that will be far better than most that are available now. There's elements of strategy in each of Dustin's example bots which are good tutorials on how to accomplish specific tactical goals. By combining those tactics with the full array of metrics, I will create strategic plans that take all game factors into consideration. Bottom line - this bot should perform at least adequately on every map right out of the box.

Just for the hell of it, here's some other metrics of what I have so far:

Number of java files: 11
Number of classes and interfaces: 20
Total lines of source code: 1272
Total size of class files: 55.3 KB

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 » Thu Feb 21, 2008 12:20 am

Once this bot is created, I want to see a VARbot Reaper showdown

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

Post by GregM » Thu Feb 21, 2008 2:27 am

Cool stuff, varoadstter! At one point I considered making a successor to BotOfDoom based on some of the principles you're using, but gave up on making a whole new bot from scratch. Is there any chance you're willing to make your code public, so others can play around with it?
Last edited by GregM on Thu Feb 21, 2008 12:57 pm, edited 1 time in total.

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

Post by varoadstter » Thu Feb 21, 2008 8:11 am

Good question.

Since my ultimate goal is to provide high quality bots to this community and I'm not as driven to be the guy with the #1 bot I think my answer to this will be yes but I'm not sure yet. I think if I were to open it up I'd need to do some work to decouple parts of it so that people could use only the parts they want and ignore the rest. It could also use some documentation in order to help botmakers understand exactly why certain things are done they way they are although I am less worried about this than providing usable modules. Just from what I have I probably have 4 distinct modules: attack simulation, metrics, command processing, and planning. I would ideally like to make it so that these pieces can be used without also requiring the other pieces to be present. Then it would be possible for a botmaker to take, say, the command processing module by itself and implement their own planning module.

Of course, I develop software for a living so I'm prone to think this way. There's probably some who would just like to tinker around with what is there now and see what it does and how it works.

To date, I think I've probably spent around 30-40 hours designing and implementing my framework. Some parts are solid as a rock, some are less so. Now that I'm at the point of implementing pure strategy I suspect I have at least as many hours to go as I have so far in getting the bot to play well. Until this pays off by producing an opponent that people respect and/or like playing with it's probably too soon to get too hyped up about all of it.

When this bot is truly release worthy, I still have a lot left to work on. My bot has no knowledge of team play. It doesn't know how to interact with human players. It doesn't have any means of being tuned through gameplay (which would make it play specific maps better over time). I'd like to be able to do what Bot-O-Matic does and provide a means for players to configre the bot at runtime to have some specific behaviors.

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

Post by Bertrand » Thu Feb 21, 2008 12:56 pm

varoadstter wrote:In the event that I earn another cash, the process starts over from the beginning. This may be good or not good but I don't really know yet. I'll game test it and find out if it's a good idea.
This will work, but it may not give you the best plan. In particular, you might not see all the multi-kills with intermediate cashing. In Reaper, I do the planning only once per turn, and the planning incorporates the intermediate cashing/placing.
varoadstter wrote:Bottom line - this bot should perform at least adequately on every map right out of the box.
I don't doubt it. Knowing what I do now, if I had to rewrite Reaper I would follow an approach similar to yours. The one thing I am curious about is the performance of your bot: how long will it have to think before having simulated enough possibilities to make a reasonably good move?

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

Post by varoadstter » Thu Feb 21, 2008 1:50 pm

Bertrand wrote:This will work, but it may not give you the best plan. In particular, you might not see all the multi-kills with intermediate cashing. In Reaper, I do the planning only once per turn, and the planning incorporates the intermediate cashing/placing.
Yes. This is exactly what concerns me about this approach. At least I can give it a try and decide for myself if it can effectively abandon current plans when a new cash occurs. I think I can mitigate this somewhat by prioritizing whom I kill first. It may just end up being a recursive way of accomplishing the same goal.
Bertrand wrote:I don't doubt it. Knowing what I do now, if I had to rewrite Reaper I would follow an approach similar to yours. The one thing I am curious about is the performance of your bot: how long will it have to think before having simulated enough possibilities to make a reasonably good move?
That's encouraging. It gives me some reason to believe I've got a solid plan for putting this together if you believe it sounds plausible. As for performance, I am going to have to wait and see on this. There is a chance I can short-circuit my plans if I find that my turn time is running low (there's a value I can check for that) so I don't just go off in la la land and take a half hour to think about what is optimum. In fact, I think it's reasonable to assume the bot can do the basics at very fast speeds. The big think will only happen when the bot is in a position where it has several viable ways to proceed and it's just searching for the best of the best. It may be that I can run scenarios that give me good scores within a few seconds and just say "that's far enough" since my turn time is getting low. The first casualty here would be in cases where I take almost my whole turn to figure out how to kill an opponent, and then complete that work, get a new cash, and then not have time to do more than deploy the new armies. At least the bot will have done something constructive during its turn.

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

Post by GregM » Thu Feb 21, 2008 4:29 pm

varoadstter wrote:At least I can give it a try and decide for myself if it can effectively abandon current plans when a new cash occurs.
What about having the bot abandon all its past plans and reassess the situation after *every* tactical move? It's always possible that the continent takeover/player kill/whatever was a success, but you lost more armies than you expected and need to find a new plan of action.

Of course, this might run into the other problem Bertrand mentioned regarding excessive use of time.

User avatar
guest
Luxer
Posts: 189
Joined: Fri Dec 17, 2004 9:17 pm
Location: Southern NH
Contact:

Post by guest » Thu Feb 21, 2008 5:31 pm

You don't think an attack though every step when you go for a kill do you? You check to see if there are enough armies with access. Its the separation between strategic and tactical thinking. You can quickly check your options without running through a full sim.

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

Post by Bertrand » Thu Feb 21, 2008 6:26 pm

guest wrote:You don't think an attack though every step when you go for a kill do you? You check to see if there are enough armies with access. Its the separation between strategic and tactical thinking. You can quickly check your options without running through a full sim.
I think it's necessary to go through every step when evaluating a kill. If you don't, the bot will often half-kill it's victim. Let me give you an example:

The bot has two groups A and B that can reach the victim, and since both groups are smaller than the victim, both have to be used. What often happens is that after using group A, group B will be unable to reach the victim. If you do not fully simulate the kill, you will fail to see this blocking.

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

Post by varoadstter » Fri Feb 22, 2008 2:46 pm

GregM wrote:What about having the bot abandon all its past plans and reassess the situation after *every* tactical move? It's always possible that the continent takeover/player kill/whatever was a success, but you lost more armies than you expected and need to find a new plan of action.

Of course, this might run into the other problem Bertrand mentioned regarding excessive use of time.
I understand why this sounds like a potential solution but I won't be able to go that way for a couple reasons:
  • I preplan the turn (placement of armies, attacks, and fortification) during the cardsPhase. Once I start attacking, I can't return to placement without cashing.

    It will be very expensive.

    It's mostly unnecessary. 95% of the time, there would be no reason to change plans after I begin, the exception being when I take a far greater loss during an attack than my simulations indicated I would. In the case that I'm in that situation, I will just stop attacking for now. Later I will probably go back to planning and redo the attack and fortify portions of the plan if I abort the original plan.

Post Reply