Калах

редактировать

Калах
Звания	Два
Посев	Один круг
Регион	США, Соединенное Королевство

Kalah, также называемое Kalaha или Mancala, это игра в манкале семья изобрела в США Уильям Джулиус Чэмпион младший в 1940 году. Эту игру иногда также называют «Калахари», возможно, по ложной этимологии из Калахари. пустыня в Намибии.

Как наиболее популярный и коммерчески доступный вариант манкалы на Западе, Кала также иногда упоминается как Варри или Авари, хотя эти названия более точно относятся к игре Oware.

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

Пример хода

Игрок начинает сеять из выделенного дома.

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

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

В игре есть доска Калаха и ряд семян или жетонов. На доске по 6 ямок, называемых домиками, с каждой стороны; и большая яма, называемая конечной зоной, на каждом конце. Цель игры - захватить больше семян, чем противник.

В начале игры в каждый дом кладется по четыре семени. Это традиционный метод.
Каждый игрок управляет шестью домами и их семенами на стороне игрока. Счет игрока - это количество семян в магазине справа от него.
Игроки по очереди сеют свои семена. В свой ход игрок убирает все семена из одного из домов под его контролем. Двигаясь против часовой стрелки, игрок по очереди бросает по одному семени в каждый дом, включая собственный магазин игрока, но не его оппонент.
Если последнее посеянное семя попадает в пустой дом, принадлежащий игроку, и наоборот дом содержит семена, и последнее, и противоположное семена захватываются и помещаются в магазин игрока.
Если последнее посеянное семя попадает в магазин игрока, игрок получает дополнительный ход. Нет ограничений на количество ходов, которые игрок может сделать в свой ход.
Когда у одного игрока больше нет семян ни в одном из домов, игра заканчивается. Другой игрок перемещает все оставшиеся семена в свой магазин, и игрок с наибольшим количеством семян в его магазине выигрывает.

Игра может закончиться ничьей.

Содержание

1 Варианты
2 Компьютерный анализ Калах
- 2.1 Калах (6,4)
- 2.2 Калах (6,5)
- 2.3 Калах (6,6)
3 Математический анализ
4 Терминология и тактика
5 Ссылки
6 Внешние ссылки

Варианты

Игра может начинаться с количеством семян в каждом доме, отличным от четырех. Для описания этих вариантов была разработана номенклатура: Kalah (h, s), где h обозначает количество домов с каждой стороны, а s обозначает количество семян, которые начинаются в каждом доме. В целом, чем больше семян, тем сложнее становится игра. Калах с тремя, четырьмя, пятью и шестью посевами был решен, при этом первый игрок всегда выигрывает при идеальной игре. Так, некоторые веб-сайты внедрили игру с правилом круговой диаграммы, чтобы сделать ее справедливой.
Альтернативное правило предусматривает, что игроки сеют по часовой стрелке, требуя, чтобы за один ход было засеяно больше камней.
Вариант «Пустой захват»: если последнее посеянное семя приземляется в пустой дом, принадлежащий игроку, даже если противоположный дом пуст, последнее семя захватывается и помещается в магазин игрока.
Альтернативное правило не учитывает оставшиеся семена как часть счета противника в конце игры.

Компьютерный анализ Калаха

Марк Роулингс написал компьютер Программа для всестороннего анализа как «стандартной» версии Kalah, так и версии «пустого захвата», которая является основным вариантом. Анализ стал возможным благодаря созданию самой большой базы данных эндшпиля, когда-либо созданной для Калаха. Они включают в себя идеальный результат игры из всех 38 902 940 896 позиций с 34 или меньшим количеством семян. В 2015 году впервые в истории каждый из начальных ходов для стандартной версии Калаха (6,4) и Калаха (6,5) был количественно определен: Калах (6,4) - это доказанная победа с 8 для первый игрок и Калах (6,5) - это доказанная победа с разницей в 10 для первого игрока. Кроме того, Калах (6,6) со стандартными правилами доказал свою победу как минимум на 4. Дальнейший анализ Калах (6,6) со стандартными правилами продолжается.

Для версии «пустого захвата» Джеффри Ирвинг и Джерун Донкерс (2000) доказали, что Калах (6,4) - это победа на 10 для первого игрока с идеальной игрой, а Калах (6,5) - выигрыш 12 для первого игрока с идеальной игрой. Андерс Карстенсен (2011) доказал, что Калах (6,6) стал победой для первого игрока. Марк Роулингс (2015) расширил эти результаты «пустого захвата», полностью определив начальные шаги для Калаха (6,4), Калаха (6,5) и Калаха (6,6). Проведя в общей сложности 106 поисков и более 55 триллионов узлов, он доказал, что Калах (6,6) - это выигрыш с 2-мя выигрышами для первого игрока с идеальной игрой. Это был неожиданный результат, учитывая, что варианты «4-посевной» и «5-посевной» дают выигрыш на 10 и 12 соответственно. Калах (6,6) чрезвычайно глубок и сложен по сравнению с вариантами с 4 и 5 начальными числами, которые теперь можно решить за доли секунды и менее чем за минуту соответственно.

