From: Sam Moore Date: Tue, 20 Dec 2011 10:41:29 +0000 (+0800) Subject: Added new sample AI - "vixen", improved "basic_python" X-Git-Url: https://git.ucc.asn.au/?p=progcomp2012.git;a=commitdiff_plain;h=72df4ec14efff5668c6237cd25e1e51ddd801c32 Added new sample AI - "vixen", improved "basic_python" I was going to create a highly advanced super AI and not reveal the source code. Then I would win the competition! But, turns out it is just as shit as all the others, so I added it to git. Also I made the competition, so that seems fairly self defeating. It was easier to add some extra stuff to basic_python than to force it into the new AI. "vixen" (where do I get these names? Well, a fox is smart, and a vixen is a fox. Therefore, "vixen" is a smart AI. Q.E.D) I basically copied asmodeus' "optimised score" and path finding technique, but I changed the way scores are calculated to include probability. At one point I was adding the scores for paths that began with the same direction. This seemed like a brilliant idea. It was not. After all this, vixen beats asmodeus some of the time, I haven't tested how often, but each AI has beaten the other at least a few times. Most of the time vixen loses seems to be due to losing the marshal or general on bombs. Its pretty good at countering the spy. It turns out writing a decent stratego AI is harder than I thought :P In other news, in the manager program, I removed the automatic hiding of the AI's pieces when a human is playing, because its useless and annoying. --- diff --git a/progcomp/agents/basic_python/basic_python.py b/progcomp/agents/basic_python/basic_python.py index 93e4100..919d1a2 100755 --- a/progcomp/agents/basic_python/basic_python.py +++ b/progcomp/agents/basic_python/basic_python.py @@ -73,6 +73,12 @@ class Piece: return 0 +def valuedRank(rank): + if ranks.count(rank) > 0: + return len(ranks) - 2 - ranks.index(rank) + else: + return 0 + class BasicAI: @@ -89,8 +95,13 @@ class BasicAI: self.board = [] self.units = [] self.enemyUnits = [] - self.alliedNumber = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1} - self.enemyNumber = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1} + + self.totalAllies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1} + self.totalEnemies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1} + self.hiddenEnemies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1} + self.hiddenAllies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1} + self.lastMoved = None + def Setup(self): @@ -230,6 +241,9 @@ class BasicAI: if attacker == None: return False + + lastMoved = attacker + defender = self.board[p[0]][p[1]] #Update attacker's position (Don't overwrite the board yet though) @@ -242,8 +256,19 @@ class BasicAI: if defender == None: return False attacker.rank = result[outIndex+1].strip() + if attacker.beenRevealed == False: + if attacker.colour == self.colour: + self.hiddenAllies[attacker.rank] -= 1 + elif attacker.colour == oppositeColour(self.colour): + self.hiddenEnemies[attacker.rank] -= 1 attacker.beenRevealed = True defender.rank = result[outIndex+2].strip() + if defender.beenRevealed == False: + if defender.colour == self.colour: + self.hiddenAllies[defender.rank] -= 1 + elif defender.colour == oppositeColour(self.colour): + self.hiddenEnemies[defender.rank] -= 1 + defender.beenRevealed = True @@ -255,35 +280,35 @@ class BasicAI: self.board[p[0]][p[1]] = attacker if defender.colour == self.colour: - self.alliedNumber[defender.rank] -= 1 + self.totalAllies[defender.rank] -= 1 self.units.remove(defender) elif defender.colour == oppositeColour(self.colour): - self.enemyNumber[defender.rank] -= 1 + self.totalEnemies[defender.rank] -= 1 self.enemyUnits.remove(defender) elif outcome == "DIES": if attacker.colour == self.colour: - self.alliedNumber[attacker.rank] -= 1 + self.totalAllies[attacker.rank] -= 1 self.units.remove(attacker) elif attacker.colour == oppositeColour(self.colour): - self.enemyNumber[attacker.rank] -= 1 + self.totalEnemies[attacker.rank] -= 1 self.enemyUnits.remove(attacker) elif outcome == "BOTHDIE": self.board[p[0]][p[1]] = None if defender.colour == self.colour: - self.alliedNumber[defender.rank] -= 1 + self.totalAllies[defender.rank] -= 1 self.units.remove(defender) elif defender.colour == oppositeColour(self.colour): - self.enemyNumber[defender.rank] -= 1 + self.totalEnemies[defender.rank] -= 1 self.enemyUnits.remove(defender) if attacker.colour == self.colour: - self.alliedNumber[attacker.rank] -= 1 + self.totalAllies[attacker.rank] -= 1 self.units.remove(attacker) elif attacker.colour == oppositeColour(self.colour): - self.enemyNumber[attacker.rank] -= 1 + self.totalEnemies[attacker.rank] -= 1 self.enemyUnits.remove(attacker) elif outcome == "FLAG": diff --git a/progcomp/agents/vixen/asmodeus.py b/progcomp/agents/vixen/asmodeus.py new file mode 120000 index 0000000..1b1739c --- /dev/null +++ b/progcomp/agents/vixen/asmodeus.py @@ -0,0 +1 @@ +../asmodeus/asmodeus.py \ No newline at end of file diff --git a/progcomp/agents/vixen/basic_python.py b/progcomp/agents/vixen/basic_python.py new file mode 120000 index 0000000..3d6b342 --- /dev/null +++ b/progcomp/agents/vixen/basic_python.py @@ -0,0 +1 @@ +../basic_python/basic_python.py \ No newline at end of file diff --git a/progcomp/agents/vixen/info b/progcomp/agents/vixen/info new file mode 100644 index 0000000..424358b --- /dev/null +++ b/progcomp/agents/vixen/info @@ -0,0 +1 @@ +vixen.py diff --git a/progcomp/agents/vixen/path.py b/progcomp/agents/vixen/path.py new file mode 120000 index 0000000..1d82284 --- /dev/null +++ b/progcomp/agents/vixen/path.py @@ -0,0 +1 @@ +../asmodeus/path.py \ No newline at end of file diff --git a/progcomp/agents/vixen/vixen.py b/progcomp/agents/vixen/vixen.py new file mode 100755 index 0000000..fc13328 --- /dev/null +++ b/progcomp/agents/vixen/vixen.py @@ -0,0 +1,171 @@ +#!/usr/bin/python -u + +#NOTE: The -u option is required for unbuffered stdin/stdout. +# If stdin/stdout are buffered, the manager program will not recieve any messages and assume that the agent has timed out. + +''' + vixen.py - A sample Stratego AI for the UCC Programming Competition 2012 + + Written in python, the slithery language + + author Sam Moore (matches) [SZM] + website http://matches.ucc.asn.au/stratego + email progcomp@ucc.asn.au or matches@ucc.asn.au + git git.ucc.asn.au/progcomp2012.git +''' + +from basic_python import * +from path import * + + + +class Vixen(BasicAI): + " Python based AI, improves upon Asmodeus by taking into account probabilities, and common paths " + def __init__(self): + #sys.stderr.write("Vixen initialised...\n") + BasicAI.__init__(self) + + + self.bombScores = {'1' : -0.9 , '2' : -0.8 , '3' : -0.5 , '4' : 0.1, '5' : 0.1, '6' : 0.3, '7' : 0.7, '8' : 1 , '9' : 0.6, 's' : 0} + self.suicideScores = {'1' : -0.5 , '2' : -0.4 , '3' : -0.35, '4' : -0.25, '5' : -0.2, '6' : 0.0, '7' : 0.1, '8' : -0.4 , '9' : 0.0, 's' : -0.4} + self.killScores = {'1' : 1.0 , '2' : 0.9 , '3' : 0.9 , '4' : 0.8, '5' : 0.8, '6' : 0.8, '7' : 0.8, '8' : 0.9 , '9' : 0.7, 's' : 0.9} + self.riskScores = {'1' : 0.0, '2' : 0.1, '3' : 0.2, '4': 0.4, '5': 0.6, '6': 0.7, '7':0.8, '8': 0.0, '9' : 1.0, 's' : 0.1} + + + + + + def MakeMove(self): + #sys.stderr.write("Vixen MakingMove...\n") + " Over-rides the default BasicAI.MakeMove function " + + moveList = [] + for unit in self.units: + if unit.mobile() == False: + continue + + scores = {"LEFT":0, "RIGHT":0, "UP":0, "DOWN":0} + + + for target in self.enemyUnits: + if target == unit: + continue + path = PathFinder().pathFind((unit.x, unit.y), (target.x, target.y), self.board) + if path == False or len(path) == 0: + continue + moveList.append({"unit":unit, "direction":path[0], "score":self.CalculateScore(unit, target, path)}) + #scores[path[0]] += self.CalculateScore(unit, target, path) + + #bestScore = sorted(scores.items(), key = lambda e : e[1], reverse=True)[0] + #moveList.append({"unit":unit, "direction":bestScore[0], "score":bestScore[1]}) + + + if len(moveList) == 0: + print "NO_MOVE" + return True + + moveList.sort(key = lambda e : e["score"], reverse=True) + sys.stderr.write("vixen - best move: " + str(moveList[0]["unit"].x) + " " + str(moveList[0]["unit"].y) + " " + moveList[0]["direction"] + " [ score = " + str(moveList[0]["score"]) + " ]\n") + if moveList[0]["score"] == 0: + print "NO_MOVE" + return True + + + print str(moveList[0]["unit"].x) + " " + str(moveList[0]["unit"].y) + " " + moveList[0]["direction"] + return True + + + def tailFactor(self, pathLength): + #if pathLength >= len(self.tailFactors) or pathLength <= 0: + # return 0.0 + #return self.tailFactors[pathLength] + #return 0.5 * (1.0 + pow(pathLength, 0.75)) + return 1.0 / pathLength + + + def CalculateScore(self, attacker, defender, path): + total = 0.0 + count = 0.0 + for rank in ranks: + prob = self.rankProbability(defender, rank) + if prob > 0.0: + #sys.stderr.write(" " + str(attacker.rank) + " vs. " + str(rank) + " [" + str(prob) + "] score " + str(self.combatScore(attacker.rank, rank, len(path))) + "\n") + total += prob * self.combatScore(attacker.rank, rank, len(path)) + count += 1 + + + #if count > 1: + # total = total / count + self.riskScore(attacker.rank) + + + total = total * self.tailFactor(len(path)) + #sys.stderr.write("Total score for " + str(attacker) + " vs. " + str(defender) + " is " + str(total) + "\n") + return total + + def combatScore(self, attackerRank, defenderRank, pathLength): + if defenderRank == 'F': + return 1.0 + elif defenderRank == 'B': + return self.bombScore(attackerRank) + elif defenderRank == 's' and attackerRank == '1' and pathLength == 2: + return self.suicideScore(attackerRank) + elif defenderRank == '1' and attackerRank == 's' and pathLength != 2: + return self.killScore(attackerRank) + + if valuedRank(attackerRank) > valuedRank(defenderRank): + return self.killScore(defenderRank) + elif valuedRank(attackerRank) < valuedRank(defenderRank): + return self.suicideScore(attackerRank) + return self.killScore(defenderRank) + self.suicideScore(attackerRank) + + def killScore(self, defenderRank): + return self.killScores[defenderRank] + + def bombScore(self, attackerRank): + return self.bombScores[attackerRank] + + def suicideScore(self, attackerRank): + return self.suicideScores[attackerRank] + + def riskScore(self, attackerRank): + return self.riskScores[attackerRank] + + def rankProbability(self, target, targetRank): + if targetRank == '+' or targetRank == '?': + return 0.0 + if target.rank == targetRank: + return 1.0 + elif target.rank != '?': + return 0.0 + + total = 0.0 + for rank in ranks: + if rank == '+' or rank == '?': + continue + elif rank == 'F' or rank == 'B': + if target.lastMoved < 0: + total += self.hiddenEnemies[rank] + else: + total += self.hiddenEnemies[rank] + + if total == 0.0: + return 0.0 + return float(float(self.hiddenEnemies[targetRank]) / float(total)) + + def InterpretResult(self): + """ Over-ride the basic AI interpret result so we can update probabilities """ + if BasicAI.InterpretResult(self) == False: + return False + + return True + + + + + +if __name__ == "__main__": + vixen = Vixen() + if vixen.Setup(): + while vixen.MoveCycle(): + pass + diff --git a/progcomp/judge/manager/game.cpp b/progcomp/judge/manager/game.cpp index d88f759..3d6dcc8 100644 --- a/progcomp/judge/manager/game.cpp +++ b/progcomp/judge/manager/game.cpp @@ -446,7 +446,7 @@ MovementResult Game::Play() while (!Board::HaltResult(result) && (turnCount < maxTurns || maxTurns < 0)) { - if (red->HumanController()) + if (red->HumanController() && blue->HumanController()) toReveal = Piece::RED; if (printBoard) { @@ -476,7 +476,7 @@ MovementResult Game::Play() else ReadUserCommand(); - if (blue->HumanController()) + if (blue->HumanController() && red->HumanController()) toReveal = Piece::BLUE; if (printBoard) {