tiagonapoli's blog

By tiagonapoli, history, 7 years ago, In English

Hi everyone, i'm a begginer on Games Theory and I was trying to solve Vasya and Chess — 281div2D but I couldn't understand the strategy behind the optimal way to play it, and , therefore, it's solution. Could anyone, please, help me with an explanation?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi!

Suppose n is odd. Let us assume that there exists a winning strategy S for first player on the given game G. After whites' first move black becomes first player on the board with one piece less(Call this game G'). This one less piece won't at all hurt black(Think yourself :P). Black can now simply copy whites' all moves symmetrically along the center vertical line. According to our assumption black is also following the same winning strategy S and is guaranteed to win G'. So, we have contradiction because in the end both can't win. So there doesn't exist such S and white can't win.

Note that this a non-constructive proof as we don't know what is the explicit winning strategy for Black. All we have shown is that White can't win. There are many such beautiful non-constructive proofs on games given in "LESSONS IN PLAY : Michael H. Albert, Richard J. Nowakowski, David Wolfe".

Now come to the case when n is even. Suppose white moves to (1,2). Note that this is the smallest (r+c) position that white can go (with smallest c). Now white simply abandons playing on first column. So now in this new game white is the second player and it can syymmetrically play along center line and from above we know that black will not have any winning strategy. So white wins. Note that in this case we have no information about whites' second move.

Hope this helps :D