Базы данных финальных игр, созданные Марком Роулингсом, были загружены в оперативную память во время инициализации программы (загрузка занимает 17 минут). Таким образом, программа могла работать на компьютере с 32 ГБ ОЗУ, базы данных с 30 и 33 начальными значениями не загружались.

Подсчет базы данных эндшпиля: общий подсчет количества позиций семян ----------------------------------- -------- 2-25 1851010435 1851010435 2705662765 26 854652330 27 1202919536 3908582301 28 1675581372 5584163673 29 2311244928 7895408601 30 3158812704 11054221305 31 4279807392 15334028697 32 5751132555 21085161252 33 7668335248 28753496500 34 10149444396 38902940896 ---------- ---------------------------------

Для следующих разделов ящики пронумерованы, как показано, с люфтом в направлении против часовой стрелки. Юг перемещается из ящиков с 1 по 6, а Север перемещается из ящиков с 8 по 13. Ячейка 14 - это магазин Севера, а ячейка 7 - это магазин Юга.

<--- North ------------------------ 13 12 11 10 9 8 14 7 1 2 3 4 5 6 ------------------------ South --->

Калах (6,4)

Начальная позиция с 4 семенами в каждой ячейке:

<--- North ------------------------ 4 4 4 4 4 4 0 0 4 4 4 4 4 4 ------------------------ South --->

В следующих таблицах показаны результаты каждого из 10 возможных ходов первого игрока (предполагается, что сначала идет Юг) для обоих стандартные правила и для варианта «пустой захват». Обратите внимание, что есть 10 возможных первых ходов, поскольку ходы из корзины 3 приводят к «повторному ходу». Глубина поиска продолжалась до конца игры.

Стандартные правила: результат хода идеальное продолжение игры ------------------------------------ ------------------- 1 проигрывает на 14 10 13 3 9 13 12 1 13 11 5 13 2 проигрывает на 10 10 13 5 9 13 8 4 10 13 8 5 3 -1 проигрыш на 6 10 11 2 13 1 12 1 13 9 4 12 3-2 ничья 10 13 5 9 13 8 3 11 1 13 10 3-4 победа на 2 10 9 13 2 1 12 3 5 8 12 13 3- 5 побед 4 9 10 2 5 12 1 2 11 2 13 5 3-6 побед 8 9 8 2 12 6 5 11 6 1 6 5 4 проигрыш 2 10 12 2 4 13 1 5 9 13 12 13 5 проиграть 8 10 9 11 2 5 10 1 8 4 12 5 6 выиграть 4 9 12 2 6 1 11 4 10 6 5 13 ----------------------- --------------------------------

Вариант "Пустой захват": результат хода идеальное продолжение игры - -------------------------------------------------- ---- 1 проигрыш на 14 10 13 4 9 13 11 2 13 8 13 10 2 проиграл на 8 10 13 5 9 13 8 4 10 13 9 5 3 1 проиграл на 8 10 11 4 9 12 2 10 5 11 12 9 3-2 проигрывают 2 10 13 5 9 13 8 3 11 5 13 10 3-4 выигрывают 2 10 9 13 2 1 12 3 5 8 12 13 3-5 выигрывают 4 9 11 2 4 8 12 5 13 5 11 4 3-6 выигрывает 10 9 8 4 11 6 2 6 4 9 5 13 4 проигрывает 2 10 12 2 5 9 8 12 9 4 10 11 5 проиграть с 6 10 9 11 4 8 13 5 6 4 12 6 6 выиграть с 4 9 12 2 6 1 11 4 10 6 5 13 --------------- ----------------------------------------

Калах (6, 5)

Начальная позиция с 5 семенами в каждой ячейке:

<--- North ------------------------ 5 5 5 5 5 5 0 0 5 5 5 5 5 5 ------------------------ South --->

В следующих таблицах показаны результаты каждого из 10 возможных ходов первого игрока (предполагается, что сначала ходы на юг) как для стандартных правил, так и для " пустой захват »вариант. Обратите внимание, что есть 10 возможных первых ходов, поскольку ходы из корзины 2 приводят к «повторному ходу». Глубина поиска продолжалась до конца игры.

