Forum

Post 17.04.2011   # 1
Subject Codefu online round 2, problem 4 TicTacToe

Test case 9 has 4 combinations with 'o' as winner. The positions in the matrix are annotated from 1 to 9. There are 4 unused spaces.

turns: o|x|o|x

  1.     3|5|9|?

  2.     9|5|3|?

  3.     7|5|9|?

  4.     9|5|7|?

? means its irrelavant, since 'o' already won the game.

P(case 1 to happen) = P('o' to play position 3)*P('x' to play position 5)*P('o' to play position 9) = 1/4*1/3*1/2 = P(case 2)=P(case 3)=P(case 4)

P('o' to win) = P(case 1) + P(case 2) + P(case 3) + P(case 4) = 1/6

Don't expain your solution. Find the error in mine.

Best regards,

Daniel.

dsmilkov is offline Reply
Post 17.04.2011   # 2

My point exactly, that is the procedure for the exact mathematical chance for victory.

Angel

angel is offline Reply
Post 17.04.2011   # 3


First of all, this post also goes as answer to igorkulev, stating about the ambigiosity of the problem. After looking at the solutions, and discussing with the competitors, I believe that I know what the problems were.
Next, some quotes from the problem synapsis:
"Given a state in the tic-tac-toe game, your task is to determine the statistical chances of the current computer on to win".
"Your task is to fetch all the possible game outcomes, and return the chances of winning for the current computer
in percentages"
"If there is a winner in some step, and still some remaining empty fields, these fields are not played in that state."
I believe that I pointed out the proper way of solving this task, thus, the test cases always fill that what it's not written.
However, missunderstandings are always possible, and this was the exact case here. Thinking about this type of task, there two possible scenarios.
One: to start processing the game tree top-bottom, calculating the sum of probabilites as equal in each step and then
summing them all in order to get the final result. That was the not intended approach in this task.
Two: to process the entire tree, calculate the sum of the tree leaves (wins/loses/draws), and then calculate the final result.
This one is the statistical approach, and it is the one that was asked to be coded.
As an example, I'll take test case 9:
the initial state is:
xx_
x_o
_o_
I'll mark the remaining fields with numbers as:
xx1
x2o
3o4
The tree of all the possible games is as follows:

 
O          1                2                         3                4
/ | \ / | \ / / \ / | \
X 2 3 4 1 3 4 1 2 4 1 2 3
/ \ / \ / \ / \ / \ / \
O 3 4 2 3 1 3 1 4 1 2 1 3
| | | | | | | |
X 4  3 2 3 1 4 2 1


 
The terminal nodes are a winning state. You can note that 4 of them are for computer 'o' and 14 are for computer 'x'.
That gives a total statistical chance of 4 / ( 4 + 18 ) = 22.2%
The other solution would actually include the branches of the terminated nodes in the upper levels, then generating additional 6 leaves, resulting in a wrong answer of 4/24 = 16.7% or 1/6.

hsilomedus is offline Reply
Post 17.04.2011   # 4

There is no ambigiosity in the problem. There is only 1 correct solution. Leave ambigiosity for non-mathematical problems. Our task was to calculate "the statistical chances of the current computer on to win", i.e.  "return the chances of winning for the current computer".

I was told that the solution of 0.222 is because there are 18 terminal nodes of which 4 are good for player 'o' therefore 4/18=0.222. However, the problem with this approach is that not all terminal nodes have equal probability of hapenning.

In other words, some terminal nodes are at depth 2  where 'x' wins, and some are at depth 3 (where 'o' wins). THEY HAVE NO EQUAL PROBABILITY OF HAPPENING and they have to be considered with causion.

Daniel.

dsmilkov is offline Reply
Post 17.04.2011   # 5

Since it is expected for us to return a percentage (0-100%), I assume that "return the chances of winning for the current computer"  means "return the probability of winning for the current computer" multiplied by 100 where probability is a number between 0 and 1.

The behavior of the players is well explained: they play randomly, i.e. they have uniform probability of choosing any of the free slots.

There is a clear connection between statistics and probability. In other words, a good statistical estimate of the probability of player 'o' winning is to run stochastic simulations. Then P('o' to win) can be approximated with r/n where r is the number of runs where 'o' actually won the game, and n is the total number of runs. The bigger the n, the smaller the estimation error.

Feel free to run simulations, and let me know of the ouput.

Daniel.

dsmilkov is offline Reply
Post 17.04.2011   # 6

One last remark motivated by the "very interesting" choice of emphasized words in the response.

Our taks is to do whatever we want, and return the chances of winning for the current computer in percentages"

dsmilkov is offline Reply
Post 17.04.2011   # 7

Ok,

I must agree with dsmilkov, angel, igorkulev and rest which stated their ground about the proper probabilty calculations. But I also must state again that the task synapsis and especially the test cases were the ones to tell that that much detail is simply not required in the task. The goal was to do some simple counting and a division operation at the end, so some subsequent rounding errors for including the associated probability will be avoided. 

Some terms in the synapsis are also missleading (i.e. random choices). However, during the competition, the discussion about this problem was very low, so maybe one question of the type: "Is the probability taken in consideration." would have solved all the ambiguities. Also, a simple on-hand breakdown of a test case directly points out the needed solution. And this is not that much time demanding.

