Головоломка

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

Дерево позиций – дерево перебора.

Несмотря на то, что мы не можем точно описать дерево до уровня, который включает большинство человеческих партий (160 уровень – 80 ходов), в виду его колоссальных размеров, все же, пользуясь простыми логическими методами, мы можем установить некоторые присущие дереву свойства:

Свойство № 1 - в дереве встречаются одинаковые позиции. Действительно, уже на третьем уровне среди 8902 позиций встречаются несколько начальных позиций. (Одна из начальных позиций может возникнуть на третьем уровне дерева после следующих ходов 1. ¤f3 ¤f6. 2. ¤g1 ¤g8). Аналогично рассуждая, легко прийти к выводу, что в дереве встречаются и различные множества одинаковых «неначальных» позиций.

Свойство № 2 – дерево бесконечно – это прямо вытекает из Свойства №1 и принятого нами условия, что мы игнорируем шахматные правила «троекратного повторения позиции» и «пятидесяти ходов». Действительно, из любой начальной позиции третьего уровня можно построить точно такое же дерево, как из начальной позиции первого уровня. Таким образом, на уровнях 0, 3, 7, 11, 15 и далее до бесконечности встречаются начальные позиции.

Свойство № 3 – В дереве существуют тупиковые ветви. Действительно, из тех позиций дерева, где зафиксирован мат или пат, ветви не растут. (Пользуясь принятой терминологией, можно сказать, что подвижность в таких позициях равна нулю).

Ну, оценка сверху очень проста. Количество позиций 32 фигур на 64 клетках не превосходит плюс 31 фигуры на 64 клетках и т.д. Понятно, что последние должны остаться два короля. Понятно, что пешки взаимозаменяемы и там не , а , но мы оцениваем сверху. Вот сумма таких комбинаций и будет оценка сверху. Это будут вершины графа. А ребрами (граф может быть даже не направленный) будут ходы — если из этой позиции можно перейти в другую по законам шахмат. Очевидно, что один ход — одно ребро. Очевидно, что число рёбер тоже конечно и не превосходит число вершин. Всё, граф конечный. А вот ходить по нему можно бесконечно. Правило трёх повторений означает, что одну и ту же вершину мы посетили 3 раза.

Да хрен с ними с учёными, главное что компы даже в будущем не потянут, а будут только "по деревьям" решать плюс огромная база данных с играми. Но всё равно люди уже не противники, хорошо что пока в шахматах.

Я имел в виду за приемлемый отрезок времени.

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

На первых ходах уже давно ничего не "прорешивается вперёд". Существующая БД позволяет пошерстить по ней. Ну и окончания там есть, хотя с окончаниями всё намного проще. Вот серединка, тут да, решается.

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

Ладно, ещё раз.

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

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

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