Каким образом и с какой точностью можно вычислить объём памяти, который будут занимать эндшпильные таблицы Налимова для всех 32 фигур?

задан 7 Июн '17 23:15

Знать бы еще, кто этот Налимов, я и Пескарева-то не очень знаю!

(7 Июн '17 23:48) Амфибрахий

@Амфибрахий: а у меня стоит закладка на эти таблицы, и я ими иногда пользуюсь для анализа малофигурных эндшпилей! Хотя в шахматы играю очень слабо.

(8 Июн '17 0:00) falcao

Есть еще таблицы Ломоносова, хотя причем тут Ломоносов :)

(8 Июн '17 2:23) abc
10|600 символов нужно символов осталось
3

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

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

Число сочетаний из n по m будем записывать в виде C(n,m).

Итак, ставим все белые пешки: C(64,8) способов. Далее все чёрные на оставшиеся поля: C(56,8). Эти числа будут перемножаться. Можно было сделать по-другому: сначала взять C(64,16) для пешек вообще, а потом домножить на C(16,8), задавая белые пешки. Далее аналогично поступаем с остальными фигурами. Получается некоторое произведение чисел сочетаний. Выписывать его в явном виде, наверное, излишне, так как принцип ясен. Но интересно его оценить, чтобы понять, насколько оно велико. Это можно сделать при помощи компьютерных программ. Получается такое вот гигантское число:

4634726695587809641192045982323285670400000

которое имеет порядок 2^{142}. Можно теперь пофантазировать на тему того, сколько световых лет заняла бы простая запись такого количества данных (подразумевается, что нужно создать граф такого размера, а потом уже на его базе что-то вычислять). Или можно прикинуть себе размеры галактик, которое бы занимало такое устройство даже при условии, что расстояние между отдельными узлами составляло бы что-то порядка постоянной Планка или какой-то другой малой величины.

Можно попутно отметить, что число пшеничных зёрен на шахматной доске из знаменитого рассказа Перельмана в "Живой математике", равное 2^{64}-1, безнадёжно отстаёт.

Конечно, здесь рассматривается очень грубая оценка, но даже если реальное число вариантов будет 2^{130} или 2^{150} (а я думаю, за счёт превращений фигур оно будет сильно больше), принципиально это ничего не меняет.

ссылка

отвечен 7 Июн '17 23:58

@falcao, Итак, ставим все белые пешки: C(64,8) способов. - я конечно дико извиняюсь... но насколько я понимаю, белые пешки не могут стоять на первой горизонтали... а достижение восьмой горизонтали делает её уже не пешкой... чешет репу ...

Далее все чёрные на оставшиеся поля: C(56,8) - более того, ели речь идёт про 32-х фигурное окончание, то можно смело утверждать, что ни одна пешка не покинет своей вертикали... Итого, вместо C(64,8)$%\cdot$%C(56,8) должно получится $%35^8$%...

(8 Июн '17 16:28) all_exist

не сказать, что это принципиально уменьшит число комбинаций... всего примерно на $%2^{22}$$, но тем не менее...

(8 Июн '17 16:29) all_exist

за счёт превращений фигур оно будет сильно больше - его не будет, так как все пешки останутся на своих вертикалях... и не пустят пешки противника на последнюю горизонталь...

Основной геморрой тут с положением королей (оба одновременно не могут находится под шахом ... и тем более под матом)... но в оценке этим можно пренебречь... Хотя и с выходом фигур за линию пешек тоже не всё понятно...

(8 Июн '17 16:33) all_exist
1

@all_exist: у меня в самом начале было сказано, что рассматриваются не реальные шахматные позиции, а произвольные расстановки фигур на доске (типа, ребёнок взял и как-то расставил). Это всего лишь оценка или "прикидка", не более того. Ясно, что её можно как-то улучшить, но этот процесс уточнений можно продолжать и далее, поэтому на чём-то надо остановиться. Завышение здесь сделано из тех соображений, что мы не включаем сюда число позиций, когда пешек стало меньше, и они во-что-то превратились, или просто были взяты. Из общих соображений ясно, что число таких расстановок огромно.

(8 Июн '17 16:56) falcao

@falcao, чисто с целью представить себе, насколько велико будет число вариантов. - но в таком случае нужно оценивать число реальных и нереальных позиций... может реальных позиций тут мизерный процент...

(8 Июн '17 17:21) all_exist

@all_exist: задача отделения реальных позиций от нереальных выглядит достаточно сложной. Из чисто эмпирических соображений, можно считать, что если нет каких-то "очевидных" препятствий для возникновения расстановки фигур, то она может возникнуть. А получение точных оценок здесь, боюсь, не очень реально.

Кстати, на близкую тему были статьи Е.Гика в "Кванте", и у него вроде даже есть специальные книжки по теме.

(8 Июн '17 17:26) falcao

@falcao, круто! Спасибо большое-пребольшое!

(9 Июн '17 17:18) Аллочка Шакед
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,399
×1,114
×370
×211
×25

задан
7 Июн '17 23:15

показан
681 раз

обновлен
9 Июн '17 17:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru