View Single Post
Hurkyl
#3
Feb10-09, 03:18 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
It's a theorem that for all games of this type, the first player has a non-losing strategy.


The proof goes as follows: suppose player 2 has a winning strategy. Then player one has a winning strategy as follows:

1. Place his first piece randomly (this will now be called the 'extra' piece)

2. Pretend the extra piece doesn't exist
Note that, when pretending this, he becomes player 2 in his pretend game
3. Use player 2's winning strategy to win[indent]Note that if the winning strategy ever asks him to play a piece where he's already put his extra piece, then he just stops pretending it's extra, and makes a random play, now considering that piece the extra piece[indent]

Since both players cannot win, we have a contradiction. Therefore, there exists a player 1 strategy that guarantees player 2 cannot win.



Of course, there are variations you can make to defeat this technique... but you didn't make one.