Chesslike.py -- A new AI, stronger than the standard AI
Moderator: Forum Moderators
-
MSchmahl
- Code Contributor
- Posts: 18
- Joined: December 28th, 2006, 12:06 pm
- Location: To the west and north
Chesslike.py -- A new AI, stronger than the standard AI
This is my attempt at a 'chess-like' AI. All moves are motivated by an underlying evaluation function. The actual eval function doesn't need to be coded, because moves can be scored and ranked based on the incremental change in the evaluation. Unlike a chess-playing program, though, this program does no lookahead, because the branching factor is prohibitively high (potentially in the thousands), and because then the script would have to create an internal model of the game state.
Despite the lack of any lookahead, I still consider this AI to be chess-like because it evaluates every possible move and attack, even those that are obviously (to a human) bad. How can a computer know that these are bad moves unless it actually checks?
The evaluation function is:
(1) side_score = village_score
+ sum(unit_score, over all units)
+ positional_score
The value of a unit can be highly subjective, but to simplify, assume that any level-1 unit is just as valuable as any other level-1 unit. Specifically, the value of a unit will be:
(2) unit_score = (1 + level + %xp)(1 + %hp)
Leaders are be considered three levels higher than their actual level. So a freshly-recruited level-1 unit is worth 4.0 points. And a level-2 unit with half its hitpoints remaining, but halfway to level 3, is worth 3.75 points.
One question is: How much is a village worth, compared to a (typical) unit? A typical unit is worth 15 to 20 gold, because that is how much we paid for it. A village is worth two or three gold *per turn* as long as it is held. (The village is worth three gold when it offsets a unit's upkeep.) So we must make some assumptions as to the value of a present gold piece, compared to a future gold piece. Assume a decay rate of 1.5 (i.e. a gold piece one turn from now is worth two-thirds of a gold piece now). This makes the present value of a village equal to twice its income. If we set the value of a typical unit at 16 gold, we get that an upkeep-offsetting village is worth 1.5 points, and a supernumerary village is worth 1.0 points. For simplicity, the value of each village is set at 1.0.
(3) village_score = number of villages
The positional score is the most interesting term of equation (1), because that, more than anything else, will guide the AI's behavior.
First, we want the AI to expand to capture villages. So, for each unit, it is scored based on how far it is from the nearest unowned or enemy village. If the distance is zero, the unit has actually captured the village, so in that limit, the value should be equal to the village value. As the distance approaces infinity, the score should tend toward zero. This suggests something like:
(4) village_proximity = c / (c + distance)
I have selected c to be equal to equal to the unit's movement. This means that (approximately) a unit one turn away from capturing a village gets 0.5 points; two turns, 0.33 points, etc. Although an exponential relationship would be more accurate, exponentiation is expensive, and better avoided, since thousands of moves are evaluated per turn.
Second, we want units to stand on defensive terrain when within range of the enemy. The 'right' way to do this would be to count up all the potential attackers at the destination square, see how much damage they might do, and score the move based on how much damage would be dealt/prevented. Again, this is much too slow. I have found a reasonable approximation is:
(5) exposure_penalty = -defense_modifier / 10
Maybe much too simple, but easy to calculate! In future editions, perhaps I should take into account how damaged the unit is, or at least make some attempt to count the attackers.
Third, we want units to heal when damaged or poisoned. Referring to equation (2), we can see that the value of healing is:
(6) healing_score = healing / max_hitpoints * (1 + level + %xp)
We consider poison, which does 8 damage *per turn*, to be equivalent to 16 points of actual damage, for the same reason a village's real value is twice its income (see above).
Fourth, we want units to guard villages if the enemy is in range to take them. If, by stationing a unit on a village, we prevent the enemy from taking it, we have prevented a 2-point swing in the enemy's favor. Again considering a decay rate of 2/3 per turn, this means the garrison value is 4/3. But since there is no guarantee that our garrison will be successful (perhaps the enemy will take the village anyway; perhaps it is not possible to garrison all threatened villages), we will cut this in half.
(7) garrison_score = 2/3
Fifth, we want our leader to stay near a keep. Otherwise, any gold we might have accumulated will be wasted. And finally, we want units to move toward the enemy leader. These are accomplished by treating keeps as if they were unowned villages (for our leader), and the enemy leader as if it were a village (for everyone else).
This should be all that is required to play a decent game of Wesnoth. This AI scores quite well against the Wesnoth default AI, which may be surprising, because it uses no sophisticated tools. There is no attempt to use any of the path-finding tools made available by the API (which would be too slow to be used thousands of times every turn). There is no attempt to use combination attacks (meaning, that even though none of several units can favorably attack a certain target, if they all attack in the same turn, the result is likely to be favorable). No attempt is made to assign units individually to targets.
Some bad behaviors may result from these shortcomings:
If the map is maze-like, or simply has a few corners surrounded by impassable terrain, units may get stuck. On Cynsaun Battlefield, for example, a group of units got stuck in the middle of the river, trying to capture a village on the other side of the deep-water hexes.
An enemy unit may get completely surrounded by friendly units, who are weak in comparison to the enemy, and our AI will make no attempt to kill the enemy unit. (Think six Wolf Riders surrounding an Orcish Grunt.) Usually one or more of these units will find something else to do, allowing a few Archers to take their place and start to wear down the Grunt. Or the Grunt will attack, getting damaged in the process, and creating a chance-to-kill for one of the Wolves.
If there is an unoccupied village in a corner of the map, our AI will send every unit that is closer to the village than any other, to that village. Often, only one unit is necessary. Thus, harassing villages with scouts may be a much more viable strategy against this AI than against human players, or against the default AI.
For those interested in results, I have set up a tournament between my AI and the default AI. The tournament consists of one match on each of the mainline two-player maps (except Wesbowl, naturally). In each map, each opponent is allowed to be player 1 once. If there is no decision after two games, two more games are played, repeating as necessary until one opponent has won the match. All games are played with a 50-turn limit, 2 gold per village, 70% experience, and no fog. (I think there is a bug (feature?) that AIs ignore fog, so I disabled it to improve the observer's (my) experience.) Factions are chosen randomly.
Edit: Added a workaround for a bug in the Python API.
Edit: Fixed a bug that would crash the script if all keeps are occupied.
Edit: Fixed a bug, introduced by the above workaround, that prevented the AI from attacking without moving.
Edit: Removed discussion from
Despite the lack of any lookahead, I still consider this AI to be chess-like because it evaluates every possible move and attack, even those that are obviously (to a human) bad. How can a computer know that these are bad moves unless it actually checks?
The evaluation function is:
(1) side_score = village_score
+ sum(unit_score, over all units)
+ positional_score
The value of a unit can be highly subjective, but to simplify, assume that any level-1 unit is just as valuable as any other level-1 unit. Specifically, the value of a unit will be:
(2) unit_score = (1 + level + %xp)(1 + %hp)
Leaders are be considered three levels higher than their actual level. So a freshly-recruited level-1 unit is worth 4.0 points. And a level-2 unit with half its hitpoints remaining, but halfway to level 3, is worth 3.75 points.
One question is: How much is a village worth, compared to a (typical) unit? A typical unit is worth 15 to 20 gold, because that is how much we paid for it. A village is worth two or three gold *per turn* as long as it is held. (The village is worth three gold when it offsets a unit's upkeep.) So we must make some assumptions as to the value of a present gold piece, compared to a future gold piece. Assume a decay rate of 1.5 (i.e. a gold piece one turn from now is worth two-thirds of a gold piece now). This makes the present value of a village equal to twice its income. If we set the value of a typical unit at 16 gold, we get that an upkeep-offsetting village is worth 1.5 points, and a supernumerary village is worth 1.0 points. For simplicity, the value of each village is set at 1.0.
(3) village_score = number of villages
The positional score is the most interesting term of equation (1), because that, more than anything else, will guide the AI's behavior.
First, we want the AI to expand to capture villages. So, for each unit, it is scored based on how far it is from the nearest unowned or enemy village. If the distance is zero, the unit has actually captured the village, so in that limit, the value should be equal to the village value. As the distance approaces infinity, the score should tend toward zero. This suggests something like:
(4) village_proximity = c / (c + distance)
I have selected c to be equal to equal to the unit's movement. This means that (approximately) a unit one turn away from capturing a village gets 0.5 points; two turns, 0.33 points, etc. Although an exponential relationship would be more accurate, exponentiation is expensive, and better avoided, since thousands of moves are evaluated per turn.
Second, we want units to stand on defensive terrain when within range of the enemy. The 'right' way to do this would be to count up all the potential attackers at the destination square, see how much damage they might do, and score the move based on how much damage would be dealt/prevented. Again, this is much too slow. I have found a reasonable approximation is:
(5) exposure_penalty = -defense_modifier / 10
Maybe much too simple, but easy to calculate! In future editions, perhaps I should take into account how damaged the unit is, or at least make some attempt to count the attackers.
Third, we want units to heal when damaged or poisoned. Referring to equation (2), we can see that the value of healing is:
(6) healing_score = healing / max_hitpoints * (1 + level + %xp)
We consider poison, which does 8 damage *per turn*, to be equivalent to 16 points of actual damage, for the same reason a village's real value is twice its income (see above).
Fourth, we want units to guard villages if the enemy is in range to take them. If, by stationing a unit on a village, we prevent the enemy from taking it, we have prevented a 2-point swing in the enemy's favor. Again considering a decay rate of 2/3 per turn, this means the garrison value is 4/3. But since there is no guarantee that our garrison will be successful (perhaps the enemy will take the village anyway; perhaps it is not possible to garrison all threatened villages), we will cut this in half.
(7) garrison_score = 2/3
Fifth, we want our leader to stay near a keep. Otherwise, any gold we might have accumulated will be wasted. And finally, we want units to move toward the enemy leader. These are accomplished by treating keeps as if they were unowned villages (for our leader), and the enemy leader as if it were a village (for everyone else).
This should be all that is required to play a decent game of Wesnoth. This AI scores quite well against the Wesnoth default AI, which may be surprising, because it uses no sophisticated tools. There is no attempt to use any of the path-finding tools made available by the API (which would be too slow to be used thousands of times every turn). There is no attempt to use combination attacks (meaning, that even though none of several units can favorably attack a certain target, if they all attack in the same turn, the result is likely to be favorable). No attempt is made to assign units individually to targets.
Some bad behaviors may result from these shortcomings:
If the map is maze-like, or simply has a few corners surrounded by impassable terrain, units may get stuck. On Cynsaun Battlefield, for example, a group of units got stuck in the middle of the river, trying to capture a village on the other side of the deep-water hexes.
An enemy unit may get completely surrounded by friendly units, who are weak in comparison to the enemy, and our AI will make no attempt to kill the enemy unit. (Think six Wolf Riders surrounding an Orcish Grunt.) Usually one or more of these units will find something else to do, allowing a few Archers to take their place and start to wear down the Grunt. Or the Grunt will attack, getting damaged in the process, and creating a chance-to-kill for one of the Wolves.
If there is an unoccupied village in a corner of the map, our AI will send every unit that is closer to the village than any other, to that village. Often, only one unit is necessary. Thus, harassing villages with scouts may be a much more viable strategy against this AI than against human players, or against the default AI.
For those interested in results, I have set up a tournament between my AI and the default AI. The tournament consists of one match on each of the mainline two-player maps (except Wesbowl, naturally). In each map, each opponent is allowed to be player 1 once. If there is no decision after two games, two more games are played, repeating as necessary until one opponent has won the match. All games are played with a 50-turn limit, 2 gold per village, 70% experience, and no fog. (I think there is a bug (feature?) that AIs ignore fog, so I disabled it to improve the observer's (my) experience.) Factions are chosen randomly.
Code: Select all
Map W-L-D %Win Match result
Blitz 2-0-0 100 Win
Caves of the Basilisk 4-2-0 67 Win
Charge 3-1-0 75 Win
Cynsaun Battlefield (1gpv) 2-0-0 100 Win
Den of Onis 4-2-0 67 Win
Hamlets 2-0-0 100 Win
Hornshark Island 0-2-0 0 Loss
Meteor Lake 2-0-0 100 Win
Sablestone Delta 2-0-0 100 Win
Silverhead Crossing 3-1-0 75 Win
Sulla's Ruins 2-0-0 100 Win
** Overall 25-8-0 76 10 Wins, 1 Loss (91%)
Edit: Fixed a bug that would crash the script if all keeps are occupied.
Edit: Fixed a bug, introduced by the above workaround, that prevented the AI from attacking without moving.
Edit: Removed discussion from
Code: Select all
tags, uploaded script as an attachment.- Attachments
-
chesslike.py.txt- To use, place in data/ais, and remove the .txt suffix
- (19.92 KiB) Downloaded 1036 times
Last edited by MSchmahl on March 28th, 2007, 12:07 am, edited 4 times in total.
congrats! nice python bot
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
-
Wintermute
- Inactive Developer
- Posts: 840
- Joined: March 23rd, 2006, 10:28 pm
- Location: On IRC as "happygrue" at: #wesnoth-mp
-
MSchmahl
- Code Contributor
- Posts: 18
- Joined: December 28th, 2006, 12:06 pm
- Location: To the west and north
This is buried at the end of the initial comments/essay, so I've cut it out for easy reference:Wintermute wrote:how does this fare when matched up against the current AI?
Code: Select all
## Map W-L-D %Win Match result
## Blitz 2-0-0 100 Win
## Caves of the Basilisk 4-2-0 67 Win
## Charge 3-1-0 75 Win
## Cynsaun Battlefield (1gpv) 2-0-0 100 Win
## Den of Onis 4-2-0 67 Win
## Hamlets 2-0-0 100 Win
## Hornshark Island 0-2-0 0 Loss
## Meteor Lake 2-0-0 100 Win
## Sablestone Delta 2-0-0 100 Win
## Silverhead Crossing 3-1-0 75 Win
## Sulla's Ruins 2-0-0 100 Win
## ** Overall 25-8-0 76 10 Wins, 1 Loss (91%)
-
Wintermute
- Inactive Developer
- Posts: 840
- Joined: March 23rd, 2006, 10:28 pm
- Location: On IRC as "happygrue" at: #wesnoth-mp
Interesting. I had skimmed over that part to look at the code.MSchmahl wrote: ## ** Overall 25-8-0 76 10 Wins, 1 Loss (91%)
Do we just put this script in /userdata/data/ais, or is it more complicated than that?
"I just started playing this game a few days ago, and I already see some balance issues."
-
wsultzbach
- Posts: 245
- Joined: November 28th, 2006, 12:42 am
-
Viliam
- Translator
- Posts: 1341
- Joined: January 30th, 2004, 11:07 am
- Location: Bratislava, Slovakia
- Contact:
Code: Select all
## Hornshark Island 0-2-0 0 LossJust for curiosity... this one was a bad luck, or is there something special (from the point of this algorithm) about this scenario?
Will have to give this a try.
Thanks for this. Look forward to trying it out.
Wow, this looks interesting, in my first try it did lose against the standard AI on Blitz though 
Oh, and towards the end (it only had a single leader remaining I think), I got this:
Also, I was told in #wesnoth-dev you asked about the .heals property, this should be fixed in SVN.
[edit]
Ok, I ran two more tests using the following shell script:
chesslike.py indeed did win 2 times and lose 1.. so overall it's 2:2 in my tests on Blitz now - which is impressive in any case, my sample.py only could win by a lucky assassination of the enemy leader from what I remember
Oh, and towards the end (it only had a single leader remaining I think), I got this:
Code: Select all
Traceback (most recent call last):
File "<string>", line 4, in ?
File "/home/elias/stuff/wesnoth-1.2/wesnoth/data/ais/mschmahl.py", line 448, in ?
if not ai.do_one_move():
File "/home/elias/stuff/wesnoth-1.2/wesnoth/data/ais/mschmahl.py", line 322, in do_one_move
base_score = self.eval_move(orig,orig)
File "/home/elias/stuff/wesnoth-1.2/wesnoth/data/ais/mschmahl.py", line 414, in eval_move
if dist > 1:
UnboundLocalError: local variable 'dist' referenced before assignment
[edit]
Ok, I ran two more tests using the following shell script:
Code: Select all
src/wesnoth \
--nogui \
--multiplayer \
--scenario=multiplayer_Blitz \
--side1=Rebels \
--side2=Rebels \
--controller1=ai \
--controller2=ai \
--algorithm1=python_ai \
--parm1=python_script:mschmahl.py
Last edited by allefant on March 27th, 2007, 2:12 pm, edited 1 time in total.
-
Darth Fool
- Retired Developer
- Posts: 2633
- Joined: March 22nd, 2004, 11:22 pm
- Location: An Earl's Roadstead
cool! I might have to add the algorithm as an option into my new (C++) AI for calculating the moves. (Yes, progress is slowly being made on the fools ai.)
"you can already do that with WML"
Fight Creeeping Biggerism!
http://www.wesnoth.org/forum/viewtopic. ... 760#131760
http://www.wesnoth.org/forum/viewtopic. ... 1358#11358
This AI is certainly up to par with the default one.
My findings so far:
Charge - Rebels vs Rebels: 13-7 for the default AI
Charge - Knalgans vs Knalgans: 5-2-13 for the chesslike AI
Games were played equally many times as player 1 and 2. Contrary to the Drake games from allefant starting player didn't seem to have any effect here. The 2 draws in the Knalgan matchup are probably more or less wins for the chesslike AI since the default AI only survived with leveling it's steelclad leader into a Dwarven Lord and most likely had no other units left (judging from the console output).
My findings so far:
Charge - Rebels vs Rebels: 13-7 for the default AI
Charge - Knalgans vs Knalgans: 5-2-13 for the chesslike AI
Games were played equally many times as player 1 and 2. Contrary to the Drake games from allefant starting player didn't seem to have any effect here. The 2 draws in the Knalgan matchup are probably more or less wins for the chesslike AI since the default AI only survived with leveling it's steelclad leader into a Dwarven Lord and most likely had no other units left (judging from the console output).
"If gameplay requires it, they can be made to live on Venus." -- scott