Материал: Теория игр. Поиск выигрышной стратегии

пока в таблице расставлены единицы в позициях, которые ведут к выигрышу Пети на первом ходу и «–1» в позициях, которые ведут к выигрышу Вани на своем первом ходу (после любого первого хода Пети)

4. 
   отметим числом 2 ячейки, откуда есть ходу в серые клетки с ходом «–1»:
   

	28	29	30	31	32	33	34	35	36	37
7				2			2	1	1	1
8			2			2	-1	1	1	1
9						2	1	1	1	1
10					2	-1	1	1	1	1
11					2	1	1	1	1	1
12				2	-1	1	1	1	1	1
13				2	1	1	1	1	1	1
14			2	-1	1	1	1	1	1	1
15			2	1	1	1	1	1	1	1
16		2	-1	1	1	1	1	1	1	1
17		2	1	1	1	1	1	1	1	1
18	2	-1	1	1	1	1	1	1	1	1

в верхней строке таблицы выделены жёлтым позиции (7, 31) и (7, 34), найденные при решении предыдущего задания

5. 
   докажем, что в верхней строке больше нет позиций с кодом 2; по определению из позиции с кодом 2 есть ход в позицию с кодом «–1»; во всех позициях с кодом «–1», не попавших в рассмотренную часть таблицы, в первой куче больше 14 камней, то есть, стартовав с первой кучей из 7 камней мы не можем получить такие позиции за один ход
   
6. 
   нам нужно найти в верхней строке позиции, из которых все ходы ведут в выигрышные позиции с кодами 1 (выигрыш за 1 ход) или 2 (выигрыш за 2 хода)
   
7. 
   сразу видны две таких позиции (выделены на следующем рисунке зелёным цветом):
   

(7, 30) – возможные ходы в (7, 31), (8, 30) и (14, 30) с кодом 2 и (7, 60) с кодом 1(7, 33) – возможные ходы в позиции (7, 34) и (8, 33) с кодом 2, а также (14, 33) и (7, 66) с кодом 1:

	28	29	30	31	32	33	34	35	36	37
7			–2	2		–2	2	1	1	1
8			2			2	-1	1	1	1
9						2	1	1	1	1
10					2	-1	1	1	1	1
11					2	1	1	1	1	1
12				2	-1	1	1	1	1	1
13				2	1	1	1	1	1	1
14			2	-1	1	1	1	1	1	1
15			2	1	1	1	1	1	1	1
16		2	-1	1	1	1	1	1	1	1
17		2	1	1	1	1	1	1	1	1
18	2	-1	1	1	1	1	1	1	1	1

8. 
   вроде бы все хорошо, и можно выбрать минимальное из двух найденных значений S (30), но кроме этих ячеек есть ещё кандидат на решение – S = 17, потому что ходом из позиции (7, 17) можно получить позицию (7, 34) с кодом 2
   
9. 
   однако на самом деле позиция (7, 17) нам не подходит, докажем это, рассмотрев все возможных ходы Пети:
   

(8, 17) (14, 17) (7, 18) (7, 34)здесь жёлтым фоном выделены ходы с кодом 2 – выигрышные позиции за 2 хода (из позиции (8, 17) есть ход в (8, 34) с кодом «–1»)

10. 
    рассмотрим ход (14, 17); возможные ходы из него
    

(15, 17) (28, 17) (14, 18) (14, 34)среди них нет ни одного хода в позицию с кодом «–1», то есть, ход Пети (14, 17) не даст Ване выиграть за 2 хода; поэтому эта позиция не подходит

11. 
    Ответ: 30.
    

Решение с помощью программы (рекурсия)

1. 
   напишем программу на языке Python, которая для всех значений S выдаёт код позиции (про коды позиций см. выше)
   
2. 
   сначала поясним идею; пусть нужно определить код позиции (x, y); для этого мы должны предварительно определить коды позиций, куда можно попасть одним ходом из (x, y):
   

(x+1, y) (2x, y) (x, y+1) (x, 2y)поскольку нужно выполнить ту же самую операцию, это будет рекурсивная функция

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

1. 
   пусть эти коды [1, 2, 2, 3], то есть все возможные ходы ведут в выигрышные позиции, Петя проигрывает; он заинтересован в том, чтобы проиграть за максимальное число ходов (всячески оттягивая поражение), поэтому из этих кодов нужно выбрать максимальный и записать его со знаком минус, получаем код «–3», то есть Петя проиграет за 3 хода (на 3-м ходу Ваня выиграет)
   
2. 
   пусть эти коды [1, –2, 2, –3], то есть найдены два хода в проигрышные позиции (с кодами «–2» и «–3»), и Петя может выиграть; он заинтересован в том, чтобы выиграть за наименьшее число ходов, поэтому нужно выбрать максимальное из полученных отрицательных чисел («–2»), убрать знак минус и добавить единицу (Петя добавляет новый ход); поэтому для данного случая код клетки будет равен 3
   

