Дневник LuckyLake., Пробуем структуризацию накопленного опыта )) Опции

[Yanavar]

Первая стадия решения.
2 ряда.
Несложно доказать, что когда у нас два ряда и наш ход, ситуации 1:N, 2:N, 3:N, 4:N для нас всегда означают победу. Таким образом, ситуация, когда количество спичек в двух рядах неодинаковое, и наш ход, выигрышным действием будет свести его к одинаковому, и далее независимо от хода противника уравнивать количество спичек на каждом ходу.

Сложность представляет наличие третьего ряда.
Ща попробую свести ситуацию к двум рядам.

3 ряда
Таким образом, если у нас любая ситуация вида N:N:M и наш ход - мы победили. Уничтожение любого ряда, когда в остальных двух неравное количество спичек приводит к проигрышу. То есть наша задача - удерживать до упора ситуацию, когда в трех рядах количество спичек неравное и ход противника.

Осталось выработать стратегию для поддержания неравного количества фишек

[LuckyLake]

Yanavar, Вообще то что я дал 3-5-7 структуру, это был просто пример.
Задача решается в общем виде для АБСОЛЮТНО любого числа спичек и рядов.

Но тот факт, что если мы оставили противнику два ряда с одинаковым количеством, гарантирует нам победу, это правильно без сомнений.

Вечером, пожалуй, дам еще одну подсказку. Последнюю.

[Yanavar]

Ну короче для трех рядов стратегия выглядит так:
1. Если количество фишек во всех трех рядах разное, забираем все фишки из любого ряда, кроме одной.
2. Если противник уравнивает количество фишек в оставшихся рядах - забираем одну и он проиграл.
Если противник оставляет в любом оставшемся ряду количество фишек, равное двум или трем - забираем в оставшемся ряду все, кроме трех или двух фишек соответственно. Он проиграл.
Если противник оставляет в любом ряду четыре и более фишек - оставляем в оставшемся ряду на одну больше. Рано или поздно ситуация сведется к 1:2:N или 1:3:N, являющимся тривиальными.

Ну вот теперь уже можно подумать, как оформить алгоритм в общем виде.

[LuckyLake]

А почему 1-2-N тривиальная ?
Вот 1-2-3 оставленная противнику, гарантирует нам победу независимо от его хода.
А 1-2-5 нет, т.к. оппонент может сделать нам 1-2-3 )))

[Yanavar]

Потому что 12N одним ходом сводится к 123

[LuckyLake]

Это если тебе предоставят такую возможность.
То есть, в начале я писал что есть позиции опасные и безопасные.
Так вот очевидно что
1-1
2-2
1-2-3
и так далее
являются безопасными позициями для нас, если мы оставили их оппоненту.
Вопрос задачи в том и состоит, что в общем виде описать безопасную ситуацию и следовательно способ как к ней прийти.
Еще раз, математически строго доказано, что любой ход из безопасной позиции делает ее опасной, и из любой опасной позиции можно сделать безопасную одним ходом.

[PSV]

]]>http://www.michurin.com.ru/online-match.shtml]]> - тут можно отрабатывать стратегию

[LuckyLake]

Ха

Изи гейм ))))

 spichki.JPG ( 147 килобайт ) Кол-во скачиваний: 38





Да и кстати.

ВНИМАНИЕ.

Обещанная вечерняя подсказка.

Воспользуйтесь нетрадиционными системами счисления.

[PSV]

Согласен

]]>]]>

[Gunner_17]

двоичной чтоли? я еще помню, что 2+2 = сто (100), но описывать систему..) вряд ли так вспомню сходу. Но попробую)

[PSV]

Нее, давайте будем использовать систему счисления шумеров

[zubr1989]

ну вот на три ряда побить легко. друго дело если рядов 8

[PSV]

От числа рядов мало что зависит , вчера ночью мне это доказали за полчаса

[dinding-a-ling]

]]>]]>http://www.michurin.com.ru/online-match.shtml]]>]]> - тут можно отрабатывать стратегию

А почему в этой вариации - "Проигрывает тот, кто берёт последнюю спичку"?
Вы уж определитесь. Или это уже не важно?)))

[Yanavar]

Фигассе, перечитал щас свое решение, и понял, что противник может свести ситуацию к 1,4,5, которая для нас проигрышная. Подумаю еще.

[LuckyLake]

А почему в этой вариации - "Проигрывает тот, кто берёт последнюю спичку"?
Вы уж определитесь. Или это уже не важно?)))

На самом деле, это не важно. Ну то есть если есть понимание, то оно для обеих ситуаций сразу.

