Шахматная математика

[Лукомор]

granit201z в сообщении #1246189 писал(а):

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

(Оффтоп)

Да, это было бы гораздо лучше...
Сначала построить, а потом прийти, сюда например, и сказать:"Я вот тут построил... Смотрите, как здорово получилось!".
Но, почему-то, чаще бывает наоборот...

[granit201z]

Цитата:

Да, это было бы гораздо лучше...
Сначала построить, а потом прийти, сюда например, и сказать:"Я вот тут построил... Смотрите, как здорово получилось!".
Но, почему-то, чаще бывает наоборот...

Согласен. Но получилось как получилось. Или, точнее, как всегда))) Но мне не привыкать.

[kotenok gav]

granit201z в сообщении #1246189 писал(а):

я лучше полную сеть 5-ти фигурной игры построю, которая влезет менее чем в гигабайт, в доказательство и назидание

Так это может и влезет, но для 32-фигурной игры, всех жестких дисков Земли не хватит.

[granit201z]

Цитата:

Так это может и влезет, но для 32-фигурной игры, всех жестких дисков Земли не хватит.

С этим я пока спорить не буду. Но если хотя бы и это (5-ти фигурная) влезет, то значит, что и правильно, что я никаких учебников о шахматном программировании не читал - нет там ничего полезного. Ну а если не влезет - считайте меня демагогом)))

[rockclimber]

granit201z
Давайте я вам помогу побыстрее почувствовать себя демагогом. Число различных 5-фигурных наборов - 1000. Теперь посчитайте для каждого набора количество возможных размещений на доске...

[granit201z]

Можете немного позлорадствовать - я ошибся))) Я имею ввиду про учебники. Они все-таки мне нужны, т.к. я ими пользуюсь для решения своих задач.

Так вот: Задача о размещении 5-ти фигур на доске абсолютно идентична задаче о 8-ми ладьях из учебника Н.Я. Виленкина "Комбинаторика" 1969 г.
Суть задачи такая: сколькими способами можно разместить 8 ладей на доске. Ответ: $64!/(8!\cdot56!)=4 328 284 968$
Учитывая, что у нас таких "ладей" 5, то ответ будет несколько другим:
$64!/(5!\cdot59!)=7 624 512$
Т.е. это количество комбинаций из 5-ти фигур (если между фигурами не делать различения) на 64-х клеточной доске. Но для решения задачи о вообще всевозможных различных размещениях между фигурами нужно делать различения. Т.е. теперь вместо ЛЛЛЛЛ может быть ФбФчКбКчЛб, или КбЛчСчКчФб или и т.д.
Тут уже можно залезть в википедию. Полный аналог этой задачи - задача о размещении с повторениями.

[url]https://ru.wikipedia.org/wiki/Размещение#.D0.A0.D0.B0.D0.B7.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81_.D0.BF.D0.BE.D0.B2.D1.82.D0.BE.D1.80.D0.B5.D0.BD.D0.B8.D1.8F.D0.BC.D0.B8[/url]

Только вместо 4-х элементов, у нас 12 (Пч Лч Кч Сч КРч Фч Пб Лб Кб Сб КРб Фб), а вместо двойных комбинаций - пятерные. Т.е. ответ будет:
$12^5=248832$
Ну а теперь, чтобы ответить на вопрос, сколько вообще 5-ти фигурных позиций может быть на доске - нужно перемножить эти два числа:
$7 624 512 \cdot 248 832 = 1 897 222 569 984$
Ну вот собственно и все. До сегодняшнего дня ни разу не изучая комбинаторику, я решил задачу по ней. А все почему? А все потому, что у меня есть умение пользоваться литературой. Не изучать литературу, а именно пользоваться ей, решая интересные мне задачи. При простом изучении вы никогда не выйдете за рамки написанного, тем более, если написана неинтересная вам "нудятина".

[Xaositect]

Хорошо, но если говорить о шахматах, то решено неверно - король обязательно должен присутствовать.

[granit201z]

Цитата:

Хорошо, но если говорить о шахматах, то решено неверно - король обязательно должен присутствовать.

Так это и отлично. 1 897 222 569 984 позиции возможны в "безбашенных шахматах", т.е. таких где из правил только и всего, что одно правило: должно быть пять фигур из двенадцати возможных, размещенных на 64-х клеточной доске любым образом. То есть это такое число, что безбашеннее уже не будет при 5-ти фигурных позициях на 64-х клеточной доске. Т.е. король белый и король черный накладывают дополнительные ограничения на это число. А это значит, что "реальных" позиций будет во много раз больше чем 7 624 512, но гораздо меньше чем 1 897 222 569 984. Это уже неплохое сужение поиска, но я пока и не говорил, что этот поиск мною завершен.

[Deggial]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Дискуссионные темы (М)»
Причина переноса: велосипеды с квадратными колёсами у нас собираются в этом подфоруме.

[granit201z]

Лукомор в сообщении #1246081 писал(а):

Кстати, крестики-нолики для моделирования игр имеют ряд преимуществ:

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

[Лукомор]

granit201z в сообщении #1251705 писал(а):

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

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