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

[AD]

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

2. e4! Be4

Ну да, убеждает. Можно, конечно, еще про 2 ... e5 поговорить, но там тоже кошмарики

[vvvv]

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

[arqady]

vvvv в сообщении #291949 писал(а):

Уровень математического развития человечества еще не так высок...

Интересно, кто же это может оценить?

[Dan77790]

Вот поставить бы начальную позицию на IBM Roadrunner на годик-другой непрерывного анализа, тогда вопросов было бы намного меньше в шахматах) А так как это нереально, люди извращаются - придумывают всякие программы типа Rybka, Freezer, таблицы Налимова....
А от истины все так же далеки... А ведь есть еще безумно сложная японская игра Го - там доска не 8х8, как в шахматах, а ... 19х19 !
То есть, если в шахматах 10 в 125 степени позиций, то в Го их уже... 10 в 321!
И если шахматные программы мочат человека уже давно, то Го ну никак не могут запрограммировать.... Хотя идеи есть.... Го - это вообще другой уровень)

[Pavlovsky]

Шахматное программирование уже давно превратилось в пляски шаманов вокруг эвристик. Нет там математики. Никто там теорем не доказывает .

[age]

Dan77790 в сообщении #292088 писал(а):

Вот поставить бы начальную позицию на IBM Roadrunner на годик-другой непрерывного анализа, тогда вопросов было бы намного меньше в шахматах)

Это бы ничего не дало, т.к. время обдумывания каждого очередного хода растет экспоненциально. Если говорить о "честном" обсчете без эвристик и глубине обдумывания 14 ходов в минуту (7 с каждой стороны), то за год это дало бы 28 (или 14 с каждой стороны). За 9 лет - по 15 ходов.
На 28 ходов думают современные шахматные программы (правда с очень большими эвристиками).
Что же касается если ставить на такой расчет "эвристическую" программу, то она "пропускает" правильные ходы, т.к. для того, чтобы считать на 20 и более ходов сходу необходимы очень серьезные алгоритмы отсечения ветвей, в которые зачастую попадают нужные ходы. Так что с какой стороны не ткнись, а все идет к одному.

-- Чт фев 25, 2010 21:27:13 --

У меня Rybka 3.0. Иногда, когда возникают наиболее интересные позиции (даже в дебюте - например, позиция, возникшая в 6-ой партии Каспаров-DeepBlue в 1997 году, когда DeepBlue на 5-м или 6-м ходу в партии пожертвовала коня. Данная позиция относится к "новым" и непроверенным в шахматах, но компьютер выбрал именно данный вариант, после чего Каспаров начал засыпать IBM гневными письмами о "подтасовке" игры и требовать распечатки листингов ходов. Закончилась партия самым быстрым поражением в карьере Г.Каспарова - на 19 ходу).

Так вот, Рыбка за 8 часов работы ушла на глубину 26 ходов (т.е. почти 13 с каждой стороны), но она так и не "поняла", что необходимо жертвовать коня. Т.е. ее эвристики все равно пропускают (отсекают) этот ход, на какую бы глубину она не считала.

-- Чт фев 25, 2010 21:44:00 --

А вообще самым гениальным шахматистом считается Роберт (Бобби) Фишер, который так и ушел непобежденным и вроде как сошел с ума из-за шахмат.
Поэтому очень интересно посмотреть как бы он сыграл с компьютером.

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

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

[Dan77790]

age

Алехин ушел непобежденным, а Фишер просто отказался играть с Карповым - боялся он его) Вопрос кто у кого выигрывает мне ну абсолютно не интересен, мне интересно полное решение шахмат)
IBM Roadrunner, думаю, закрыл бы очень много вариантов.... Кстати, Рыбка реально что-то ход Ке6!! не хочет видеть в той партии Каспарова с Диип Блю) Может это все-таки люди там читерили?) Обычно такие форсированные линии расчитываются четко и до конца...

[mserg]

Возможно, для Вас интересной будет идея игр из черновика
http://np-soft.ru/downloads/automodel.zip

[age]

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

Просто некоторые оценочные функции слабее, некоторые проще. Лучшие работают по экспоненте. Старенькие где-то по степеням десятки. Разумеется в обоих случаях одно и то же число просчитанных позиций дает совершенно различную глубину просчета. Т.е. для 10 млн.позиций:
$10^n=10000000$, $n=7$ ходов (старые программы)
$e^n=10000000$, $n=16$ ходов (современные программы).
Но и соответственно новые оценочные функции требуют больше времени и считают меньше позиций в секунду.

Разумеется, что если идти дальше во времени, то старая программа увеличит глубину незначительно (лишь на 3 хода при увеличении времени в 1000 раз). Новая же - уже на 7 ходов.

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

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

[mserg]

to age.
Идея состоит в том, чтобы математически описать задачу так, чтобы решением этой задачи был бы алгоритм игры в шахматы. Грубо говоря, пространство поиска в этой задаче – это дерево «алгоритмов» (а не вариантов ходов!!!!) игры в шахматы.

[age]

mserg
Дерево алгоритмов? Т.е. для каждой позиции свой алгоритм? Если число позиций $\sim 10^{140}$, то выходит нужно сравнимое число алгоритмов?

[mserg]

Нет, не для каждой позиции. Алгоритм игры в шахматы создается компьютером по базе сыгранных партий. После этого его можно использовать и он остается неизменным до проигрыша. Проигранная партия вносится в базу сыгранных партий, и алгоритм пересоздается компьютером снова. И т.д.