Стандартные правила: результат хода идеальное продолжение игры ------------------------------------ ------------------- 1 проигрыш на 10 9 11 4 8 13 2 9 6 3 11 13 2-1 проигрыш на 4 9 10 2 12 1 11 3 12 8 11 1 2–3 победа 10 10 1 6 9 5 13 6 2 8 4 13 2–4 победа 10 8 11 1 6 9 2 13 11 4 12 6 2-5 побед 8 8 10 1 6 9 5 13 12 2 13 11 2-6 ничья 8 11 1 6 3 11 6 5 12 6 8 3 выигрывает 2 9 8 12 1 4 11 2 12 10 4 3 4 выигрывает 2 8 11 1 5 12 3 10 5 2 11 6 5 выигрывает 2 8 12 1 4 9 2 12 4 9 3 11 6 галстук 8 12 1 6 4 10 6 2 11 4 3 ------------------------- ------------------------------

Вариант "Пустой захват": результат хода идеальное продолжение игры --- -------------------------------------------------- - 1 проигрыш на 10 9 12 6 8 12 11 2 8 6 5 12 2-1 проигрыш на 6 9 10 2 12 4 8 9 3 10 11 3 2-3 побед на 12 8 10 1 6 10 5 13 9 6 4 11 2-4 выигрывает 8 8 9 1 6 11 4 13 10 4 13 9 2-5 выигрывает 8 8 10 1 6 9 5 13 12 3 13 6 2-6 проигрывает 2 8 11 1 6 5 9 6 3 11 12 5 3 выигрывает 2 9 8 12 1 4 11 2 10 4 5 10 4 ничья 8 11 1 5 12 3 9 5 2 11 3 5 ничья 8 10 1 4 12 5 1 1 2 9 4 13 6 галстук 8 12 1 6 4 9 6 2 12 6 5 -------------------------------- -----------------------

Калах (6,6)

Исходная позиция с 6 семенами в каждом бункере:

<--- North ------------------------ 6 6 6 6 6 6 0 0 6 6 6 6 6 6 ------------------------ South --->

В следующих таблицах показаны результаты каждого из 10 возможных ходов первого игрока (предполагается, что сначала ходы на юг) для варианта «пустой захват» и текущий статус результатов для стандартного варианта. Обратите внимание, что есть 10 возможных первых ходов, поскольку ходы из корзины 1 приводят к «повторному ходу». Глубина поиска варианта «пустой захват» продолжалась до конца игры.

«Стандартный» вариант: (Результаты все еще вычисляются Марком Роулингсом.) Результат перемещения -------------------------- ----------------------------- 1-2 подтвержденных победы, минимум 2 1-3 подтвержденных победы минимум 4 1 -4 1-5 1-6 доказанных проигрышей, по крайней мере, 2 2 с тенденцией к выигрышу 3 4 5 6 доказанных потерь, по крайней мере, на 2 ------------------- ------------------------------------ Оставшиеся ходы (1-4, 1-5, 3, 4 и 5) являются вероятными связями, основанными на очень глубоких поисках, однако результат еще не доказан.

Вариант «Пустой захват»: результат хода идеальное продолжение игры --------------------------------- ---------------------- 1-2 выигрыша у 2 10 3 12 4 8 6 10 11 6 3... 1-3 выигрыша у 2 11 1 8 2 10 6 8 3 11 5... 1-4 связка 10 3 12 5 10 3 9 1 12 3... 1-5 связка 9 4 8 3 10 2 10 4 1 9... 1-6 связка 10 4 9 6 3 11 6 8 2 10... 2 выигрыша 2 12 4 10 1 12 8 1 11 3 9... 3 ничья 10 5 12 4 11 1 12 8 4 3... 4 ничья 10 3 11 1 9 5 11 2 10 8... 5 ничья 10 3 11 4 12 2 11 4 10 5... 6 проигрыш на 2 10 3 8 6 4 13 1 10 13 8... ---------- ---------------------------------------------

Разбивка 55+ триллионов узлов, найденных для решения варианта Kalah с "пустым захватом" (6,6):

время перемещения (сек), поиск узлов ----------- ----------------------------- 1-2 305,791 2,214,209,715,560 1-3 403,744 2,872,262,354,066 1-4 401,349 2,335,350,353,288 1-5 317,795 1,886,991,523,192 1 -6 392,923 2,313,607,567,702 2 1,692,886 9,910,945,999,186 3 1,296,141 7,398,319,653,760 4 1,411,091 9,623,816,064,478 5 1,607,514 9,318,824,643,697 6 1,354,845 7,824,794,014,305 ---------------------------------------- всего 9,184,079 55,699,121,889,234

Математический анализ

Эту модель можно очистить за один ход, сыграв ямы 1, 3, 1, 2 и 1 в указанном порядке, объединив пять ходов.

Этот образец камней может быть захвачен за один ход. один ход, объединяя 17 последовательных ходов. Это самая длинная такая цепочка из возможных на стандартной доске с 6 ямами.