A note for further competitions: anytime when you suspect a task validity, comment in the arena or at the forum. Don't just ask if it correct or no, say your thoughts, or point out some possible missunderstandings. Mistakes are always possible.

Since the difference between these solutions and the one that was being asked for, is the taken probability, the judges will discuss about them. There are already several 100% correct solutions submitted, so the their validity will not be compromised. There are already enough and well stated complaints, so further arguing about the task is not needed.

I'll say again, always discuss in depth during the competition. That way, we can resolve these issues quickly and effectivelly.

hsilomedus is offline Reply
Post 17.04.2011   # 8

The problem I see with the original solution is the interpretation of the result. I can understand the programming point of view, but mathematically, it doesn't represent anything actually, whereas our approach produces the exact percentage for winning.

Angel

Edited: this was written before the previous comment appeared

angel is offline Reply
Post 18.04.2011   # 9

I also want to state an interesting fact that came up after some fruitful discussions with angel and igorkulev.

In the problem synopsis there is a statement: They really don't bother using advanced logic or heuristic in order to play a better move, so they just take a random move

This statement is NOT misleading. This means that the players are not using any logic and play randomly.

Interestingly, the original "solution" does not depend on this statement, i.e. it does not depend on the playing strategies of the players and yields the same results for any strategy.

In other words, players can be smart and their choices can be biased (not uniform) but still the result of the original "solution" will be the same. This is so because it ignores the probabilities of the branches of the tree.

What part does the statement mentioned before play in the original not-misled "solution"?

In conclusions, one question of the type: "Is the probability taken in consideration." would have NOT solved anything.

dsmilkov is offline Reply
Post 19.04.2011   # 10

We have taken all comments into consideration.
The problem is indeed misleading, and probably splits the competitors to a group that goes into statistical counting solution and into probability solution.

From the solutions submitted, we see 11 competitors taking the statistical approach and 3 with probability approach (probably more, as there are at least 3 competitors who didn't submit their solution due to wrong results while testing).

We want to have the same and fair approach for every competitor, therefore we stand by the official testing and award the points for correctly tested solutions and not award points for "wrong" solutions.

This is based on the fact that it would very difficult now to find who are the mislead competitors who didn't submit a solution at all.

This decision is very tough and difficult for us and I really hope we will not have similar cases in the future.

Regarding other online competitions, I still strongly believe that we are very strict and clear in describing our problems, and much better than others in avoiding misunderstandings and multiple interpretations.

Anikov

anikov is offline Reply
Post 19.04.2011   # 11

Ќе пишувам на македонски, пошто сум малце поелоквентен така

Прво еден мал пример: Јованче е на крстопат. Лево му е домата, десно е шумата. Во шумата има уште многу рачви, и може:

- да го изеде мечка

- да го изеде волк

- да падне во потокот

- да падне во јама

.... (вкупно 99 начини за Јованче да заврше неславно )

Ако претпоставеме било која стратегија за движењето на Јованче (дури и таква во која тој секогаш врти лево ) според задачата 400, неговите шанси безбедно да стигне дома, статистички се 1%??

----

Во секој случај, една од карактеристиките што ги ценам кај луѓето е способноста да се признае грешка. Елегантното решение (според мене ) беше да се признае дека е згрешено. Луѓе сме, грешиме, ништо страшно.  Да немаше багови во овој занает, цел можен софтвер ќе беше совршен веќе во осумдесеттите (Секако, тие кои успеале да ја решат задачата според понудените резултати, треба да ги задржат поените - сепак, за време на натпреварот тоа се официјалните вредности според кои се работи )

Меѓутоа влегување во разноразни демагогии околу што значел кој збор и што се мислело да се каже, а не се кажало, е далеку од елеганција. Во протест, нема понатаму да учестувавам во CodeFu натпреварите (а и секако сум веќе престар ).

Поздрав, SWeko.

sweko is offline Reply
Post 20.04.2011   # 12

sweko wrote:

Во секој случај, една од карактеристиките што ги ценам кај луѓето е способноста да се признае грешка. Елегантното решение (според мене ) беше да се признае дека е згрешено. Луѓе сме, грешиме, ништо страшно.  Да немаше багови во овој занает, цел можен софтвер ќе беше совршен веќе во осумдесеттите (Секако, тие кои успеале да ја решат задачата според понудените резултати, треба да ги задржат поените - сепак, за време на натпреварот тоа се официјалните вредности според кои се работи ) Меѓутоа влегување во разноразни демагогии околу што значел кој збор и што се мислело да се каже, а не се кажало, е далеку од елеганција. Во протест, нема понатаму да учестувавам во CodeFu натпреварите (а и секако сум веќе престар ).

Поздрав, SWeko.

Zdravo SWeko,

Mnogu vreme potroshivme vo analizata ovoj problem, priznavme deka ne e ednoznachen problemot i deka del od natprevaruvachite se pogreshno navedeni kon poinakvo reshenie, shto avtomatski znachi deka e nasha greshka.

Ne go razbiram delot so demagogiite i protestot.
Iskreno, zhal mi e shto taka mislish.

Pozdrav,
Anikov

anikov is offline Reply

Please login to post reply.