Математика в шахматах

[vek88]

Видимо, надо уточнить, что шахматами сейчас занимается не просто математика, а вычислительная математика.

С этой точки зрения шахматы представляют собой прекрасный полигон для разработки и тестирования полезных вычислительных моделей. И не только при создании шахматных программ (хотя это вполне самостоятельный вызов для программистов и шахматистов).

[Hottabych]

Коровьев в сообщении #287050 писал(а):

С ума сойти! Ужель уже такие мощные шахматные программы.

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

[Circiter]

2Dan77790
Подсчитайте количество незамкнутых маршрутов коня, чтобы он побывал по одному разу во всех клетках. Для замкнутых маршрутов (без учета направления) это число равно 13267364410532.

2vek88

Цитата:

Видимо, надо уточнить, что шахматами сейчас занимается не просто математика, а вычислительная математика.

Ага, и большинство задач сводятся к проблемам (порой нерешенным) теории графов.

[deep blue]

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

[Quantrinas]

Шахматы и программирование

[age]

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

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

[AD]

age в сообщении #289787 писал(а):

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

Ждёмс ...

-- Ср фев 17, 2010 21:24:10 --

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

[Quantrinas]

AD в сообщении #289927 писал(а):

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

Вот пример

[age]

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

Вот контрпример (ход белых Nc7+):


С этой точки зрения, допустим, что выигрышная стратегия появляется в том случае, когда число ходов до эффективного шаха $N<N_{kp}$, где $N_{kp}$ - константа шахматной игры (критическое число ходов до эффективного шаха). Думаю, что для шахмат $N_{kp}\sim7-8$.
В таком случае смысл игры для белых (а ходят первыми они) появляется в том, чтобы создать на доске такую позицию, чтобы через $N$ ходов из которой можно было сделать эффективный шах (без потерь).

Если же такую позицию белым нельзя создать, т.е. существует всегда стратегия черных такая, что $N\geq N_{kp}$, то я прав и выигрыша нет.

Другими словами, если бы шахматная игра начиналась с позиции, представленной выше, то выигрывали бы всегда белые, т.к. после Nc7+ черные обязаны играть королем, после чего у белых появляется 100% возможность выиграть ладью за коня.

-- Чт фев 18, 2010 00:19:49 --

AD в сообщении #289927 писал(а):

age в сообщении #289787 писал(а):

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

Ждёмс ...

Позвольте спрятаться за тенью солнцезащитных очков.

[Dan77790]

Коровьев, age

Сейчас полностью доступны Базы Налимова для максимум 6 фигур на доске - http://www.shredderchess.com. Есть куча рассчитанных 7-фигурок, но далеко не все. О 8-фигурках нет смысла и мечтать) Ближайшие лет 50... Самый длинный мат, который я видел - 587 ходов) Ферзи носятся там по всей доске)

[age]

Dan77790
Спасибо. Открыл вот эту ссылку
http://www.shredderchess.com/online-che ... abase.html

- что-то дальше у меня не получается (и перетаскивал фигуры и нажимал на них), видимо там платный сервис?

[Dan77790]

Все правильно делаете
Может у вас Javа какая то не такая устновлена? Или вы забыли королей поставить) Без королей то не будет никакой оценки позиции)
Я постоянно юзаю этот сайт и все ок) Нажимаете на фигурку внизу, потом на клетку, куда хотите эту фигурку поместить, и все

[age]

Справился. Спасибо!

[AD]

age в сообщении #289964 писал(а):

Другими словами, если бы шахматная игра начиналась с позиции, представленной выше, то выигрывали бы всегда белые, т.к. после Nc7+ черные обязаны играть королем, после чего у белых появляется 100% возможность выиграть ладью за коня.

А что мешает устроить
1. Nc7+ Kd7
2. Na8 Nc2+
и т.д.? Не, мне кажется, пример должен быть более идиотским

[age]

AD
Мешает
2. e4! Be4
3. f3 Bf5
4. Na8 Nc2+
5. Kf2 Na1
6. Bb5+
после чего у черных не остается ни одного шанса.

Если же в 5 ходе черные не берут ладью, а берут коня, то получается размен конь за ладью.