Вечером напишу ответ, ну то есть оптимальную стратегию.
Так что, okys, думаю начальника своего ты обыграешь. Главное продумай, как замазать его предварительно

[LuckyLake]

Оптимальная стратегия игры в спички.

Идея такая. Как я уже говорил, в игре есть два состояния, опасное и нет. Опять же, как вводное было известно, что любое опасное состояние можно сделать безопасным за один ход, и что любой ход из опасной ситуации делает ее опасной. Безопасной ситуацией называется та, при которой оппонент не может одержать победу. Если оба игрока знают оптимальную стратегию, то в случае если начальная позиция опасна, то выиграет тот, кто первый ходит, в случае, если начальная позиция безопасна, то начинающий игру проиграет.

Рассмотрим самые простые безопасные ситуации.

Очевидно, что в если мы оставим оппоненту два ряда с одной спичкой в каждом, победить он не сможет. Так же и в случае, если в обоих рядах одинаковое количество. В трех рядах простейшая ситуация, гарантирующая нам победу, это ситуация 1-2-3.

Я давал пример 3-5-7, и Zubr, нашел правильный первый ход - убрать одну спичку из второго ряда. Gunner17 предположил, что общее количество спичек после нашего хода должно быть четным, и это тоже правильная мысль.

После чего я дал последнюю подсказку в виде "Воспользуйтесь нетрадиционными системами счисления". Опять же Gunner17 правильно догадался, что двоичной, но видать вспоминать было лень )))

Возьмем 1-2-3 - безопасную ситуацию. Запишем количество спичек в каждом ряду в двоичной системе.

01
10
11
если внимательно посмотреть то в каждом столбце одинаковое количество едениц. Что бы выражаться корректно, есть такая функция в логике - "исключающее или", или сложение по модулю 2. То есть результатом сложения нескольких бинарных чисел будет остаток в последнем разряде, то есть:
1+0=1
0+0=0
1+1=0
1+1+1=1 и так далее

В общем виде можно сказать, что позиция будет безопасной, если результат поразрядного сложения количества всех фишек по модулю 2 будет равен 0.

Проверим ход Зубра по этой системе.

Начальная позиция

3 - 011
5 - 101
7 - 111
В третьем столбце сумма по мод. 2 = 1 значит позиция опасна. Очевидно, надо убрать оттуда одну еденицу, а значит из любого ряда взять одну фишку. Тогда получится:

3 - 011
4 - 100
7 - 111
И безопасная позиция в итоге.

Это применимо для абсолютно любого количества рядов и фишек в них.

Но если подумать, то для простых случаев игры можно и не прибегать к двоичной системе.

В случае двух рядов, очевидно, равное количество фишек гарантирует безопасную позицию, т.к. любое число, сложенное по мод.2 поразрядно с самим собой, очевидно даст 0 в результате.

При трех рядах, опять же, если сумма фишек (в десятичной системе) в двух наименьших рядах равна наибольшему, то это практически то же самое что два ряда с равным количеством, то есть позиция безопасна.

При четырех рядах, можно искать комбинацию из суммы трех меньшх рядов и сравнивать с наибольшим, можно складывать ряды попарно, но тут вариантов будет уже больше. При пяти и более рядах, наверное уже будет проще писать в двоичной и складывать поразрядно.

Кстати, эта игра решается и для ситуации, когда спички можно брать из нескольких рядов сразу, но не более какого-то количества рядов (обозначим m рядов). В этом случае надо записывать количество спичек в двоичной системе, но складывать столбцы без учета переноса разрядом уже в m-ичной системе счисления.

Про эту игру, кстати, можно прочитать в Википедии. ]]>http://ru.wikipedia.org/wiki/Ним_(игра)]]>

Ну а я узнал о ней, когда учился в 8 или 9м классе и усердно занимался программированием, вот из этой книги:
 DSC_0098.jpg ( 365.8 килобайт ) Кол-во скачиваний: 49

Тех, кто помнит эти до пентиумные времена, наверняка проберет ностальгия.

[oykc2005]

Так что, okys, думаю начальника своего ты обыграешь. Главное продумай, как замазать его предварительно

Ну вот, теперь ещё одна задача нарисовалась, будем работать в этом направлении

[Arlley]

А меня "Пешечная дуэль" порадовала (по ссылке с Вики):
]]>http://anyintelli.com/games/pawnduel/index.php?lang=rus]]>

Не зная стратегии выиграть нереально...

[PSV]

Ну а я узнал о ней, когда учился в 8 или 9м классе и усердно занимался программированием, вот из этой книги:
 DSC_0098.jpg ( 365.8 килобайт ) Кол-во скачиваний: 49

У меня есть такая книга