Задача №26. Построение дерева игры. Поиск выигрышной стратегии

Автор материалов - Лада Борисовна Есакова.

В простых играх можно найти выигрышную стратегию, расписав все возможные ходы игроков. Такая схема ходов называется деревом игры.

Все позиции в простых играх делятся на выигрышные и проигрышные.

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

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

Определение выигравшего игрока при заданной начальной позиции

Пример 1.

Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 3, а во второй – 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигравшего игрока? Ответ обоснуйте.

Решение:

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

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

Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.

Таблица содержит все возможные варианты ходов второго игрока и ходы, приводящие к победе первого.

Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.

Определение выигравшего игрока для различных начальных позиций

Пример 2.

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой 7 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 7). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка – зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка. На­при­мер, при на­чаль­ных по­зи­ци­ях (6, 34), (7, 33), (9, 32) вы­иг­рыш­ная стра­те­гия есть у Пети. Чтобы вы­иг­рать, ему до­ста­точ­но удво­ить ко­ли­че­ство кам­ней во вто­рой куче.

За­да­ние 1. Для каж­дой из на­чаль­ных по­зи­ций (6, 33), (8, 32) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

За­да­ние 2. Для каж­дой из на­чаль­ных по­зи­ций (6, 32), (7, 32), (8, 31) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

За­да­ние 3. Для на­чаль­ной по­зи­ции (7, 31) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. Опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стра­те­гии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таб­ли­цы.

Решение:

За­да­ние 1. В на­чаль­ных по­зи­ци­ях (6, 33), (8, 32) вы­иг­рыш­ная стра­те­гия есть у Вани. При на­чаль­ной по­зи­ции (6, 33) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (7, 33), (12, 33), (6, 34), (6, 66). Каж­дая из этих по­зи­ций со­дер­жит менее 73 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 73 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Для по­зи­ции (8, 32) после пер­во­го хода Пети может по­лу­чить­ся одна из сле­ду­ю­щих четырёх по­зи­ций: (9, 32), (16, 32), (8, 33), (8, 64). Каж­дая из этих по­зи­ций со­дер­жит менее 73 кам­ней. При этом из любой из этих по­зи­ций Ваня может по­лу­чить по­зи­цию, со­дер­жа­щую не менее 73 кам­ней, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. Таким об­ра­зом, Ваня при любом ходе Пети вы­иг­ры­ва­ет своим пер­вым ходом.

За­да­ние 2. В на­чаль­ных по­зи­ци­ях (6, 32), (7, 32) и (8, 31) вы­иг­рыш­ная стра­те­гия есть у Пети. При на­чаль­ной по­зи­ции (6, 32) он дол­жен пер­вым ходом по­лу­чить по­зи­цию (6, 33), из на­чаль­ных по­зи­ций (7, 32) и (8, 31) Петя после пер­во­го хода дол­жен по­лу­чить по­зи­цию (8, 32). По­зи­ции (6, 33) и (8, 32) рас­смот­ре­ны при раз­бо­ре за­да­ния 1. В этих по­зи­ци­ях вы­иг­рыш­ная стра­те­гия есть у иг­ро­ка, ко­то­рый будет хо­дить вто­рым (те­перь это Петя). Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 1. Таким об­ра­зом, Петя при любой игре Вани вы­иг­ры­ва­ет своим вто­рым ходом.

За­да­ние 3. В на­чаль­ной по­зи­ции (7, 31) вы­иг­рыш­ная стра­те­гия есть у Вани. После пер­во­го хода Пети может воз­ник­нуть одна из четырёх по­зи­ций: (8, 31), (7, 32), (14, 31) и (7, 62). В по­зи­ци­ях (14, 31) и (7, 62) Ваня может вы­иг­рать одним ходом, удво­ив ко­ли­че­ство кам­ней во вто­рой куче. По­зи­ции (8, 31) и (7, 32) были рас­смот­ре­ны при раз­бо­ре за­да­ния 2. В этих по­зи­ци­ях у иг­ро­ка, ко­то­рый дол­жен сде­лать ход (те­перь это Ваня), есть вы­иг­рыш­ная стра­те­гия. Эта стра­те­гия опи­са­на при раз­бо­ре за­да­ния 2. Таким об­ра­зом, в за­ви­си­мо­сти от игры Пети Ваня вы­иг­ры­ва­ет на пер­вом или вто­ром ходу.

Ответ:

За­да­ние 1. Ваня вы­иг­ры­ва­ет своим пер­вым ходом.

За­да­ние 2. Петя вы­иг­ры­ва­ет своим вто­рым ходом.

За­да­ние 3. Ваня вы­иг­ры­ва­ет первым или вторым ходом.

Определение начальной позиции, обеспечивающей выигрыш того или иного игрока

Пример 3.

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. На­при­мер, имея кучу из 15 кам­ней, за один ход можно по­лу­чить кучу из 16 или 45 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

 Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 48. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 48 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 47.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

1. а) Ука­жи­те все такие зна­че­ния числа S, при ко­то­рых Петя может вы­иг­рать в один ход. Обос­нуй­те, что най­де­ны все нуж­ные зна­че­ния S, и ука­жи­те вы­иг­ры­ва­ю­щий ход для каж­до­го ука­зан­но­го зна­че­ния S.

б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

2. Ука­жи­те два таких зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём (а) Петя не может вы­иг­рать за один ход и (б) Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня. Для каж­до­го ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

3. Ука­жи­те зна­че­ние S, при ко­то­ром:

— у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и

— у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На рёбрах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход, в узлах — ко­ли­че­ство кам­ней в куче.

Решение:

1. а) Петя может вы­иг­рать, если 16, ..., 47. Во всех этих слу­ча­ях до­ста­точ­но утро­ить ко­ли­че­ство кам­ней. При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить кучу, в ко­то­рой боль­ше 47 кам­ней.

б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 15 кам­ней. Тогда после пер­во­го хода Петя в куче будет 16 или 45 кам­ней. В обоих слу­ча­ях Ваня утра­и­ва­ет ко­ли­че­ство кам­ней и вы­иг­ры­ва­ет в один ход.

2. Воз­мож­ные зна­че­ния S: 5 и 14. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 15 кам­ней: в пер­вом слу­чае утро­е­ни­ем, во вто­ром до­бав­ле­ни­ем од­но­го камня. Эта по­зи­ция разо­бра­на в п. 16. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.

3. Воз­мож­ное зна­че­ние S: 13. После пер­во­го хода Пети в куче будет 14 или 39 кам­ней. Если в куче ста­нет 39 кам­ней. Ваня утро­ит ко­ли­че­ство кам­ней н вы­иг­ра­ет пер­вым ходом. Си­ту­а­ция, когда в куче 14 кам­ней, уже разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

На рисунке изображено дерево игры. Выигрышные позиции подчеркнуты.

Ответ:

1.   а) S от16 до 47

б) S = 15

2. S = 5 и S = 14

3. S = 13