Как упоминалось выше, если последнее посеянное игроком семя попадает в магазин этого игрока, игрок получает дополнительный ход. Умный игрок может воспользоваться этим правилом, чтобы связать много-много дополнительных ходов. Таким образом, определенные конфигурации ряда доски могут быть очищены за один ход, то есть игрок может захватить все камни в своем ряду, как показано справа. Самая длинная такая цепочка на стандартной доске Кала из шести ям длится семнадцать ходов. На обычной доске с n ямами образцы семян, которые можно очистить таким образом за один ход, были объектом математического исследования. Можно доказать, что для всех n существует один и только один шаблон, который можно очистить ровно за n ходов, или, что то же самое, один и только один очищаемый шаблон, состоящий ровно из n начальных чисел.

Эти шаблоны требуют произвольно длинных рядов ямок и n увеличений. Например, справа можно увидеть, что для уникального шаблона с 5 семенами требуется только 3 ямки, а для шаблона с 17 семенами требуется 6 ямок. Связь между необходимым количеством ямок и количеством семян можно описать следующим образом. Пусть s (n) обозначает минимальное количество семян, для очистки которых требуется n ямок. Тогда $s (n) ∼ n 2 π {\ displaystyle s (n) \ sim {\ frac {n ^ {2}} {\ pi}}}$ ${\ displaystyle s (n) \ sim {\ frac {n ^ {2} } {\ pi}}}$ , где символ $∼ {\ textstyle \ sim}$ ${\ textstyle \ sim}$ обозначает асимптотическую эквивалентность, то есть $lim n → ∞ s (n) n 2 / π = 1 {\ displaystyle \ lim _ {n \ to \ infty} {\ frac {s (n)} {n ^ {2} / \ pi}} = 1}$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {s (n)} {n ^ {2} / \ pi}} = 1}$ , или, что эквивалентно, $lim n → ∞ n 2 s (n) = π {\ displaystyle \ lim _ {n \ to \ infty} {\ frac {n ^ {2}} {s (n)}} = \ pi}$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {n ^ {2}} {s (n)}} = \ pi}$ .

Терминология и тактика

Базовый аспекты игры (Крис Бэнди):

Тайник: дом с семенами в нем, особенно.
Удар: действие, которое приводит к захвату тайника противника.
Цель: пустой дом, в который вы приземляетесь, в чтобы захватить тайник противника.
Атака: ход, который ставит вас в положение, в котором вы можете нанести удар в следующий ход.
Блок: ход, устраняющий угрозу, создаваемую оппонентом атака.
Последовательность: серия движений за один ход (достигается постоянным приземлением в вашем собственном магазине).
Двойной: атака вражеского тайника двумя собственными домами одновременно.
Противодействие: ответ на атаку собственной атакой (вместо блокировки).

Есть два типа ударов:

Короткий удар: опустошение дома 1-5 семенами.
Долгая забастовка: опустошение птичника 8-13 семенами. Длинные удары труднее обнаружить, и в среднем они дают вам на 2 семени больше (одно из семени, которое вы положили в свой магазин, и одно из семени, которое вы положили в тайник, который вы наносите).

Есть три типа блоков :

Уклонение: опустошите атакованный дом.
Укрытие: очистите дом, чтобы заполнить целевую дыру противника.
Нейтрализация: захватить атакующий дом (обычно это доступно только если противник допустил грубую ошибку).

Есть пять уровней тайников:

Короткие нападающие: 1-5 семян
Секвенсоры: 6 семян
Бесполезно: 7 семян
Длинные нападающие: 8-13 семян
Обертки: 14+ семян

Поскольку даже новички могут обнаруживать открытые атаки (есть только шесть мест для проверки), более продвинутые игроки организуют скрытые удары. скрытый удар - это когда вы используете последовательность, чтобы начать атаку и нанести удар в один ход. Например (используя диаграмму выше), у вас 1 семя в 5 и 6, а у вашего оппонента есть тайник в 8. Вы можете начать атаку, опустошив 6, а затем нанести короткий удар 5 в том же ходу. Такого рода атаку заметить труднее, чем открытую.

Еще более совершенная форма скрытых ударов - это скрытые удары. Скрытый удар - это когда вы увеличиваете один из своих домов в последовательности, чтобы открыть атаку. Например, у вас есть 2 семени в 5 и 7 семян в 6, а у вашего оппонента есть тайник в 13. Вы можете начать атаку, опустошив 5 семян, таким образом увеличивая дом с 6 до 8 семян. Затем вы можете нанести долгий удар с 6, забрав 13 тайник.

Ссылки

^Solving Kalah Джеффри Ирвинг, Йерун Донкерс и Джос Уйервейк.
^Решение (6,6) -Калаха Андерса Карстенсена.
^ Broline, Duane M.; Леб, Дэниел Э. (1995-02-08). «Комбинаторика игр типа манкала: Ayo, Tchoukaitlon и 1 / π». arXiv : math / 9502225.

Внешние ссылки

Портал игр