История развития компьютерных шахмат

Тема в разделе "Машинное отделение", создана пользователем GlazAlmaz, 9 апр 2009.

  1. TopicStarter Overlay

    GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
  2. Tsukrov Учаcтник

    • Участник
    Рег.:
    10.08.2007
    Сообщения:
    65
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Вообще:
    Хорошая статья, но какая-то схематичная. Реши, о чём именно хочешь писать.
    Там пласты и пласты.

    Важный недостаток: нет ссылок на развитие отдельных тем.
    И картинок!

    По истории.
    Тьюринг сыграл на бумажечке. Файст и Томпсон реализовали для ChessBase. Сейчас на Pocket PC почти точная копия машинки Тьюринга играет где-то на 1500.

    Альфа-Бету придумали параллельно и ещё уточняли. При всей простоте, она требует мыслить с поворотами.
    Брудно не забываем из патриотических соображений.

    А дальше имена и имена.
    Донской, Кнут, Бил, Райнфельд, Перл, Плаат...

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

    Открытые темы: Шоги (в меньшей степени), Го.
  3. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Tsurkov, машина Тьюринга - это не шахматная программа, это математическое построение, предназначенное для уточнения понятия алгоритма.
    Машину Тьюринга можно рассматривать как упрощенную модель ЭВМ. И никакого отношения она к шахматам не имеет.
    http://ru.wikipedia.org/wiki/Машина_тьюринга
    И программа играющая в 1500 - не точная копия машины Тьюринга, а шахматная программа играющая на эмуляторе машины Тьюринга.
  4. TopicStarter Overlay

    GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
    думаю, больше именно в историю, во всяком случае до 1990-х
    например, как менялась система оценок позиции? как вообще первые программы пытались оценивать позу? кроме материального соотношения

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    По сути оценка Каиссы по набору признаков была не хуже ОФ современных программ. Веса были плохие.
  6. Tsukrov Учаcтник

    • Участник
    Рег.:
    10.08.2007
    Сообщения:
    65
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Обижаете, Сергей, на ровном месте.

    Я не имел в виду ту машину Тьюринга.
    Речь идёт о "движке" Тьюринга. Мы же употребляем "машинка Морша".
    Движок Тьюринга работает не на машине Тьюринга, а на random access машине.

    Оценка у него была забавная. Он делил материал на материал.
    Достаточно формальное описание алгоритма без "внутри у ней ионка" можно найти в Сети или сборнике статей Алана Тьюринга.

    В кассу ещё старый анекдот про оценку.
    Бил как-то заменил оценочную функцию генератором случайных чисел. Программа продолжала играть сильнее с увеличением глубины перебора.

    "Королева" сильна не потому, что у неё груди корона, а потому, что мобильна. Больше мобильность фигур - больше подузлов у узла - больше оценка из случайных.
  7. Tsukrov Учаcтник

    • Участник
    Рег.:
    10.08.2007
    Сообщения:
    65
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Там много обычной академической истории.
    Такой-то уточнил то-то, этот скорректировал оценку. У Кнута есть классическая статья с обзором.

    История с душком - "троллинг" Берлинером Ботвинника. Все знают, все молчат. А Осипов дражнится.

    Очень важный вопрос: почему поиск, основанный на ненадёжных оченках работает лучше с увеличением глубины. Даже с самой дурной оценкой есть улучшение. (см. анекдот про Била).
    Половина работ посвящены анализу этого вопроса.
    Ответ, предположительно, в высокой неравномерности и зависимости оценок.
  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Прошу прощения :) Поищу на эту тему в сети.
    Видимо о разных движках говорим - есть движок именно для машины Тьюринга.
    А насчет деления - самая правильная оценка:
    Делаем две оценки - Оценка победы, и симметричная (относительно сторон) ничейная оценка.
    Все оценки должны быть >=0
    Теперь оценка позиции равна (WinWhite-WinBlack)/(WinWhite+WinBlack+Draw)
    И очень просто делается контемпт.
    Например для игры на победу, и оценки победы 3, ничьи 1, поражения 0 -
    (WinWhite*2-WinBlack)/(WinWhite+WinBlack+Draw)
  9. 17 Учаcтник

    • Участник
    Рег.:
    07.04.2008
    Сообщения:
    1.451
    Симпатии:
    13
    Репутация:
    0
    Оффлайн
    http://www.chessbase.com/download/download2.asp

    Turing

    Chess engine for Fritz by Mathias Feist and Ken Thompson which implements the famous paper machine by Alan Turing. The orginal set of rules was incomplete and unclear in several points, which are discussed below.
    1. no mention was made of stalemate; detection was added with a positional evaluation of 0.0, which seemed to be the most logical.
    2. a move gets a bonus if threatening mate in 1; a threat obviously means a nullmove for the other side which is illegal if the move was giving check. Still it may be a mate in 1 move. This was ignored, the move just gets the bonus for a checking move.
    3. algorithm enhanced so that the engine may play with both sides, i.e. everything logically negated if black to move.
    4. iterative deepening added to allow higher search depths.
    5. a recapture is not made entirely clear: it is considered to be a capture to the same square as the previous move.
    6. rule d) is not clear about checks/enemy pieces; a wKe1 and a wPe4 give the vulnerability of e2+e3, but a bPe4 gives an additional vulnerability of e4. Doesn't sound logical.
    7. calculating the material value is impossible if one side is left with the king only. A division by zero would occur. In this case the material value is material+1.0 of the other side.

    The algorithm is based on material value, at the root moves with equal material values are resolved by positional values which are shown as the evaluation. This is not completely satisfying since the positional values are rather "jerky" and the more important material values are hidden.
    You download a setup program which allows you to install the engine in the Fritz directory.
    Download Turing Engine
  10. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Что-то я никак не могу найти шахматную прграмму для машины Тьюринга, хотя где-то явно что-то такое видел...
  11. 17 Учаcтник

    • Участник
    Рег.:
    07.04.2008
    Сообщения:
    1.451
    Симпатии:
    13
    Репутация:
    0
    Оффлайн
    http://www.chessbase.com/download/download2.asp
    в конце!

    Я тоже где-то видел `бумажки`, но тоже не припоминаю... Кажеться там были у chessbase, но они променили страницу!
  12. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    8
    Репутация:
    0
    Оффлайн
    Корифей это кто? Искусственная глупость это что?
  13. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    384
    Симпатии:
    361
    Репутация:
    10
    Оффлайн
    Это о чем?
    Сижу себе тихо, никого не трогаю, исходники Рыбки никому не даю. Чего еще надо?
  14. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.138
    Симпатии:
    2.373
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    1. Описывать Deep Blue как "шестипроцессорный суперкомпьютер" не совсем точно.
    См. http://sjeng.org/ftp/deepblue.pdf

    2. "Каисса" была всё-таки программой, а не "шахматным компьютером".

    3. Наряду с именами Арлазарова и Брудно, мне кажется, достойны упоминания Александр Битман (самый сильный шахматист в команде Каиссы, мастер), Михаил Донской, Усков...

    4. Количество шахматных движков перевалило за сотню не "сегодня", а лет 5...7 назад. Их уже за 300, если даже считать только названия, а не версии.
  15. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.138
    Симпатии:
    2.373
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    И ещё. Поскольку статья чисто компилятивная, хорошо бы дать обширный список ссылок на первоисточники, где все эти вопросы освещены глубже и из первых рук (авторами программ, участниками чемпионатов и т.д).
  16. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    122
    Репутация:
    1
    Оффлайн
    А ещё бы хорошо бы цельное произведение, труд, энциклопедию издать на эту тему. В красивом кожаном переплёте. "Эх, мечты, мечты, где ваша сладость?" :)
  17. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Адельского-Вельского еще забыли. И насчет авторства альфа-беты не всё так однозначно.
  18. TopicStarter Overlay

    GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
    WinPooh
    учту :)
    в общем, поизучаю еще инфу разную...
  19. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.138
    Симпатии:
    2.373
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Да, а самое главное - в Го нет никаких цветных поясов. Это я вам как второй кю говорю :)
  20. Tsukrov Учаcтник

    • Участник
    Рег.:
    10.08.2007
    Сообщения:
    65
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Это про программы с приятным гандикапом.
    Которые играют сильно, но спекулятивно. И красиво, по-человечески лажают.

    Сказал, кажется, или Файст, или Вюлленвебер.
  21. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    Замечаний много, особенно по цифрам. А еще есть и по принципиальным соображениям. Например Белл осуществляла не 180 000 операций в секунду, а гораздо больше, но ходов рассматривала ( пернодес ) 20 000.
    Это вообще разные вещи операций и ходов в секунду. Сервер, игравший с Крамником в 2002 году, вообще не стоит упоминания в разделе истории. И дата не указана. Проще указать что он 4млн. позиций считал в секунду.
    Рядовому пользователю такая байда действительно недоступна, кстати у нее не 2 , а больше процессоров. Но пользователь может сходить в любой магазин и купить ноутбук за 20 000 рублей с такой же производительностью. Каисса не до 80-х годов доминировала, а только в 1974 году случайно выиграла швейцарку в 5 туров из 10 участников. Про соотношение глубины перебора и силы игры - астрологические предсказания начала 80-х. Уж куча прог перебирала на 14 полуходов, но 2800 не пахло. В оценке дело. С другой стороны Гениус 3 с уровнем перебора 0 полуходов уверенно меня перекатывает, да и многих кмс тоже.
    Там форсированные варианты только считаются.
    Вклад Ботвинника в компьютерные шахматы давно выяснен что на уровне Сталина, дававшего ценные директивы типо советские самолеты должны летать выше, быстрее. И ведь летали выше на самом деле, но ни у кого не прочитаешь о Сталине, как о внесшем вклад в развитие мировой авиации. Все это обсуждалось и на этой гостевой. Никакого отношения к программированию он не имел, а писал пространные теоретические статьи, не нашедшие практического применения. И его Пионер коллектив его программистов научил лишь подгонять цепочки ходов под известный результат. И то не совсем удачно. Как агитатора за компьютерные шахматы вклад Ботвинника ценен.
  22. Ворчун Учаcтник

    • Участник
    Рег.:
    15.04.2007
    Сообщения:
    1.154
    Симпатии:
    3
    Репутация:
    0
    Оффлайн
    На русском языке принято говорить о Марии-Терезии, автрийской императрице.
  23. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    ——Если заложить абсолютно все позиции в базу данных компьютера, то игра шахматной программы станет идеальной из любой позиции и всегда будет приводить к лучшему исходу—— Очень спорное философское утверждение. По опыту шашечных прог, где просчитаны некоторые дебюты ( а не все шашки, как некоторые считают ) , речь идет о том, что прога не проиграет, а насколько это лучший ход - вопрос вкуса. Шахматные эндшпильные базы это подтверждают. В проигранных позициях часто советуют безвольно слить, отсрочив поражение шахами и бессмысленными ходами, в ничейных никаких попыток на выигрыш.
    Про Марию ваще жесть :)
  24. TopicStarter Overlay

    GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
    в 32-фигурном просчитанном эндшпиле вряд ли будет такое:
    потому что прога не получит такую позу
  25. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    Но и к выигрышу стремиться особо не будет - ведь все ходы из начальной позиции приводят к ничьей.
  26. TopicStarter Overlay

    GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
    тоже верно... из начальной позиции не будет
    но там ведь и нет выигрыша, нет вариантов таких...
    поэтому в начале она будет играть по дебютной библиотеке, а потом, глядишь человек и ошибется :)
  27. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    Дебютную библиотеку люди составляют. И если дебютная табия ничейна, то опять же к выигрышу стремиться не будет. Люди с компом вроде стараются не лезть в позиции типа дракона с разносторонними рокировками или английской атаки. В общем игра по 32 фигурной базе явно не идеальная.
  28. R Ov Учаcтник

    • Участник
    Рег.:
    27.02.2007
    Сообщения:
    1.299
    Симпатии:
    7
    Репутация:
    0
    Адрес:
    Нижний Тагил
    Оффлайн
    Извините, Сергей!
    Но русские шашки были просчитаны задолго до появления прог (из опыта общения с гроссмейстерами по шашкам). Это было их великой тайной.
  29. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    Проги по шашкам были созданы задолго до Вашего рождения, Ув. R Ov. И кстати когда шахматные играли на уровне 4 разряда, то шашечные уж как то на 1 разряд катали. Там же проще все. Еще кстати и у некоторых современных шашечных прог отсутствует позиционная оценка - быстрее считают зато. Поддал, еще поддал, побил четыре. Брать обязательно...
    В буллит эта стратегия многими шахматистами с успехом взята на вооружение.
  30. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Без позиционной оценки будут сливать без борьбы.
  31. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    Другим прогам да, а человека, сильного любителя надерут. Кстати NS первую версию своей шахматной проги, Анечки, без позиционной оценки сделал. А уж шашки то...
  32. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    122
    Репутация:
    1
    Оффлайн
    А какие принципы позиционной оценки в шашках? Я без малейшего представления. Когда то давно, лет 25 назад я общался с шашечным мастером, сейчас он уже гросс, и спросил его каковы основные принципы игры в шашки. Всё что он ответил -это играть активно. А как активно, что это значит? Вот в шахматах есть четкие рекомендации. Развитие, захват открытых вертикалей, рокировка, проходная и т.д. А в шашках за что зацепиться можно?
  33. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Вряд ли.
    Хотя бы за расположение шашек.
  34. Сергей С. Питер Учаcтник

    • Участник
    Рег.:
    31.03.2006
    Сообщения:
    1.193
    Симпатии:
    59
    Репутация:
    11
    Оффлайн
    Ну в шахматах та же Анечка без позиционной оценки слабого кмс надерет. В шашках тем более проще.
  35. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    384
    Симпатии:
    361
    Репутация:
    10
    Оффлайн
    Это говорит о слабости кмс.
    Я попробовал отключить в Рыбке 3 главную составляющую позиционной оценки - PST. Результат : минус 200 пунктов.

Поделиться этой страницей