Введение

Кала — это современная вариация древнего семейства игр манкала, самая ранняя известная версия которой была найдена вырезанной на каменной плите в пирамиде Хеопса в XVI веке до нашей эры. Вариант Кала был разработан в Соединенных Штатах Уильямом Джулиусом Чемпионом-младшим в 1940 году. Иногда эту игру также называют «Калахари», возможно, из-за ложной этимологии, связанной с пустыней Калахари в Намибии. В большинстве своих вариаций Кала является решённой игрой, в которой первый игрок побеждает при идеальной игре обоих участников. Правило «пирога» можно использовать для уравновешивания преимущества первого игрока.

Стандартный игровой процесс

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

Пример поворота

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

Реализация видеоигр

В 1991 году была создана DOS-версия игры (под названием Kalakh). Начальная позиция соответствует "стандартному" варианту с 6 семенами в каждой лунке и 6 домами. Другой вариант, "Bantumi", можно найти в телефоне Nokia 3310.

Вариации

Игра может начинаться с количества семян в каждом доме, отличного от четырех. Для описания этих вариаций разработана номенклатура: Kalah(h,s), где h обозначает количество домов с каждой стороны, а s – количество семян, с которых начинается игра в каждом доме. В целом, чем больше семян, тем сложнее игра. Кала с тремя, четырьмя, пятью и шестью семенами решена, и при идеальной игре начинающий игрок всегда побеждает. Поэтому некоторые веб-сайты реализовали игру с правилом "pie rule", чтобы сделать её более справедливой, или разрешают второму игроку переместить одно семя из любого дома в любой другой перед началом игры, что приводит к эффективному количеству в 144 различных игр. Альтернативное правило предполагает посев в направлении по часовой стрелке, требуя большего количества камней для посева за один ход, чтобы достичь магазина. Вариант "Пустой захват": если последнее посеянное семя попадает в пустой дом, принадлежащий игроку, даже если противоположный дом пуст, последнее семя захватывается и помещается в магазин игрока. В варианте "Seed On" захваты не производятся при окончании хода в пустом доме, но когда последнее семя попадает в непустой дом с любой стороны доски, это семя и все семена из этого дома сеются, так что ход заканчивается только тогда, когда последнее семя попадает в пустой дом. Альтернативные правила либо учитывают оставшиеся семена в конце игры в качестве части счета игрока, который опустошил свои дома, либо не учитывают их вовсе.

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

Как уже упоминалось выше, если последнее посеянное игроком семя попадает в его магазин, игрок получает дополнительный ход. Опытный игрок может использовать это правило, чтобы последовательно выполнять множество дополнительных ходов. Определенные конфигурации ряда на доске можно таким образом очистить за один ход, то есть игрок может захватить все камни в своем ряду, как показано на рисунке справа. Самая длинная такая цепочка на стандартной доске Калаха с 6 лунками длится 17 ходов. На доске с общим числом n лунок, узоры семян, которые можно таким образом очистить за один ход, стали объектом математического изучения. Можно доказать, что для любого n существует ровно один узор, который можно очистить ровно за n ходов, или, что эквивалентно, ровно один узор, состоящий ровно из n семян. Для этих узоров требуются произвольно длинные ряды лунок и увеличение n. Например, как видно на рисунке справа, уникальный узор из 5 семян требует всего 3 лунки, а узор из 17 семян – 6 лунок. Связь между необходимым количеством лунок и количеством семян можно описать следующим образом. Пусть s(n) обозначает минимальное количество семян, необходимое для очистки n лунок. Тогда

где символ обозначает асимптотическую эквивалентность, то есть , или, что эквивалентно, .