11229 - Improved tic-tac-toe.

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

11229 - Improved tic-tac-toe.

Post by sjn »

Any idea how to solve it?

or please just explain the case following:

50 50 50
50 50 50
50 50 50
50 50 50
50 50 50
50 50 50

47.46


thx in advance!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

They know that who plays first has a better chance to win, so they always try to win when playing first and try not to loose when playing second.
This means:
First player chooses the mass which leads first player's win with the highest probability.Second player chooses the opposite.

I think this phrase will naturally lead you to the algorithm ...
----
Rio

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Well, what is natural for some people is not natural for others :)

I started doing these probability/game questions recently and took me a while to grasp the concept. It does not help that I just can't think recursively. I recommend going through "Understanding Probabilities" tutorial at TopCoder (I haven't finished those problems yet, and I should).

In this specific case - you can consider a tie to be a win for the second player. That is why you get <50% for that board. And, note that in the case of a tie, first player made the last move.

Post Reply

Return to “Volume 112 (11200-11299)”