So, do any of you watch survivor?

[jemfinch]

If any of you watch survivor, you'll remember the immunity game they just played. If not, here are the rules:

The playing field starts with 21 flags whose arrangement is irrelevant; 20 "normal" flags and 1 "special" flag. Each person, on his or her turn, takes 1, 2, or 3 flags from the field. The special flag can only be taken when it is the last flag taken (but it can be taken with other flags) The goal of the game is to take the special flag.

Challenge #1: Write a program to play this game.
Challenge #2: Determine if the game is already won for either player.

I have a hunch that the game is already won for the second player, but I haven't proven it yet. Once we get some ideas on how to write a program to play the game, we should easily find out if it's won or not.

Jeremy

[scanez]

Well I didn't actually write the game yet, but I have proved that the first player has a won game. First we just label the flags 1-21 with 21 being the special flag. All the first player has to do to win is take flags 1, 5, 9, 13, and 17 (by this I mean when it is his turn, take the smallest amount of flags necessary to have taken one of the flags above, but no more). So for example, player 1 takes flag 1; to be sure of taking flag 5, if player 2 takes 1,2, or 3 flags, player 1 has to take 3,2, or 1 flag (respectively). In fact after the first flag this pattern continues- if the second player takes 1,2,or 3 flags, player 1 takes 3,2, or 1. After taking the 17th flag, player 2 has to take 1,2, or 3 flags starting with flag 18, but either way next turn player 1 can take flag 21 :)

I wonder if the survivor people knew that :p

Edit: so actually with these rules (taking 1,2, or 3 flags) if the total number of flags is not divisible by 4. player 1 has a won game; else player 2 has a won game ;)

[Strike]

Originally posted by scanez
I wonder if the survivor people knew that :p
Not bloody likely :P

[jemfinch]

kmj asked a question via Private Message (so he wouldn't give anything away, just in case :)) that definitely needs clarification.

You should write a computer program that plays the game against a human (or against itself), not a computer program that lets two humans play. If you want to do both, by all means, but my original idea (on the assumption that it'd be at least slightly harder than what scanez said) was to write a computer program to play the game.

Jeremy

[scanez]

Nothing in my analysis assumes that it's human vs human. If it's human vs computer, the human has a won game if he goes first and the computer has a won game (assuming that the programmed strategy it uses is a good one) if it goes first. In the same way, if it's computer vs computer the first player has a won game. Doesn't matter who's playing, the first player will win if he/she/it knows what he/she/it is doing :)

[kmj]

Nothing in my analysis assumes that it's human vs human.


I don't think jemfinch was trying to imply that does; do you?

[scanez]

Originally posted by kmj
I don't think jemfinch was trying to imply that does; do you?
I don't know, I'm a tard ;)

So then should the computer randomly choose how many flags to take each turn?

[inkedmn]

alright, here's mine (in python)


# the survivor game
# coded by inkedmn for cf.net

import random, sys

class Survivor:
def __init__(self):
self.flagsTaken = 0
self.flagsLeft = 21
self.gameOver = 0
self.playerFlags = 0
self.compFlags = 0

def playerGrab(self):
self.printStatus()
valid = 0
while valid == 0:
print "How many flags do you want to grab?"
try:
num = int(raw_input())
if self.isValid(num):
self.playerFlags += num
self.flagsTaken += num
self.flagsLeft -= num
valid = 1
else:
print "Invalid selection, try again\n"
except:
print "Invalid selection, try again\n"
print "you grabbed %d flags" % num
if self.flagsLeft == 0:
self.gameOver = 1
self.showWinner("player")

def computerGrab(self):
self.printStatus()
if self.flagsLeft <= 3:
self.compFlags += self.flagsLeft
print "Computer grabbed %d flags" % self.flagsLeft
self.gameOver = 1
self.showWinner("computer")
else:
num = random.choice([1, 2, 3])
print "Computer grabbed %d flags" % num
self.compFlags += num
self.flagsTaken += num
self.flagsLeft -= num

def isValid(self, num):
if num > 3 or num > self.flagsLeft:
return 0
else:
return 1

def printStatus(self):
print "\n%d flags in play" % self.flagsLeft
print "Computer has %d flags" % self.compFlags
print "Player has %d flags\n" % self.playerFlags

def showWinner(self, winner):
print "%s is the winner!" % winner
sys.exit()

if __name__ == '__main__':
surv = Survivor()
while surv.gameOver == 0:
surv.playerGrab()
surv.computerGrab()



works pretty well, could somebody run this and tell me if i'm doing this right? i'm pretty sure i understand the game, but i'd like to be sure...

[scanez]

inkedmn: Yep, that seems to run as it should :)

