[Guest]

i fould a neat little game on the internet.

there are 8 cards numbered in acending order. they alternate between green and red. player 1 takes red.

each player takes a turn switching any two cards, such that the card on the right is smaller than the card on the left after the switch.

the goal of the game is to get your 4 colored cards in decending order. if after yor move, both are in decending, its a draw. the game also has the pie rule: if your first move is viewed as too strong by your opponent, he may switch colors as his move.

so, what's the optimal first move for each side?

example game:

1 2 3 4 5 6 7 8 <- initial state

1 5 3 4 2 6 7 8 <- player 1 swaps 2 and 5.

1 6 3 4 2 5 7 8 <- player 2 swaps 5 and 6.

1 6 7 4 2 5 3 8 <- player 1 swaps 7 and 3. (if player 2 now swaps 1 and 8, it would be a draw.)

1 6 7 4 2 8 3 5 <- player 2 swaps 5 and 8.

1 6 7 5 2 8 3 4 <- player 1 swaps 4 and 5.

1 6 8 5 2 7 3 4 <- player 2 swaps 8 and 7.

1 6 8 7 2 5 3 4 <- player 1 swaps 7 and 5.

1 6 8 7 3 5 2 4

1 6 8 7 5 3 2 4

1 6 8 7 5 4 2 3

2 6 8 7 5 4 1 3

2 6 8 4 5 7 1 3

2 6 8 4 7 5 1 3

3 6 8 4 7 5 1 2

4 6 8 3 7 5 1 2

8 6 4 3 7 5 1 2 <- player 2 wins.

[Molly Mae]

Is there a ko-esque rule to prevent an opponent from ever winning by repeating the immediately played position?

EDIT: I guess there is by "each player takes a turn switching any two cards, such that the card on the right is smaller than the card on the left after the switch."

=P

I'd switch 7 and 8, as it guarantees a secured 7 without retaliation. This puts red up by half a move (which switching 5 and 6 doesn't do). If the second player switches colours for his turn, he will now be down half a move after the first player's initiative-based next turn. A 5-6 switch can be countered by the second player choosing to switch 2 and 5. But I'll play some more before I decide on this as my final answer.

Edited October 25, 2011 by Molly Mae

[superprismatic]

Thanks, Phillip. This is one cool problem. It wasn't clear to me that every permutation on eight things can be formed during this game. So, I wrote a program to check it.

Sure enough (modulo programming bugs), every permutation can occur. I'm trying to think about what to do next. In the meantime, I wanted to let you know that someone

is working on this pretty hard.

[Guest]

ah! cool. i'm glad you enjoy it super. i too am trying a programming attack on it.

[CaptainEd]

Hmmm...

If there IS a winning move for P1 in the game without the pie rule, then the same move is NOT a winning move for P1 WITH a pie rule, as P2 can swap colors, and now P1 is in a losing position by definition.

So, either there is no winning move for P1 or there is a losing move for P1 that becomes a winning move if P2 swaps colors. But P2 will be disinclined to change a winning position into a losing one, so will not swap colors.

So I conclude that P1 has no winning move in the game with the pie rule.

That's a surprising result, isn't it? Especially as, in the 4 coin or 6 coin case, the first player has an instant one-move win.

[CaptainEd]

oops, forgot they can tie, please ignore previous conclusion. I think the argument is valid up to a point--it needs to be softened to say "I think P2 can always avoid losing".

[Molly Mae]

oops, forgot they can tie, please ignore previous conclusion. I think the argument is valid up to a point--it needs to be softened to say "I think P2 can always avoid losing".

I still believe there to be a winning strategy for P1. Perhaps I'm mistaken, but if P2 invokes the pie rule, it is again P1's turn to move, correct?

So far, my best first move as P1 is 1 - 6. Although it sacrifices the left most position early, it guarantees that the 6 will have to move again while the 1 can't be moved to the left any more, granting more space for the first player to work with. It's not so strong to warrant a role swap, but if the second player does so, P1 might still be in a better position because he has the next move.

