Game of Hex,,,,invented by John Nash
From: karan (karan_at_iitk.ac.in)
Date: 06/26/04
- Next message: Quinn Tyler Jackson: "Re: Math research, passion is importantQ"
- Previous message: Donald G. Shead: "Re: Efficiency against frictional resistance"
- Messages sorted by: [ date ] [ thread ]
Date: 25 Jun 2004 18:59:23 -0700
hex
Proof that there exists a winning strategy for the first player in the
game Hex. This proof is more constructive than the one given by Nash
which only shows the existence of such a strategy.
the following is a sequence of games where the white player is a
"mechanical non thinking" device.The black player is a perfect
player.Moreover black responds to a particular board situation in the
samr manner every time it occurs.I prove that after a finite number of
moves the white player always wins. Moreover, white can obtain the
winning strategy from the following method.
Assume that winning strategy always exists for black(second player)
Assume that the hex board has odd number of hexagons.
Players exchange positions after every game.
White Black
Game 1 a1,a2,a3,a4........an
b1,b2,b3,b4........bn
Game 2 b1,b2,b3............bn
c1,c2,c3,..........cn
Game 3
a1,c1,c2............cn
b1,d1,d2,..........dn
Game 4
b1,d1,d2,..........dn
c1,e1,e2,e3,e4.....en
Game 5
a1,c1,e1,e2,e3 ......en
b1,d1,f1,f2,f3.........fn
Game 6
b1,d1,f1,f2,f3.........fn
c1,e1,g1,g2,g3......gn
Game 7
a1,c1,e1,g1,..........gn
b1,d1,f1,h1,h2,.......hn
Game 8
b1,d1,f1,h1,h2,.......hn
c1,e1,g1,i1,i2,i3,....in
Game 9
a1,c1,e1,g1,i1 b1,d1,f1,h1.
explanation:
for example in the sixth game white plays b1.black has to play c1
since the situation is same as that in game 2 after the first move of
white.next white plays d1.since now the situation is same as after 3
moves(in total) of game 4 black must play e1.white now plays f1.Since
this is a new arrangement on the board(uptill now) black has freedom
to play any move.Call blacks move as g1.
after this white plays f2,black plays g2,....till black wins.
Black wins all games from 1 to 8.
Let us assume that a maximum of 9 coins can be put on the board.
In game 9 white has won.For if not then black has won ....this implies
that in game 8 white had already won after first 4
moves.Contradiction.
In this method,it is assumed that black responds to a particular
setting of the board in exactly the same manner every time.seems
reasonable to me.(there may be more than one solution for blackat a
stage ...then there is a prob with black choosing any strategy.)
Also n is assumed same for all games .there is no need for this.
- Next message: Quinn Tyler Jackson: "Re: Math research, passion is importantQ"
- Previous message: Donald G. Shead: "Re: Efficiency against frictional resistance"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