Since I go first, I win every time by the way :)

[inkedmn]

yeah, me too :)

[jemfinch]

Ugh..my computer's broken, so the code samples that follow aren't tested...sorry about any typos (not that I think anyone actually tries out my SML code, but anyway...)

So if I were to design a framework to play this game, then I'd represent moves like this:

datatype move = ONE | TWO | THREE


Since this is a game of perfect knowledge, "players" are simply functions that take a list of all the old moves made and return a move.

So scanez found the solution, and I played with it a little bit, and saw a pattern, so I quickly coded up a "perfect player" that could never lose if he was the first player:


fun perfectFirstPlayer [] = ONE
| perfectFirstPlayer (ONE :: _) = THREE
| perfectFirstPlayer (TWO :: _) = TWO
| perfectFirstPlayer (THREE :: _) = ONE


That is, take ONE flag to begin, and from there on, take 4 - the number of flags the other guy took. But I realized that this wasn't a "perfect" algorithm because it wouldn't take advantage of an opponent's mistakes. If this player was playing against a human who, say, took 2 flags on his first turn, he wouldn't be able to turn it into a win; he'd just maintain the status quo.

So I kept thinking for a short bit (longer, since I have no computer to test things on) and came up with this really perfect player:


fun moveToInt ONE = 1
| moveToInt TWO = 2
| moveToInt THREE = 3

fun flagsTaken [] = 0
| flagsTaken l = List2.foldl1 op+ (map moveToInt l)

fun perfectPlayer [] = ONE
| perfectPlayer l =
(case Int.mod (flagsTaken l, 4) of
0 => ONE
| 2 => THREE
| 3 => TWO
| _ => ONE (* Doesn't matter -- we're losing. *))


The algorithm isn't quite as clear as the last one, but this one actually will turn poor moves by its opponent into a win.

So the game turned out to be won from the start. I can't believe they had that as an immunity challenge on Survivor. Oh well. I suppose I should expect that from a game that's had Towers of Hanoi as an immunity challenge (and, interestingly, the team with the Software Engineer won both those challeneges)

Anyway, I doubt there's much more to say about this competition.

Jeremy

[Strike]

Er, that's what scanez said way ^^ up there, just in easier to understand language :)

[scanez]

General solution for such a game: Let k be the maximum number of flags a player can take during a turn. Then if the total number of flags is not divisible by k+1, player1 has a won game. If it is divisible by k+1, player2 has a won game :)

[recluse]

scanez, you're the man.

I'm finished here.

[scanez]

Final note: Actually now that I think about it, this game is an exampe of a finite (ends in a finite number of moves), zero-sum (one player's loss is the other player's gain, and vice-versa), two-person game. And it follows from the Minimax Theorem of Game Theory that in every such game there exists an optimal strategy for each player. Consequences are that if it is possible to get a draw in the game, then the optimal strategies lead to that draw; if it's not possible, one player's optimal strategy leads to a forced win (basically the game is predetermined). In this flag game, there can be no draw so one player is guarenteed to have a forced win at the beginning of the game (the 1st player in this case:))

If the survivor people would have read up on game theory they may have found out how unfair this game was to the second team :p

[stuka]

heh...that took me back to Adv. Data Structures and Algorithms - we actually had to draw game trees...eeew