Here is a nice little problem (via LJ-users avva and flaass). Suppose you are offered to play tic-tac-toe with a computer that uses the following algorithm:
1. If it has two in a row, it will play the third to win.
2. If you have two in a row, it will play the third to block them.
3. Otherwise, it will choose a place for the next move at random.
Would it make sense for you to play with such a machine, if you always make the first move, get $1 for each win, and pay $10 for each draw or loss?
Update: A solution can be found in the comments, and I am too lazy to delete it temporarily (and don't know if it is possible to screen/unscreen comments here). So if you want to think on your own, don't read the comments please.
6 comments:
А в чем проблема-то? По-моему, ответ очевидно "нет". Ключевое наблюдение: если в ответ на первый ход нолики делают ход, не ведущий к форсированному проигрышу, то тупой тактики (отбиваться, если в ряд два крестика) достаточно, чтобы свести вничью.
Если первый ход в угол, то вероятность ответа, не ведущего к форсированному проигрышу, равна 1/8, в двух других случаях --- 1/2. И все, казалось бы?
"Ключевое наблюдение" неправильно! Посмотри внимательней на третье правило.
The answer is obviously yes.
First you play in the corner. The only computer response that draws the game is the one in the center. Chances of this: 1/8. Otherwise, you win (7/8).
Second move (assuming the computer played correctly), you play in the opposite corner. The way the computer can counteract that is to play in the middle of any side: the chances of that are 4/6, otherwise (2/6=1/3) you win.
After that rules 1 and 2 apply.
So you win in 7/8 + 1/8 * 1/3 = 21/24 + 1/24 = 22/24 = 11/12.
Since 11/12 > 10/11, you should play.
Now that I've written this, I'm not sure this qualifies as "obvious" after all.
Vladimir:
1. Yes!
2. This was my solution too.
3. I don't think this is totally obvious.
4. To my surprise, the strategy can be improved!! This was done (by a collective effort with my participation but the idea was not mine) in the discussion at avva's.
Почитал комменты к Авве (со вчерашнего дня там добавилось). Очень понравилось соображение насчёт того, что 5 рублей в час -- слишком маленький заработок, чтоб ради него тратить время на игру с дураком...
Женя, если так рассуждать, то от всей математики мало что останется :)
Post a Comment