Как компьютеры играют в шахматы

[@poluekt]

Интересно, сколько читателей всё-таки осилили статью полностью )

[@bar_boss]

Все, кто читает твой комментарий

[@ZiZZoKo]

Не факт. Кому-то комментарии покажутся более «интересными». :)

[@bar_boss]

А зачем читать комментарии, если статья не интересная?

[@LevaniD]

статья отличная

не стал вчитываться только в код, за остальное спасибо

[@BnetAngel]

Ну я почти осилил=)

[@qmax]

это всё же интереснее, чем рассуждения о старданиях тетрадок в клетку.

[@oogl]

Поддерживаю: так длинно писать про элементарную альфа-бету — перебор.

[@megaserg]

Статья и есть про перебор ;-)

[@gorbarov]

Я осилил, но скажу честно, до конца не осознал ;)

[@dozen]

«Искусственный интеллект: стратегии и методы решения сложных проблем»
Джордж Ф. Люгер

Рекомендую для более глубокого ознакомления.
Видел ее в books.google.com.

[@ExxY]

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

[@n1tra]

Практически невозможно, а не в принципе :)
А шашки таки-да, перебрали…

[@alexxxst]

> Мои студенты после 2 курса втроем за три недели сваяли вот эти шахматы.

Глюк там в программке, компьютер почему-то стал ходить конем по прямой, да еще и моим конем :)

[@salmin]

компьютерный игрок задействовал чит-код :)

[@Zoberg]

Ну зачем же так жестоко?:( Теперь студентам оценки понизят:(

[@zak2k]

хорошая идея привлекать хабровитчан бетта тестарами
PS особо выгодно для преподавателей ))

[@dmgorsky]

Всё правда, всё про нас.
Минимакс в универе преподают.
Ждём статью про оценочные функции =)

[@Stepler]

дерево ходов на самом деле выглядет не так, в нём есть приоритетные ветки, подветки, ветки с вопросом, с равенством,…

[@Ackrite]

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

[@tangro]

Блин, вот какими примерами нужно иллюстрировать метод ветвей и границ в курсе математических методов исследования операций! А то нам ну так нудно и надуманно про него рассказывали, что я уж решил, что это что-то ненужное.

[@ubique]

Принципа минимакса еще придерживались в романе Филиппа Дика «Солнечная Лотерея» =) Он кстати отлично там быр реализован.

[@tifeit]

Пройдёт ещё лет двадцать и на шахматных чемпионатах помимо допинг контроля, будет проверка организма на наличие микрочипов — помощников.

[@ykcyc]

самое интересное — это потом стравить между собой два разных алгоритма и посмотреть как они играть будут и кто кого :-)

[@ptiss]

у нас был чемпионат игровых алгоритмов (правда, не по шахматам, и не с использованием методов ТПР) по потоку кафедры, первые пять ботов давали авторам автомат.

[@IchBinFrei]

Камнем преткновения в написании шахматных движков является реализация функции оценки позиции, она и определяет характер игры движка в сложных несбалансированных позициях, можно даже УСЛОВНО разделить шахматные движки на позиционные (приоритетом является оценка позиции) и тактические (приоритетом является перебор большего числа ходов для получения позиций более простых для оценивания), например движок Rybka скорее позиционный, а
Fritz — тактический.

[@AMCDM]

Приду домой, сведу в баталию предоставленную программу и шахматы мелкмягких в висте!
О результатах отпишусь =)

[@maxshopen]

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

[@stepan_ovchinnikov]

да и я на самом деле обыгрываю. была где-то более сообразительная версия, да потерялась

[@ptiss]

а потом они посеяли исходники (ц) Бобук

[@IchBinFrei]

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

[@Ackrite]

Это все хорошо, но ведь до позиции, когда осталось 6 фигур, еще и довести надо… По 3 фигуры у каждого… Это, мягко говоря, сложно осуществить, если играешь с неглупым человеком. Имхо конечно…
Но возможно в будущем просчитают все варианты :) И тогда компьютеры захватят убьют людей :)

[@umnik]

Про полный перебор всех шахматных комбинаций частенько говорят «слишком сложно».
А если брать численно? Сколько, скажем, floating point operations понадобится.
Может быть есть смысл собрать сеть распределённых вычислений и просчитать ВСЕ ходы, сделав самого крутого шахматного соперника?

[@tangro]

Во-первых, такой мощности сеть собрать невозможно.
Во-вторых, даже если предположить, что соберете — смысл играть? Ясно, что зная наперед все хода, она победит.
В чем суть затеи?

[@umnik]

Суть затеи в том, что мне интересно это реализовать =)
Наверное, именно потому, что почти все считают это невозможным

[@stepan_ovchinnikov]

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

задача явно не та

геном человека или те же seti@home интересны людям куда более

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

[@linx56]

— Г-голубчики, — сказал Фёдор Симеонович озадаченно, разобравшись в почерках. — Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что она н-не имеет р-решения.
— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
— К-как-то ты странно рассуждаешь, К-кристо… К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то…
— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен. По-видимому, я напрасно начал с тобой беседовать на эту тему.

(с) АБС, Понедельник начинается в субботу.

[@qmax]

шикарно! :)
было б моей любимой цитатой — если б помнил :)

[@darkk]

Суть? Узнать — белые или чёрные выигрывают при правильной игре. :-)

[@KeepYourMind]

Почти похожая ситуация. (=

[@qmax]

для осознания масштабов стоит посмотреть на тему en.wikipedia.org/wiki/Computational_complexity_theory

[@doni]

Причем тут искусственный интеллект. Тут проста перебор всех вариантов.

[@stepan_ovchinnikov]

позвольте поспорить

задача искусственного интеллекта по одному из определений — такая задача, для которой неизвестно точного алгоритмического или аналитического решения. для шахмат из-за огромного числа вариантов такого алгоритмического решения нет

кроме того, в описанном «переборе вариантов» используются, и существенно, разнообразные эвристические, качественные, оценочные параметры и функции, что напрямую относится к инженерии знаний, т.е ИИ

[@qmax]

вот тут бы уместно было бы «завернуть» оценку задачи в категориях полиномиальностей.

[@stepan_ovchinnikov]

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

[@qmax]

ну я к тому, что этот момент не особо акцентирован в посте,
потому и возникают идеи «собрать большой большой кластер», и «причом тут интеллект»

[@DeeoniS]

Вот функции оценки тут самое интересное, а к альфа-бета-отсечениям и минимаксному методу можно и путем логических рассуждений прийти

[@yvanko]

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

[@stepan_ovchinnikov]

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

[@stepan_ovchinnikov]

не совсем так

шахматы фишера не обязательны, если вы, например, хотите участвовать в соревнованиях по классическим шахматам или блицу

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

[@Dark_MX]

Ну вот. Опять поламал :'(
[url]http://smages.com/i/4a/2e/4a2e32250669fc21c126734367e3bb45.jpg[/url]

[@Nakilon]

Огромное спасибо за статью! Сколько раз ломал голову и приходил к выводам Кнута и Мура, но не хватало собранности мыслей, чтобы написать это в программер по-человечески. Когда-то делал одной рекурсивной ф-цией, потом тремся, потом двумя… У вас, как я смотрб, довольно компактно все получилось. Как только найду свободное время, попробую использовать ваш код. Спасибо ещё раз.

[@uncleLem]

А как определяется f(p)?