Edit: No. You are absolutely right. I just had a little fun with a counting game that echoes the pie rule and can't come up with a winning strategy theory.

Edited October 28, 2011 by Molly Mae

[CaptainEd]

By the way, I'm assuming that P1 wins if P2 makes a move that puts P1's coins into the winning order without putting P2's coins into the winning order (an "own goal" situation).

Edited October 28, 2011 by CaptainEd

[Guest]

that assumption is correct captain. i tend to agree with your logic, with the pie rule, its makes a guaranteed win as player 1 near impossible.

if there is a winning first move for player 1, player 2 can switch sides. so the best player 1 can do is draw.

[Molly Mae]

Assume there is an optimum play without the pie rule. Player 1 wins by playing that optimal strategy. To compensate for the optimum play, the pie rule is introduced. The optimal winning strategy still exists. If player 1 plays an arbitrary move, Player 2 will have optimum play to win (else he can switch roles and P1 by definition will not have optimum play to win, since P2 didn't have optimum play in that same situation).

[Guest]

Question: each player takes a turn switching any two cards, such that the card on the right is smaller than the card on the left after the switch.

In your example

1 2 3 4 5 6 7 8 <- initial state

1 5 3 4 2 6 7 8 <- player 1 swaps 2 and 5.

3 is smaller than 5 valid move, but 6 is not smaller than 7 isnt it invalid move.

Or, it should be any one card should satisfy the condition.

[Guest]

6 is not smaller than 7? you sure?

[Guest]

sorry.

I was concern of of 2 and 6?

[Guest]

oh i see. no, what i mean is the cards themselves that you are switching.

for examle, after swapping 2 and 5, niether 3 nor 4 can swap with 5.

Edited October 31, 2011 by phillip1882

[Guest]

okay i think i finally have an answer.

i ran a monte carlo type sim on the game, generating thousands of random games and returning the best move. according to my calculations, swapping 1 and 7 is best for player 1. i didn't factor in the pie rule. if anyone is interested, here is my code.

 import random def factorial(n): if n == 0 or n ==1: return 1 else: return n*factorial(n-1) def permute(array,i): inc = len(array) value = factorial(inc) temp = array[:] while i > 0: if value > i: inc -= 1 value = factorial(inc) else: index = int(i/value)-1 temp[inc],temp[index] = temp[index],temp[inc] i = i%value return temp def detectWin(cards): odd = len(cards)+1 even = len(cards)+1 for i in range(0,len(cards)): if cards[i]%2 == 0: if cards[i] < even: even = cards[i] else: even = -1 else: if cards[i] < odd: odd = cards[i] else: odd = -1 if even != -1 or odd != -1: if even == -1: return "odd" elif odd == -1: return "even" else: return "draw" return "false" def availMoves(cards): swaps = [] for i in range(len(cards)-1,-1,-1): for j in range(i-1,-1,-1): if cards[j] < cards[i]: swaps += [[j,i]] return swaps array = list(range(1,9)) postates = {} player = "odd" for i in range(factorial(len(array))-1,-1,-1): cards = permute(array,i) outcome = detectWin(cards) if outcome != "false": if outcome == "draw": postates[str(cards)] = [0.5,0.5] elif outcome != player: postates[str(cards)] = [0.0,1.0] else: postates[str(cards)] = [1.0,0.0] else: postates[str(cards)] = [0.5,0.5] trials = 100000 while trials > 0: cards = array[:] check = "false" movelist = [] turn = 0 while check == "false": possmoves = [] curmoves = availMoves(cards) for i in range(0,len(curmoves)): cards[curmoves[i][0]],cards[curmoves[i][1]] = cards[curmoves[i][1]],cards[curmoves[i][0]] chance = random.random() if chance < postates[str(cards)][turn]: possmoves += [curmoves[i]] cards[curmoves[i][0]],cards[curmoves[i][1]] = cards[curmoves[i][1]],cards[curmoves[i][0]] if len(possmoves) > 0: value = random.sample(possmoves,1) cards[value[0][0]],cards[value[0][1]] = cards[value[0][1]],cards[value[0][0]] if turn == 0: turn = 1 else: turn = 0 else: break movelist += value check = detectWin(cards) cards = array[:] if check != "draw" and cards != "false": if check == player: turn = 0 else: turn = 1 for i in range(0,len(movelist)): cards[movelist[i][0]],cards[movelist[i][1]] = cards[movelist[i][1]],cards[movelist[i][0]] postates[str(cards)][turn] *= 1.002 if turn == 0: turn = 1 else: turn = 0 postates[str(cards)][turn] *= 0.998 trials -= 1 cards = array[:] moves = availMoves(cards) for i in range(0,len(moves)): cards[moves[i][0]],cards[moves[i][1]] = cards[moves[i][1]],cards[moves[i][0]] print(cards) print(postates[str(cards)]) cards[moves[i][0]],cards[moves[i][1]] = cards[moves[i][1]],cards[moves[i][0]] 

Edited November 2, 2011 by phillip1882

[Guest]

ugh sorry previous post didnt format right, that quick reply option is broken.

import random

def factorial(n):

   if n == 0 or n ==1:

	  return 1

   else:

	  return n*factorial(n-1)

def permute(array,i):

   inc = len(array)

   value = factorial(inc)

   temp = array[:]

   while i > 0:

	  if value > i:

		 inc -= 1

		 value = factorial(inc)

	  else:

		 index = int(i/value)-1

		 temp[inc],temp[index] = temp[index],temp[inc]

		 i = i%value

   return temp

def detectWin(cards):

   odd = len(cards)+1

   even = len(cards)+1

   for i in range(0,len(cards)):

	  if cards[i]%2 == 0:

		 if cards[i] < even:

			even = cards[i]

		 else:

			even = -1

	  else:

		 if cards[i] < odd:

			odd = cards[i]

		 else:

			odd = -1

   if even != -1 or odd != -1:

	  if even == -1:

		 return "odd"

	  elif odd == -1:

		 return "even"

	  else:

		 return "draw"

   return "false"

def availMoves(cards):

   swaps = []

   for i in range(len(cards)-1,-1,-1):

	  for j in range(i-1,-1,-1):

		 if cards[j] < cards[i]:

		   swaps += [[j,i]]

   return swaps

array = list(range(1,9))

postates = {}

player = "odd"

for i in range(factorial(len(array))-1,-1,-1):

   cards = permute(array,i)

   outcome = detectWin(cards)

   if outcome != "false":

	  if outcome == "draw":

		 postates[str(cards)] = [0.5,0.5]

	  elif outcome != player:

		 postates[str(cards)] = [0.0,1.0]

	  else:

		 postates[str(cards)] = [1.0,0.0]

   else:

	  postates[str(cards)] = [0.5,0.5]

trials = 100000

while trials > 0:

   cards = array[:]

   check = "false"

   movelist = []

   turn = 0

   while check == "false":

	  possmoves = []

	  curmoves = availMoves(cards)

	  for i in range(0,len(curmoves)):

		 cards[curmoves[i][0]],cards[curmoves[i][1]] = cards[curmoves[i][1]],cards[curmoves[i][0]]

		 chance = random.random()

		 if chance < postates[str(cards)][turn]:

			possmoves += [curmoves[i]]

		 cards[curmoves[i][0]],cards[curmoves[i][1]] = cards[curmoves[i][1]],cards[curmoves[i][0]]

	  if len(possmoves) > 0:

		 value = random.sample(possmoves,1)

		 cards[value[0][0]],cards[value[0][1]] = cards[value[0][1]],cards[value[0][0]]

		 if turn == 0:

			turn = 1

		 else:

			turn = 0

	  else:

		 break

	  movelist += value

	  check = detectWin(cards)

   cards = array[:]

   if check != "draw" and cards != "false":

	  if check == player:

		 turn = 0

	  else:

		 turn = 1

	  for i in range(0,len(movelist)):

		 cards[movelist[i][0]],cards[movelist[i][1]] = cards[movelist[i][1]],cards[movelist[i][0]]

		 postates[str(cards)][turn] *= 1.002

		 if turn == 0:

			turn = 1

		 else:

			turn = 0

		 postates[str(cards)][turn] *= 0.998

   trials -= 1

cards = array[:]

moves = availMoves(cards)

for i in range(0,len(moves)):

   cards[moves[i][0]],cards[moves[i][1]] = cards[moves[i][1]],cards[moves[i][0]]

   print(cards)

   print(postates[str(cards)])

   cards[moves[i][0]],cards[moves[i][1]] = cards[moves[i][1]],cards[moves[i][0]]

[Guest]

just noticed a slight bug, about 3/4 the way down, the line

if check != "draw" and cards != "false":

should be

if check != "draw" and check != "false":

the result is the same, perhaps a slight over counting.

[CaptainEd]

Phillip, after P1 swapped 1 and 7, if P2 swaps 7 and 8, what is P1's approach?

Molly Mae, after P1 swaps 1 and 6, if P2 swaps 2 and 8, what is P1's approach?

I don't know why, but I get the feeling P2 doesn't need the pie rule! But I'm not good at playing against myself.

Fascinating problem, Phillip!

Edited November 2, 2011 by CaptainEd

[Guest]

i just played against myself, and here is my result...

1 2 3 4 5 6 7 8

7 2 3 4 5 6 1 8

8 2 3 4 5 6 1 7

8 2 3 7 5 6 1 4

8 2 3 7 6 5 1 4 <-- the game looks over at this point, i dont see any move player 2

8 2 7 3 6 5 1 4 can make that will fix his problem and prevent player 1 from winning.

8 3 7 2 6 5 1 4

8 7 3 2 6 5 1 4 <-- what can player 2 do?

[Guest]

ah!

how about...

1 2 3 4 5 6 7 8

7 2 3 4 5 6 1 8

8 2 3 4 5 6 1 7

8 2 3 7 5 6 1 4

8 6 3 7 5 2 1 4 !!!

now player 1 is trapped.

[CaptainEd]

yup. This is a tricky game, both players are so close to wins, and can affect each other in such interesting ways, such as your last move.

Since I haven't been able to convince myself that 1x7 or 1x6 is a clear winner, I'm imagining 3x5 or 2x5, just becase they demand immediate response. But it's a tricky game...

[Molly Mae]

after P1 swaps 1 and 6, if P2 swaps 2 and 8, what is P1's approach?

1 2 3 4 5 6 7 8

6 8 3 4 5 1 7 2

I see your point. Let's try a game of 3 and 5:

1 2 5 4 3 6 7 8

Edit: just saw your reply. 3x5 is a good candidate because it forces an immediate response and it keeps the leftmost position, which P1 can use to swap with any other number... It's a stronger position than I previously credited it (which you showed me in the game above).

Edited November 2, 2011 by Molly Mae

[Guest]

swapping 6 and 5 looks promising for player 2 in that position...

1 2 6 4 3 5 7 8

[Molly Mae]

1 2 7 4 3 5 6 8

7 and 6 (is met by 8 and 2)

1 4 6 2 3 5 7 8

2 and 4 is met by 4 and 6...

4 2 6 1 3 5 7 8

1 and 4 is met by...?

Edited November 2, 2011 by Molly Mae

[Guest]

4 2 6 1 3 5 7 8

any move seems to have potential, i personally like swapping 2 and 5.

4 5 6 1 3 2 7 8

[CaptainEd]

4 2 6 1 3 5 7 8

any move seems to have potential, i personally like swapping 2 and 5.

4 5 6 1 3 2 7 8

P1 can now swap 4 and 7, yielding

7 5 6 1 3 2 4 8

I think P2 can't prevent P1 from winning on next move.