Page 1 of 1
11229 - Improved tic-tac-toe.
Posted: Tue Jun 19, 2007 3:06 am
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!
Posted: Wed Jun 20, 2007 4:31 am
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
Posted: Wed Jun 20, 2007 4:30 pm
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.