Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 56
Компьютер уже давно обыграл человека в шахматы, сейчас сильнейшие шахматисты не способны выиграть даже у старенького ноутбука.
По-подробнее можно? Кто играл, когда, какая программа и кто выиграл?
По-подробнее можно? Кто играл, когда, какая программа и кто выиграл?
Подробности — на википедии. В частности Крамник — Deep Fritz и участие Pocket Fritz в турнирах. Конкретно с ноутбуком никто вроде не играл, так что это можете считать моей оценкой.
Достаточно ли вы компетентны в данной области, чтобы давать такую оценку?
Да. Чемпион мира признавался, что затрудняется в игре с мобильным приложением.
Для тех, кто в теме, это очевидно. Возможно оценка дана несколько расплывчатая, но идея верна. Ни один факт не указывает на противоположное.
Для тех, кто в теме, это очевидно. Возможно оценка дана несколько расплывчатая, но идея верна. Ни один факт не указывает на противоположное.
а что слышно про идею когда в соревнования принимают участие пары человек (сам опытный шахматист) и компьютер. будет ли человек тут только придатком к компьютеру? есть ли такие соревнования?
Есть.Называется advanced chess или просто адванс по русски. Федерация шахмат по переписке (ICCF) разрешает использование компьютерного анализа в играх.
Влияют ли адвансеры на анализ? Они считают что да. Я склонен им верить, человек пока еще может направлять компьютер и подсказывать ему идеи, но с каждым годом это все сложнее и сложнее. Несколько лет назад сильные адвансеры на домашнем компьютере обыгрывали кластер на котором был запущен движок.
С контролем же меньше часа-двух на ход, человек вряд ли что-то может улучшить.
Влияют ли адвансеры на анализ? Они считают что да. Я склонен им верить, человек пока еще может направлять компьютер и подсказывать ему идеи, но с каждым годом это все сложнее и сложнее. Несколько лет назад сильные адвансеры на домашнем компьютере обыгрывали кластер на котором был запущен движок.
С контролем же меньше часа-двух на ход, человек вряд ли что-то может улучшить.
Такие дисциплины уже достаточно давно существуют и даже успели потерять популярность — соревнования в таком формате с участием топовых гроссмейстеров проводятся крайне редко.
Вероятно «продвинутые» шахматы имели смысл, когда человеческое «интуитивное» понимание позиции могло помочь оценке компьютера (в 2005-ом fritz по загадочным обстоятельствам просто просчитался в партии с Пономаревым). Сейчас скореее всего человек уже просто придаток и грубых просчетов программы уже не допускают.
Вероятно «продвинутые» шахматы имели смысл, когда человеческое «интуитивное» понимание позиции могло помочь оценке компьютера (в 2005-ом fritz по загадочным обстоятельствам просто просчитался в партии с Пономаревым). Сейчас скореее всего человек уже просто придаток и грубых просчетов программы уже не допускают.
Например ИИ не умет спец. поддаваться что бы в некоторых местах(ходах) что бы выигрывать. Так скажем блефавать. Это минус в сов. играх. ИИ думает или сделать что бы просто побеждать.
Можете привести пример из шахмат? Или даже любой другой игры.
Читал книгу где человек играет с ИИ шахмат по сети и ему кажется что тут что то не так. Так как ИИ не может спец. поддаваться. В конце он выяснил что играл с человеком. (No Game No Life)
Кажется я понимаю, о чем вы. Компьютер всегда ожидает сильнейший с его точки зрения ход. Он не ставит некорректные ловушки, в расчете на то, что противник не заметит комбинацию или атаку. Люди делают это постоянно.
Взамен, у движков есть параметр "презрение" — число, которое добавляется к оценке (или вычитается из нее), чтобы он оценивал позицию в свою пользу. В целом, это несколько ослабляет игру движка, но помогает ему играть на победу с более слабым соперником.
Взамен, у движков есть параметр "презрение" — число, которое добавляется к оценке (или вычитается из нее), чтобы он оценивал позицию в свою пользу. В целом, это несколько ослабляет игру движка, но помогает ему играть на победу с более слабым соперником.
Спасибо что правильно донесли то что я хотел сказать.
не думаю, что возникают проблемы «ловушек» у компьютеров, т.к. это лишь типичная проблема выбора между «локальным» и «глобальным» оптимумом, а т.к. до глобального оптимума все равно не добраться (пока не включились «эндшпильные таблицы»), то горизонт поиска оптимумов у компьютера гораздо шире и скорей это будет «ловушка» для человека.
Человек вообще по-другому играет, тренируя «ощущения», какая позиция хорошая, а какая плохая (как описанный тут пример Giraffe) + таблицы дебютов и рассчеты в эндшпилях. Правда, чем больше контроль времени тем больше рассчетов и меньше интуиции.
Человек вообще по-другому играет, тренируя «ощущения», какая позиция хорошая, а какая плохая (как описанный тут пример Giraffe) + таблицы дебютов и рассчеты в эндшпилях. Правда, чем больше контроль времени тем больше рассчетов и меньше интуиции.
Под ловушкой подразумеваю ход, гораздо худший если найти опровержение, который человек делает, ожидая, что соперник опровержение не заметит или, чаще, сам его не замечая.
Например, я подставляю слона так, что сделав очевидный ход, соперник проиграет ферзя. Но сделав правильный ход, он выиграет пешку. Компьютер так не сыграет, а человек — может
Например, я подставляю слона так, что сделав очевидный ход, соперник проиграет ферзя. Но сделав правильный ход, он выиграет пешку. Компьютер так не сыграет, а человек — может
С точки зрения алгоритма это всё равно одно из ветвей ветвления. Даже если тупо добавить некоторую константу , "корректирующую" решение в сторону рандомного, это тоже имеет вес.
Вероятно, использование такого подхода на данном этапе развития алгоритмов очень сильно увеличивает вычислительную сложность, поэтому отказываются от такого подхода.
Вангую в следующей итерации алгоритмов буду подавать на вход "профиль" соперника для корректировки весов решений
Вероятно, этого он действительно не умеет. Но кто сказал, что это слабость?
тяжело «на глазок» оценить фору в 1-2 пешки — я бы сказал, что это «200-400» пунктов ЭЛО. Это значит что в «человеческом рейтинге» программы за 3000 уже выбрались.
Я сначала привел почти такую же цифру, но потом убрал, ибо оценки одной пешки сильно колеблются у разных исследователей. Тем более она зависит и от силы игроков — новичкам зевающим фигуры лишняя пешка мало чем поможет, для гроссмейстеров это серьезное подспорье.
Но да, программы явно выбрались за 3000
Но да, программы явно выбрались за 3000
да, спасибо, очень правильное замечание, что перевод фиксированной форы в очки рейтинга ЭЛО будет сильно зависеть от силы игрока и от времени на игру. Видимо мы уже не узнаем (точно) насколько они сильны. Чтобы измерять силу программ нужно много игр с людьми, причем программ разных уровней (включая сопоставимых по уровню) и игр программ разных уровней самими с собой.
Не сочтите за придирку, но всё-таки «рейтинг Эло», а не «рейтинг ЭЛО» (эта ошибка в статье тоже наличествует). Арпад Эло — это дяденька такой был.
Мне кажется, эта статью стоит и в хабр скопировать, она вполне там будет к месту. ИМХО.
Кстати было б очень интересно почитать также и про шашки, если у когонибудь есть похожый материал, буду рад почитать.
По словам знакомого мастера спорта шашки намного тяжелее поддаються компьютерному анализу, хотя вродиб клеток меньше возможностей хода тоже меньше. В подтверждение он говорит что компьютер однозначно победил человека в шашки на 2 года позже чем в шахматы (хотя может и проблема в том что шашки не так популярны как шахматы в целом мире). Было б тоже интерестно подтвердить или опровергнуть ситуацию с компьютерным анализом шашек VS шахмат.
Также у человека досих пор есть возможность выиграть в шашки у компьютера, при условии что компьютер не использует ендшпильные таблицы и время на партию 1минута.
По словам знакомого мастера спорта шашки намного тяжелее поддаються компьютерному анализу, хотя вродиб клеток меньше возможностей хода тоже меньше. В подтверждение он говорит что компьютер однозначно победил человека в шашки на 2 года позже чем в шахматы (хотя может и проблема в том что шашки не так популярны как шахматы в целом мире). Было б тоже интерестно подтвердить или опровергнуть ситуацию с компьютерным анализом шашек VS шахмат.
Также у человека досих пор есть возможность выиграть в шашки у компьютера, при условии что компьютер не использует ендшпильные таблицы и время на партию 1минута.
У шашек в отличие от шахмат найдено слабое решение, после чего мне кажется интерес к ним практически полностью испарился.
В целом же алгоритмы похожи: та же альфа-бета. Поиск спокойствия (и придумал же я переводить термины на русский) очень важен, очевидно почему. Конечно продления-отсечения и статическая оценка позиции абсолютно другие, но это уже вопрос по шашкам а не поп программированию, а в них я мало что смыслю.
В целом же алгоритмы похожи: та же альфа-бета. Поиск спокойствия (и придумал же я переводить термины на русский) очень важен, очевидно почему. Конечно продления-отсечения и статическая оценка позиции абсолютно другие, но это уже вопрос по шашкам а не поп программированию, а в них я мало что смыслю.
Если мне не изменяет память, выигрышные алгоритмы для шашек существовали ещё в 80-е и были реализованы на «домашних» компьютерах типа Commodore или ZX Spectrum в виде коммерческих игр.
Программирование шашек почти всегда шло примерно в фарватере развития шахматного программирования (исключая только самые ранние годы в англо/американских шашках). К шахматам было приковано внимание ведущих программистов, в разработку программ нередко вливались значительные денежные средства. В свою очередь, шашечные программы были редки, интерес программистов небольшой. Такой порядок вещей, в принципе, сохранился и до наших дней. В международных шашках (10х10) активны в основном голландские программисты, в русских шашках — российские и белорусские. В начале-середине "нулевых", и в тех, и в других шашках ведущие программы достигли уровня лучших шашистов-людей, после чего по сути уперлись в ничейный барьер. Количество ничьих зашкаливает за 90%.
Если в международных шашках ещё есть некоторый прогресс (об этом ниже), то в русских шашках из года в год на звание лучших претендует один и тот же десяток программ, из которых признаки жизни подают только 3-4. Остальные как-то подзаброшены своими программистами. По-видимому, это следствие низкого общественного интереса и высокой ничейности игры.
Что касается алгоритмов, то они не особо отличаются от шахматных. Сами шашечные программы как правило меньше шахматных и попроще. Чтобы не быть голословным, приведу мнение Сергея Нефедова, автора одной из лучших шашечных программ "Скифи":
Кстати, Сергей хоть и не слишком хорошо играет в шашки, но тем не менее создал свою программу всего за несколько месяцев, используя стандартные алгоритмы. Если кому интересно — исходный код Скифи открыт. Его можно найти в архиве программы Каллисто 4.
Теперь про международные шашки.
Здесь ситуация немного получше. Программы медленно, но всё же прогрессируют. Сейчас они набирают примерно 65% очков против программ начала "нулевых". Что довольно много, учитывая большую ничейность игры. В настоящее время лучшая программа — Scan 2.0, авторства небезызвестного Фабьена Летузи. Писать он её начал совсем недавно — где-то в начале прошлого года. Не особо напрягался, использовал известные методики, но как ни странно программа сразу же заиграла сильно, и намного опередила все другие известные программы. Как и Скифи, Scan 2.0 тоже open source, т.е. движок с открытым исходным кодом. Скачать код можно здесь. Краткое описание алгоритмов здесь. Пожалуй стоит особо отметить, что для оценки позиции Scan использует также и набор локальных паттернов заимствованных из игры Отелло.
результаты матчей с сильнейшими шашистами
Международные шашки:
2001 Buggy vs. N'Diaga Samb, GMI +0 –2 =11
2002 Flits vs. Johan Krajenbrink, GMI +3 –0 = 7
2003 Buggy vs. N'Diaga Samb, GMI +3 –0 = 3
2003 Flits vs. Guntis Valneris, GMI +0 –0 = 7
Русские шашки:
2003 Кандауров — Магистр +1 -0 =9
2003 Кандауров — Тундра +1 -0 =9
2007 Королев — Каллисто +1, -2, =9 (игра с нестандартных позиций)
2001 Buggy vs. N'Diaga Samb, GMI +0 –2 =11
2002 Flits vs. Johan Krajenbrink, GMI +3 –0 = 7
2003 Buggy vs. N'Diaga Samb, GMI +3 –0 = 3
2003 Flits vs. Guntis Valneris, GMI +0 –0 = 7
Русские шашки:
2003 Кандауров — Магистр +1 -0 =9
2003 Кандауров — Тундра +1 -0 =9
2007 Королев — Каллисто +1, -2, =9 (игра с нестандартных позиций)
Если в международных шашках ещё есть некоторый прогресс (об этом ниже), то в русских шашках из года в год на звание лучших претендует один и тот же десяток программ, из которых признаки жизни подают только 3-4. Остальные как-то подзаброшены своими программистами. По-видимому, это следствие низкого общественного интереса и высокой ничейности игры.
Что касается алгоритмов, то они не особо отличаются от шахматных. Сами шашечные программы как правило меньше шахматных и попроще. Чтобы не быть голословным, приведу мнение Сергея Нефедова, автора одной из лучших шашечных программ "Скифи":
NS » 22.02.2009, 18:03
Чтоб прилично играл шашечный движок нужно совсем немного
Перебор — Альфа-бета либо PVS, рассмотрение всех взятий за горизонтом.
Для сортировки — Хеш, киллеры, история, взятия сортировать по взятому материалу.
В переборных алгоритмах LMR, MultiCut, отсечения на малой глубине (Футилити/ProbCut/Рыбья схема)
В оценке достаточно PST. Накрутки (мобильность, центр, баланс флангов и т.д.) что-то прибавляют, но для силы Каллисто3 они совершенно необязательны.
Кстати, Сергей хоть и не слишком хорошо играет в шашки, но тем не менее создал свою программу всего за несколько месяцев, используя стандартные алгоритмы. Если кому интересно — исходный код Скифи открыт. Его можно найти в архиве программы Каллисто 4.
Теперь про международные шашки.
Здесь ситуация немного получше. Программы медленно, но всё же прогрессируют. Сейчас они набирают примерно 65% очков против программ начала "нулевых". Что довольно много, учитывая большую ничейность игры. В настоящее время лучшая программа — Scan 2.0, авторства небезызвестного Фабьена Летузи. Писать он её начал совсем недавно — где-то в начале прошлого года. Не особо напрягался, использовал известные методики, но как ни странно программа сразу же заиграла сильно, и намного опередила все другие известные программы. Как и Скифи, Scan 2.0 тоже open source, т.е. движок с открытым исходным кодом. Скачать код можно здесь. Краткое описание алгоритмов здесь. Пожалуй стоит особо отметить, что для оценки позиции Scan использует также и набор локальных паттернов заимствованных из игры Отелло.
Если в международных шашках ещё есть некоторый прогресс (об этом ниже), то в русских шашках из года в год на звание лучших претендует один и тот же десяток программ, из которых признаки жизни подают только 3-4. Остальные как-то подзаброшены своими программистами.
В обоих т.н. чемпионатах мира среди шашечных программ в ТОП-3 была одни и те же программы. Из которых как минимум одна (собственно, чемпион, Торнадо 3), похоже заброшена окончательно.
По-видимому, это следствие низкого общественного интереса и высокой ничейности игры.
Мне кажется, что больше на них просто не заработать. А улучшать всё сложнее и сложнее. Трудно найти в таком случае мотивацию.
Шашки вроде бы решены: была статья "checkers solved."
Спасибо за статью.
В FIDO рассылку о программировании шахмат, вел Сергей Марков, разрабатывающий фpиваpный отечественный шахматный движок SmarThink. Прилагаю часть одного письма:
─ FIDO EchoMail (2:5064/10.6) ──────── SU.CHESS ─
Сооб: 115 из 116
От: Sergei Markoff 2:5027/16.13 04 Окт 01 20:01:41
Кому: All 19 Окт 01 02:37:30
Тема: Русскоязычные сайты по компьютеpным шахматам:
— Доминиpующим подвидом альфа-бета поиска (или метода Бpудно — по имени
советского математика, котоpый откpыл этот метод) является т.н. NegaScout.
Считается, что NegaScout и SSS* пpимеpно pавны по эффективности. В pазных
случаях выигpывает pазный алгоpитм. Однако SSS* весьма сложен в pеализации, это
pаз, а во-втоpых большинство эвpистик, используемых в пеpебоpной схеме (SEE,
history heuristic, killer moves и т.д.) «заточены» под альфа-бету и ее
pазновидности.
MTD(f) это, насколько я помню, попытка пpименять на пpактике теоpию т.н.
«conspiracy numbers» (pазделение min и max стpатегий в пеpебоpе). Тезисы
докладов есть на http://www.cs.ualberta.ca.
Для всех интеpесующихся шахматным пpогpаммиpованием pекомендую наш pесуpс:
*http://www.aigroup.narod.ru*
Там же совpеменный фpиваpный отечественный шахматный движок SmarThink (ELO
поpядка 2400).
В FIDO рассылку о программировании шахмат, вел Сергей Марков, разрабатывающий фpиваpный отечественный шахматный движок SmarThink. Прилагаю часть одного письма:
─ FIDO EchoMail (2:5064/10.6) ──────── SU.CHESS ─
Сооб: 115 из 116
От: Sergei Markoff 2:5027/16.13 04 Окт 01 20:01:41
Кому: All 19 Окт 01 02:37:30
Тема: Русскоязычные сайты по компьютеpным шахматам:
— Доминиpующим подвидом альфа-бета поиска (или метода Бpудно — по имени
советского математика, котоpый откpыл этот метод) является т.н. NegaScout.
Считается, что NegaScout и SSS* пpимеpно pавны по эффективности. В pазных
случаях выигpывает pазный алгоpитм. Однако SSS* весьма сложен в pеализации, это
pаз, а во-втоpых большинство эвpистик, используемых в пеpебоpной схеме (SEE,
history heuristic, killer moves и т.д.) «заточены» под альфа-бету и ее
pазновидности.
MTD(f) это, насколько я помню, попытка пpименять на пpактике теоpию т.н.
«conspiracy numbers» (pазделение min и max стpатегий в пеpебоpе). Тезисы
докладов есть на http://www.cs.ualberta.ca.
Для всех интеpесующихся шахматным пpогpаммиpованием pекомендую наш pесуpс:
*http://www.aigroup.narod.ru*
Там же совpеменный фpиваpный отечественный шахматный движок SmarThink (ELO
поpядка 2400).
В отличии от движков, где свободный Stockfish уверенно борется за первую строчку рейтинга с платным Komodo.И это при том, что разработчики закрытых движков часто воруют код из опенсорса.
Это не доказано.
Более того, архитектура этих движков должна настолько отличаться, а код быть настолько запутанным, что воровать код было бы просто нелогично. Все равно что винде воровать код у линукса.
Можно воровать идеи, но опять таки, на таком уровне многие улучшения для одного движка будут ухудшениями для другого.
Более того, архитектура этих движков должна настолько отличаться, а код быть настолько запутанным, что воровать код было бы просто нелогично. Все равно что винде воровать код у линукса.
Можно воровать идеи, но опять таки, на таком уровне многие улучшения для одного движка будут ухудшениями для другого.
Хм, и что, платные шахматные GUI — это денежный рынок?
Заняться что ли… :)
Заняться что ли… :)
Ну стоит тот же Chessbase прилично… И им пользуется большое количество шахматистов.
И все они спортсмены или обычные любители тоже готовы тратить 300 евро на такой софт?
Вместе с тем, слабый гроссмейстер достаточно уверенно выиграл с форой в 2 пешки.
По ссылке ничья с вечным шахом…
По ссылке ничья с вечным шахом…
По ссылке — матч из 6 партий с результатом +3=2-1 в пользу человека.
Да, действительно. Сперва пустой чекбокс даже не заметил...
Шестая партия сыграна уже с меньшей форой, вероятно, из-за того, что победа в матче уже достигнута, а вот регламент партий у Накамуры мне не очень понятен, слишком разные стартовые условия…
Но в любом случае это хороший результат — если спросить заранее я бы сказал, что одна пешка — недостаточная фора человеку, чтобы играть на равных...
Шестая партия сыграна уже с меньшей форой, вероятно, из-за того, что победа в матче уже достигнута, а вот регламент партий у Накамуры мне не очень понятен, слишком разные стартовые условия…
Но в любом случае это хороший результат — если спросить заранее я бы сказал, что одна пешка — недостаточная фора человеку, чтобы играть на равных...
Кстати, я задумывался над тем, что текущее представление хранения позиции — не оптимально. Проблем две:
Размышляя над возможными исправлениями недостатков я уверен, что можно сделать алгоритм хранения с переменным размером бит на позицию. От 60 до 120 бит, в зависимости от того, как много фигур осталось на доске и на сколько хорошо подобраны узловые позиции.
Получив такое компактное хранение можно их пронумеровать и результат оценки для 9 фигур по принципу, схожему с Syzygy. Игра в эндшпиле для компьютера будет сводиться к довольно сложному получению порядкового номера всех полу-ходовых позиции и проверка их в базе на результат.
Понятно, что такое представление будет иметь недостатки, в виде того, что позиция представлено номером и при ее оценке не была известна информация о предыдущем ходе (взятие на проходе) а также возможности рокировки (но это и сейчас в эндшпильных таблицах отсутствует).
Зато можно хранить таблицу для 9 а то и 10 фигур на одном обычном компьютере! Отдельный вопрос: как быстро будет посчитана такая таблица, но это уже отдельная история.
- Дело в том, что большинство позиций, который можно выставить на доске полным перебором — не валидны с точки зрения правил игры. Или крайне низковероятны. Например: три чернопольных слона с любой из сторон.
- Между соседними ходами очень небольшое изменение. Т.е. если озадачится именно проблемой ХРАНЕНИЯ позиций то можно сделать так, что совокупность позиций опирается на базовую, храня только дельту изменения к ней.
Размышляя над возможными исправлениями недостатков я уверен, что можно сделать алгоритм хранения с переменным размером бит на позицию. От 60 до 120 бит, в зависимости от того, как много фигур осталось на доске и на сколько хорошо подобраны узловые позиции.
Получив такое компактное хранение можно их пронумеровать и результат оценки для 9 фигур по принципу, схожему с Syzygy. Игра в эндшпиле для компьютера будет сводиться к довольно сложному получению порядкового номера всех полу-ходовых позиции и проверка их в базе на результат.
Понятно, что такое представление будет иметь недостатки, в виде того, что позиция представлено номером и при ее оценке не была известна информация о предыдущем ходе (взятие на проходе) а также возможности рокировки (но это и сейчас в эндшпильных таблицах отсутствует).
Зато можно хранить таблицу для 9 а то и 10 фигур на одном обычном компьютере! Отдельный вопрос: как быстро будет посчитана такая таблица, но это уже отдельная история.
Получив такое компактное хранение можно их пронумеровать и результат оценки для 9 фигур по принципу, схожему с Syzygy. Игра в эндшпиле для компьютера будет сводиться к довольно сложному получению порядкового номера всех полу-ходовых позиции и проверка их в базе на результат.
Syzygy хранит позиции очень, очень компактно.
Безпешечные 9фигурки одного типа (например король, ладья и 3 легких фигуры против короля, двух ладей и легкой фигуры) состоят из 10 (симметрия)6362616059585756=1,56*10^15. Прикиньте, сколько места займет весь набор (5720 типов).
Итерационный п… што? Я всегда это называл поиском в ширину, где глубиной является кол-во шагов.
А вообще хороший вышел чек-лист для любого ИИ. Почерпнул для себя «Quiescence Search», «Историческое отсечение», «Razoring» и «Эндшпильные таблицы». Большая часть вкусностей, к сожалению, не годится для игр несопернических, и где хочется найти решение лучшее, кратчайшее и т.п.
А вообще хороший вышел чек-лист для любого ИИ. Почерпнул для себя «Quiescence Search», «Историческое отсечение», «Razoring» и «Эндшпильные таблицы». Большая часть вкусностей, к сожалению, не годится для игр несопернических, и где хочется найти решение лучшее, кратчайшее и т.п.
Отсечения значительно ослабляют игру при фиксированной глубине и значительно усиляют её при фиксированном времени: тест Komodo с включёнными и отключёнными отсечениями. Именно поэтому правильная сортировка ходов и хорошие отсечения гораздо важнее всего остального.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как компьютер играет в шахматы?