4. 
   рекурсия должна заканчиваться, когда сумма x+yстала больше или равна 77; определим это значение как константу TARGET («цель»);
   

TARGET = 77такую позицию (когда игра завершена) будем обозначать кодом 0 и считать её проигрышной

, как и позиции с отрицательным кодом

5. 
   запишем первую версию функции gameResult, которая принимает два параметра - количество камней в первой и второй кучах:
   

def gameResult( x, y ):if x + y >= TARGET: return 0# рекурсивно определяем коды всех возможных ходовnextCodes = [ gameResult(x+1, y), gameResult(x*2, y),gameResult(x, y+1), gameResult(x, y*2) ]ifв nextCodes есть отрицательные или 0:res = -max(отрицательные или 0) + 1else:res = -max(nextCodes)returnres

6. 
   строки, выделенные красным цветом – это псевдокод, который нужно заменить на операторы Python; выделим из массива nextCodes все отрицательные числа и нули (соответствующие проигрышным позициям):
   

negative = [c for c in nextCodes if c <= 0]тогда условный оператор ifв nextCodes есть отрицательные или 0: может быть записан как ifnegative:res = -max(negative) + 1else:res = -max(nextCodes)получается такая функция:def gameResult( x, y ):if x + y >= TARGET: return 0# рекурсивно определяем коды всех возможных ходовnextCodes = [ gameResult(x+1, y), gameResult(x*2, y),gameResult(x, y+1), gameResult(x, y*2) ]negative = [c for c in nextCodes if c <= 0]ifnegative:res = -max(negative) + 1else:res = -max(nextCodes)returnres

7. 
   попробуем посчитать коды для всех возможных значений S от 69 = 77-7-1 до 1:
   

X = 7for S inrange(TARGET-X-1,0,-1):r = gameResult( X, S )print( "{:d} {:d}".format(S, r) )

8. 
   к сожалению, обнаруживаем, что программа работает очень медленно… Дело в том, что программа много раз вычисляет значение кода для одних и тех позиций. Чтобы этого избежать, будем запоминать их в словаре results:
   

results = {}# (1)def gameResult( x, y ):if (x,y) in results: return results[(x,y)] # (2)if x + y >= TARGET: return 0nextCodes = [ gameResult( x+1, y ), gameResult( x*2, y ),gameResult( x, y+1 ), gameResult( x, y*2 ) ]negative = [c for c in nextCodes if c <= 0]if negative:

res = -max(negative) + 1else:res = -max(nextCodes)results[(x,y)] = res # (3)return res

9. 
   добавленные строчки выделены голубым фоном; в строке (1) создаётся пустой словарь (глобальная переменная), ключом в этом словаре будет кортеж, описывающий позицию (x, y);
   
10. 
    в строке (2) мы проверяем, нет ли в словаре кода для запрошенной позиции; если есть, то сразу возвращаем этот код
    
11. 
    в строке (3) добавляем в словарь новый код запрошенной позиции
    
12. 
    теперь программа отрабатывает очень быстро, и мы видим, что позиция (7, 17), которую мы хотели проверить, на самом деле выигрышная (её код 11); это значит, что ответ на вопрос задачи 21 – это 30.
    
13. 
    Ответ: 30.
    

Решение с помощью программы (рекурсия, 2-й вариант)

1. 
   введём константы: количество камней в первой куче, цель игры,
   

N1, TARGET = 7, 77

2. 
   количество камней, которые можно добавить, и коэффициент, на который можно умножить количество камней в любой куче:
   

KADD, KMUL = 1, 2

3. 
   определим вспомогательную функцию gameOver, которая возвращает истинное логическое значение (True), если игра окончена:
   

def gameOver( n1, n2 ):return n1+n2 >= TARGET

4. 
   определим функцию win(n1,n2,byMove), которая возвращает истинное логическое значение (True), если в позиции (n1,n2) можно гарантированно выиграть не более чем за byMove ходов:
   

def win( n1, n2, byMove ):if gameOver(n1, n2): return False return lose( n1+KADD, n2, byMove-1 ) or \lose( n1*KMUL, n2, byMove-1 ) or \lose( n1, n2+KADD, byMove-1 ) or \lose( n1, n2*KMUL, byMove-1 )В первой строке проверяется условие окончания игры: если игра окончена, то тот, чья очередь ходить в этой позиции, проиграл:if gameOver(n1, n2): return False Игрок выигрывает в некоторой позиции не более чем за byMove ходов, если все его возможные ходы ведут в проигрышные (для соперника) позиции, причем при любом ходе соперник проигрывает не более чем за byMove-1 ходов:return lose( n1+KADD, n2, byMove-1 ) or \