• 11131
  • 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
1247

Загрузка...
Loading...

Комментарии

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

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

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

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

Нет ничего более вдохновляющего, чем видеть стада сайгаков. Не зря их называют «киелі»

Нет ничего более вдохновляющего, чем видеть стада сайгаков. Не зря их называют «киелі»

В начале 2000-х годов в уральской популяции оставалось только 2500 сайгаков. Сейчас благодаря охране от браконьеров их численность выросла до 100 тысяч.
theYakov
17 июля 2017 / 17:55
  • 8932
  • 3
Ресторанный консенсус в Казахстане: мужчина платит всегда

Ресторанный консенсус в Казахстане: мужчина платит всегда

Ресторанный консенсус в этой стране таков, что если речь идет именно о свидании, то оплачивает его на 100% из 100 именно мужчина. Пытаться его расшатать - это достаточно дорогое удовольствие.
convoluted
17 июля 2017 / 15:32
Решили рискнуть и обратиться к риэлторам. И этим людям мы доверяем свой ночлег?

Решили рискнуть и обратиться к риэлторам. И этим людям мы доверяем свой ночлег?

Звоним риэлтору, говорим, верните наши 15 000 тг, так как ваша клиентка нас кинула. По его словам, он вернуть деньги больше не может. Не имеет право.
decorus
17 июля 2017 / 14:48
  • 3225
  • 15
«Алматы – город, летящий под откос», или Кто заказал утку у российского блогера

«Алматы – город, летящий под откос», или Кто заказал утку у российского блогера

Некий блогер Сергей Никитский неустанно пишет о Казахстане, Астане, Экспо и посвящает два материала Алматы, причём подчёркнуто называет город Алма-Ата.
Langdon
19 июля 2017 / 15:44
  • 3408
  • 56
Польша – страна простых решений. Почему они смогли, а мы еще нет?

Польша – страна простых решений. Почему они смогли, а мы еще нет?

В Польше вообще очень много понятного и простого – инфраструктура, коммуникации и дороги прежде всего, льготы в образовании, поляки вообще получают его бесплатно. А урожай побольше нашего.
Shimanskaya
17 июля 2017 / 16:08
  • 3360
  • 37
«Язык мой – враг мой», или 7 причин никогда не разговаривать с полицией

«Язык мой – враг мой», или 7 причин никогда не разговаривать с полицией

На этот раз пост очень важный и необходим к прочтению каждым! Не поленитесь и уделите время прочтению. Ни в коем случае, не разговаривайте с полицейскими до прихода вашего адвоката!
asselsabekova
18 июля 2017 / 14:19
  • 3157
  • 31
Один из способов выиграть суд против коллекторов

Один из способов выиграть суд против коллекторов

Сегодня в своем посте я постараюсь рассказать, как выиграть суд против некоторых коллекторских компании в нашей стране. Чем отличается коллекторское агенство от обычного банка?
Advokot
18 июля 2017 / 15:31
  • 2966
  • 10
Книга, которая сэкономит вам 150 тысяч долларов и два года жизни

Книга, которая сэкономит вам 150 тысяч долларов и два года жизни

Автор утверждает, что программы МБА не дают никакого позитивного выхлопа, если ты уже не являешься владельцем или наследником прибыльного бизнеса. Знания МБА можно получить бесплатно, уверяет он.
Aks_Ras
19 июля 2017 / 16:28
  • 2551
  • 2
Госорганы, ответственные за жизни детей, хранят молчание. У них в отчетах все хорошо

Госорганы, ответственные за жизни детей, хранят молчание. У них в отчетах все хорошо

Вчера все информационные агентства страны передали сообщение, которое заставило забиться в ужасе сердца всех матерей страны. В мусорном контейнере города Сатпаев было обнаружено тело новорожденной девочки.
AliyaSadyrbaeva
19 июля 2017 / 11:06
  • 2259
  • 18