CS 54 - SOS Game


Answer

You should reject the offer. The second player has the advantage of reacting to the other player's move resulting in at worst a tie and at best a win for the second player. For such a small game board, analyzing the other player's decisions is very easy and the second player has the advantage of more complete information when choosing her/his move.


Proof

Theorem: The second player can win the SOS game.
Proof: Player one has two choices on his/her first move: either place an S or an O in one of the spaces. So:

Case 1 (Player one places an S): Suppose that the first player puts and S in any of the squares. The second player can either construct the winning string by placing an O next to the first S or by placing another S two spaces away. But this would give the win to player one, so player two will not make such a move. Instead, player two can place an S based on where player one placed the S. If the S was placed at an endpoint, player two can place an S at the opposite end point. On the other hand, if the S was placed in a middle point, player two can place either an S or O on the left endpoint. In any case, player one's second move can at best tie the game and therefore player one cannot win by placing an S.
Case 2 (Player one places an O): Suppose that the first player puts O in any of the squares. We get the same case as above except dealing with O's instead of S's and S's instead of O's. As in the last case, the first player can at best tie the game and cannot win.

Therefore, player one has a disadvantage in this game and only player two can win. QED. ∎


Reference

http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf