• 10082
  • 6
  • 3
Нравится блог?
Подписывайтесь!

Машина играет в тогызкумалак (дерево игры)

"Машина играет в шахматы" - так называется книга авторов "Каиссы" (советской шахматной программы), из которой можно почерпнуть много полезного.

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

Согласно теории игр (есть такой подраздел в математике), тогызкумалак (как и шахматы, как и го) относится к играм с полной информацией. Основные принципы написания программ для таких игр сформулировал еще в середине прошлого века Клод Шеннон, создатель теории информации.

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

У непосвященного человека может возникнуть вопрос, а возможно ли таким образом просчитать тогызкумалак до конца и на основе сделанного расчета играть идеально и безошибочно?

После первого хода белых может возникнуть 9 позиций, после ответного хода черных - 73 позиции. Программисты измеряют продолжительность партии в полуходах, поэтому будем придерживаться этой традиции. После трех полуходов имеем 613 возможных позиций, после четырех полуходов - 5 199.

Дерево игры растет экспоненциально, но пока не выглядит слишком страшным. Однако что будет дальше? После пяти полуходов - 43 184, после шести - 360 035, после семи - 3 003 052 (больше трех миллионов), после восьми - 25 166 174, после девяти - 210 521 787, после десяти - 1 766 804 407 (счет пошел уже на миллиарды), после одиннадцати - 14 811 651 049.

Таким образом, после 11 полуходов (то есть только после шести ходов белых и пяти ходов черных) возникает 15 миллиардов позиций. Это 15 миллиардов возможных партий! Если бы население всего Казахстана (16 миллионов человек), забросив все свои дела, расставили доски и воспроизвели все возможные партии после 11 полуходов, затрачивая на партию по полторы минуты, то это заняло бы почти сутки. И это всего лишь дебют, самое начало партии!

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

По моему мнению, тогызкумалак - это идеальная игра из семейства манкала. Очень удачно выбрано число лунок - 9. Если их число делать меньше (6, как в калахе), то запустив программу на несколько лет, можно получить окончательный результат игры при оптимальной игре обеих сторон. В том случае, если увеличить количество лунок, то игра приобретает затяжной характер и может продолжаться чрезмерно долго. Кстати, по этой же причине шахматы остаются в своем классическом варианте (8 на 8), несмотря на многочисленные попытки модернизировать эту игру. Даже Капабланка в свое время предлагал добавить дополнительные фигуры и увеличить размер доски, но позже понял, что это заметно удлиняет партию и перестает делать шахматы столь интересными.

Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.

Ернар Шамбаев Yernartogyz
Win or lose, sink or swim, One thing is certain we`ll never give in!
28 октября 2011, 22:06
1174

Загрузка...

Комментарии

Оставьте свой комментарий

Спасибо за открытие блога в Yvision.kz! Чтобы убедиться в отсутствии спама, все комментарии новых пользователей проходят премодерацию. Соблюдение правил нашей блог-платформы ускорит ваш переход в категорию надежных пользователей, не нуждающихся в премодерации. Обязательно прочтите наши правила по указанной ссылке: Правила

Также можно нажать Ctrl+Enter

Популярные посты

Я был удивлён, что в Азербайджане есть Казахский район

Я был удивлён, что в Азербайджане есть Казахский район

Мне как казаху по национальности очень хотелось туда попасть. Оказалось, что климат там намного суровей и люди, говорят, суровые и воинственные. Казах – город на западе Азербайджана...
alidimash
18 янв. 2017 / 21:50
  • 31000
  • 18
Астана глазами алматинских девушек. Как при таких погодных условиях можно выжить?

Астана глазами алматинских девушек. Как при таких погодных условиях можно выжить?

В спальных районах, и в высотных домах сквозь стены слышно завывание ветра. В особенности ночью. Такие звуки, я слышала, пожалуй, только по телевизору, в фильмах про метель.
Naomi_K
20 янв. 2017 / 12:36
Сильное ДТП произошло в Алматы на Тимирязева-Байзакова

Сильное ДТП произошло в Алматы на Тимирязева-Байзакова

NoComment (c) Официальный слоган EuroNews. Катастрофа на алматинской утренней трассе началась с того, что водители «Ниссана» и микровена ожидали сигнала светофора на запад по Тимирязева...
ibestreporter
17 янв. 2017 / 22:52
  • 3980
  • 5
Вейпинг безопасен? Эндрю Холл из США тоже так считал, пока что-то не пошло не так

Вейпинг безопасен? Эндрю Холл из США тоже так считал, пока что-то не пошло не так

Эндрю Холл из США считал, что вейпинг безопасен и усиленно убеждал в этом близких. Но как-то раз что-то пошло не так. Это результат взрыва хипстерского устройства - выбило 7 зубов + ожоги и раны...
Maxambet
17 янв. 2017 / 16:28
  • 4118
  • 52
Это поколение просрет страну. 20-летняя молодежь представляет из себя сказочных эльфов

Это поколение просрет страну. 20-летняя молодежь представляет из себя сказочных эльфов

Смотря в очередные пустые глаза вчерашнего студента, приходящего устраиваться на первую работу страшно становится. Потому что сравниваю с теми же китайскими студентами, которые готовы выгрызать себе мечту.
mbaitykov
18 янв. 2017 / 11:34
Разрубить сирийский узел. Казахстан как миротворец сделает невозможное?

Разрубить сирийский узел. Казахстан как миротворец сделает невозможное?

Только что в Астане начались межсирийские переговоры. Событие это примечательно не столько содержанием и ожидаемыми результатами, а самим фактом.
openqazaqstan
вчера / 13:35
  • 3464
  • 15
Становится хуже, но как-то постепенно. Беднеем, но тоже как-то не разом

Становится хуже, но как-то постепенно. Беднеем, но тоже как-то не разом

Помню, когда я уезжал и Казахстана, тут было довольно прилично, даже не смотря на то, что жить было невыносимо. Но прилично так. Мусора было меньше. Дороги чистили, вони почти не было. Да и в остальном тоже норм.
shootnix
18 янв. 2017 / 12:49
  • 3893
  • 36
Поправки в стиле «1937» не прошли. МИК отказалось от запрета анонимных комментариев

Поправки в стиле «1937» не прошли. МИК отказалось от запрета анонимных комментариев

Сегодня Министерство информации и коммуникаций исключило из законопроекта предложенные ранее нормы, предполагавшие «деанонимизацию» комментаторов и регистрацию блогеров.
openqazaqstan
20 янв. 2017 / 12:12
  • 2510
  • 22
Почему мужчины используют некоторых женщин? Случай из жизни

Почему мужчины используют некоторых женщин? Случай из жизни

Однажды мне довелось приеxать к своей сестре в другой город с ночевкой. Она живет одна и ей почти 33 и она не замужем. Лично я считаю, что её старой девой называть рано, она все еще открыта для...
Roza_pvl
19 янв. 2017 / 15:32
  • 2877
  • 94