Некоторые идеи написания искуственного интелекта для шахмат. Искусственный интеллект и базы знаний Учебный проект шахматы и искусственный интеллект
Главная » Пол » Некоторые идеи написания искуственного интелекта для шахмат. Искусственный интеллект и базы знаний Учебный проект шахматы и искусственный интеллект

Некоторые идеи написания искуственного интелекта для шахмат. Искусственный интеллект и базы знаний Учебный проект шахматы и искусственный интеллект

Фото из открытых источников

Новый искусственный интеллект всего за 4 часа обучения стал лучшим шахматистом на Земле! (сайт)

А помните, какой фурор наделал в 1996 году шахматный суперкомпьютер «Deep Blue», выиграв первую партию у российского чемпиона Гарри Каспарова? Несмотря на то, что наш соотечественник все же одержал победу в этой игре, уже тогда стало понятно, что искусственный интеллект стремительно прогрессирует и когда-нибудь обаятельно станет наилучшим шахматистом, после чего людям будет бесполезно играть с программой. Оставался лишь вопрос, когда это произойдет.

Представители известной корпорации «Google» заявили, что это время, наконец-то, настало. По словам специалистов, разработанная ими нейросеть «AlphaZero» всего за 4 часа самообучения превратилась в самого виртуозного и безупречного шахматного игрока за всю историю этой игры. Сверхмощный искусственный интеллект обучался игре в шахматы, зная только ее правила. Поиграв 4 часа с самим собой, робот научился идеально играть, без труда победив шахматную программу «Stockfish», считавшуюся до этого самой совершенной. Компьютеры провели 100 партий - «AlphaZero» удалось выиграть 28 из них и свести вничью оставшиеся 72. Передовая нейросеть, имитирующая работу человеческого мозга, способна рисковать и даже использовать своеобразное подобие интуиции.

Мечтать о победе над искусственным интеллектом уже не приходится

Более ранние модели «AlphaZero» обучались игре, следя за живыми шахматистами. Разработчики предполагали, что это поможет искусственному интеллекту лучше понять стратегии игры. На самом же деле оказалось, что наблюдение за людьми только замедляет развитие программы. Когда нейросеть предоставили самой себе, ее способности взлетели до небес. Теперь инженеры «Google» думают над тем, как применить подобные технологии для реальной пользы человечеству, поскольку шахматная игра, даже самая виртуозная, не имеет прикладной цели.

В 1968 году известный Дэйвид Леви заключил пари, что в течение ближайшего десятилетия его не обыграет ни одна программа. Все это время гроссмейстер постоянно состязался с различные шахматными компьютерами и всякий раз выигрывал у них. В 1978 году он одержал победу над сильнейшей в то время программой «Chess 4.7», выиграв пари. К несчастью, в наши дни столь интересных поединков уже не будет - нам предстоит теперь узнавать только о том, как одна фантастическая нейросеть победила другую. Живые шахматисты о победе над такими монстрами не могут уже даже мечтать. И это только начало подобных побед ИИ над человеком…

1997 год, Нью-Йорк. Чемпион мира по шахматам Гарри Каспаров проигрывает компьютеру «Deep Blue» фирмы IBM, и это сражение становится величайшей шахматной партией всех времен и народов. Об этой игре будут говорить как о «последней битве человеческого разума», многие будут сравнивать ее с первым полетом братьев Райт и высадкой астронавтов на Луну.

20 июля — в международный день шахмат — расскажем вам о том, что было дальше. А также о том, в чем искусственный интеллект уступает человеческому, и причем здесь Алан Тьюринг. Слово Гарри Каспарову, чемпиону мира по шахматам и автору книги .

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

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

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

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

Это подало мне идею. После того как мои матчи с Deep Blue привлекли столь пристальное внимание, я хотел продолжать шахматные эксперименты, несмотря на то, что IBM от них отказалась.

Мой план, попросту говоря, был таков: если вы не можете их победить, то присоединитесь к ним.

Я подумал: что если человек и машина будут не противниками, а партнерами? Замысел воплотился в году в испанском Леоне, где состоялся первый матч по продвинутым шахматам (advanced chess). Оба партнера имели под рукой персональный компьютер и могли использовать во время партии любую программу по своему выбору. Цель заключалась в том, чтобы выйти на новый, высочайший уровень игры — благодаря синтезу самых сильных сторон человеческого и машинного интеллекта. Хотя, как мы увидим далее, не все прошло так, как задумывалось, поразительные результаты этих «битв кентавров» убедили меня в том, что шахматы по-прежнему могут предложить очень многое в такой области, как взаимодействие человеческого разума и искусственного интеллекта.

К этому убеждению я пришел далеко не первым. Шахматные машины были святым Граалем задолго до того, как люди научились их создавать. И вот наука наконец получила доступ к этой чаше — а я оказался тем человеком, который держит ее в руках. Передо мной стоял выбор: отклонить вызов или принять его. Как я мог устоять? Это был шанс еще больше поднять популярность шахмат и расширить аудиторию, завоеванную ими после знаменитого матча между Бобби Фишером и Борисом Спасским во времена холодной войны и после моих поединков за мировую корону с Анатолием Карповым. Это позволило бы привлечь в мир шахмат армию щедрых спонсоров, особенно из числа высокотехнологичных компаний. Так, корпорация Intel в середине 1990-х годов спонсировала целую серию турниров по быстрым и классическим шахматам и полный цикл чемпионата мира, включая мой титульный матч с Вишванатаном Анандом, проходивший на верхнем этаже Всемирного торгового центра. К тому же мной управляло непреодолимое любопытство. Неужели машины действительно могут научиться играть в шахматы так же хорошо, как чемпион мира? Неужели они и вправду способны мыслить?

Интересно, что
первая шахматная программа появилась раньше, чем первый компьютер.

Ее разработал гениальный британский математик Алан Тьюринг, взломавший код нацистской шифровальной машины «Энигма». В 1952 году он написал на бумаге алгоритм, с помощью которого машина могла бы играть в шахматы, — только в роли центрального процессора выступал сам математик. «Бумажная машина Тьюринга» оказалась вполне компетентным игроком. Причина ее конструирования выходила за рамки личного интереса Тьюринга к шахматам. Умение играть в шахматы издавна считалось частью человеческого интеллекта, и создание устройства, способного победить человека в этой игре, должно было знаменовать появление действительно умной машины.

Имя Алана Тьюринга также навсегда связано с названием предложенного им мысленного эксперимента, позднее проведенного в реальности и получившего название «тест Тьюринга». Суть его в том, чтобы определить, сможет ли компьютер обмануть человека таким образом, чтобы тот думал, что имеет дело с человеком, и если сможет — тест считается пройденным. Еще до моего первого матча с Deep Blue компьютеры начали проходить то, что можно назвать «шахматным тестом Тьюринга». Они по-прежнему играли довольно плохо и часто делали явно нечеловеческие ходы, но иногда им уже удавалось разыгрывать партии, которые выглядели бы вполне уместно и в приличном человеческом турнире. С каждым годом машины становились все сильнее и сильнее, но в процессе их эволюции мы узнавали больше о самих шахматах, чем об искусственном интеллекте (ИИ).

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

По сути, «ум» Deep Blue ничем не отличался от «ума» программируемого будильника.

Мысль об этом только усугубляла для меня горечь поражения — проиграть программируемому будильнику, пусть даже стоимостью $10 млн?!

Так называемое ИИ-сообщество, безусловно, радовалось результату и привлеченному вниманию, но в то же время ученые были явно обескуражены тем фактом, что Deep Blue ничуть не напоминает искусственный интеллект, о котором мечтали их предшественники. Вместо того чтобы играть в шахматы как человек — демонстрируя человеческую интуицию и нестандартное творческое мышление, он играет в шахматы как машина: оценивает до 200 млн возможных ходов в секунду и побеждает благодаря грубой вычислительной силе. Разумеется, это нисколько не умаляет самого достижения. В конце концов, Deep Blue — творение человеческого разума, и проигрыш человека созданной им машине одновременно означает его победу.

После невероятного напряжения того матча, которое усугублялось подозрительным поведением IBM и моей склонностью к сомнениям, я не был готов легко признать свое поражение. Честно говоря, я никогда не умел проигрывать. Полагаю, что человек, который легко смиряется с поражением, никогда не станет настоящим чемпионом, и этот принцип, конечно, справедлив и в моем случае. Но я верю в честную борьбу. Тогда же я считал, что IBM обманула меня — а также весь мир, пристально следивший за нашим матчем.

Должен признать, что повторный анализ каждого аспекта того бесславного поединка с Deep Blue оказался нелегким делом.

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

Публикаций, посвященных Deep Blue, великое множество, но данная книга — первая и единственная, где собраны все факты и вся история рассказывается так, как ее вижу я. Несмотря на болезненность воспоминаний, это был поучительный и благотворный опыт. Мой великий учитель Михаил Ботвинник, шестой чемпион мира по шахматам, учил меня искать истину в каждой позиции. И я попытался выполнить его завет и поискать истину в самой сути Deep Blue.

Иллюстрация: Shutterstock

Предмет, возраст учащихся

Информатика и ИКТ,10-11класс

Краткая аннотация проекта

Проект разработан в рамках дисциплины "Информатика и ИКТ" для обучающихся 10-11 класса

Вопросы, направляющие проект

Основополагающий вопрос

Может ли компьютер заменить человека?

Проблемные вопросы

1. Может ли ЭВМ сама ставить задачи и решать их?

2. Способен ли компьютер воспроизвести все действия и мысли человека?

3. Способна ли ЭВМ управлять человеком?

Учебные вопросы

1. Какие задачи решает компьютер?

2. Самообучается ли ЭВМ?

3. Могут ли автоматы заменить человека?

4. Искусственный интеллект=Интеллект человека?

5. Нужно ли руководить работой ЭВМ?

6. Возможно ли поставить робота "во главу стола"?

7. Умеет ли думать компьютер?

8. Возможно ли заменить человеческий мозг искусственным?

9. Готов ли человек поручить всю работу роботам?

План проведения проекта

Представление проблемной ситуации:

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

Работа над проектом:

На начальном этапе работы над проектом учитель помогает каждой тематической группе распределить роли, обсудить стратегию исследования, способы поиска информации, методы исследования и возможности оформления результатов работы. Итогом является индивидуальный план деятельности. Далее начинается самостоятельная исследовательская, поисковая работа студентов в соответствии с планом. На этом этапе студенты собирают информацию по теме проблемного вопроса в энциклопедиях, учебниках и в Интернете, обсуждают собранную информацию в группе, разрабатывают инструментарий исследования, проводят исследования, сравнивают его результаты с собранной информацией, делают выводы, которые будут ответом на проблемный вопрос. Основное внимание учителю следует уделить промежуточным обсуждениям, дискуссиям внутри групп, консультациям учителей-предметников.Лист самооценки поможет участникам проекта осознать уровень личностного роста.

Оформление результатов проектной деятельности:

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

Защита проекта, оппонирование, дискуссия:

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

По окончании работы:

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

Визитная карточка проекта

Публикация учителя


Матч проигран: компьютер против человека.

Креативное мышление, логика, опыт – качества, которые позволяли человеку лидировать в схватке «человек-машина». Казалось, эти преимущества всегда будут секретным оружием человека, и компьютер будет выполнять роль «догоняющего».

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

Искусственный интеллект обыграл человека: где и как

Кубик Рубика
Эта головоломка известна по всему миру. Миллионы людей стараются выполнить задание и собрать правильно кубик, а некоторые даже соревнуются в скорости сборки. Рекорд среди людей показал 14-летний Лукас Эттер из США, который разбирается с головоломкой за 4,904 секунды. Невероятно, не правда ли? Но этот результат удалось превзойти роботу, который создали два энтузиаста Джей Флэтлэнд и Пол Роуз: результат робота 1,047 сек.


Благодаря встроенным камерам, а их четыре, компьютер оценивает положение, и подбирает лучший алгоритм действий. В основе системы лежит формула Коцебы (сборка за 20 ходов). Едва ли кто-то из людей сможет собрать кубик Рубика быстрее, чем за 1 секунду.
0:1 в пользу искусственного разума.

«Отелло»
Пик популярности этой игры приходится на начало 70-х годов прошлого века. Суть игры заключается в размещении на игровом поле (8×8 клеток) фишек: необходимо фишками своего цвета перекрыть с двух сторон ряды фишек соперника, тогда фишки меняют цвет и переходят к оппоненту. Победа достается тому, кто занял большую площадь.


В 1980 году чемпионом мира по «Отелло» был Хироси Иноуе, и он с легкостью победил программу Moor со счетом 5:1.
Позже программы научились просчитывать ходы соперника (примерно на 25 ходов), и когда в 1997 году действующий чемпион мира Такеси Мураками сошелся в матче-реванше с системой Logistello, счет был сокрушительным 0:6 в пользу ПО.

Нарды
Своему преимуществу в нардах над человеком искусственный интеллект обязан чемпиону мира по шахматам по переписке (и такие есть) Хансу Берлинеру, который написал программу BKG 9.8. И в 1979 году программа оказалась сильнее чемпиона мира по игре в нарды Луиджи Виллу.


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

Шахматы
Шахматные системы начали разрабатывать еще в середине ХХ века, разработки принадлежали компании IBM. Но из-за того, что программа требовала серьезных и длительных расчетов эту затею пришлось отложить на 30 лет. В 1996 году против Гарри Каспарова был выставлен «шахматный мозг» — компьютер Deep Blue.


Матч закончился в пользу человека: 3 победы, 2 ничьи, 1 проигрыш. Спустя год матч повторили, и в этот раз Deep Blue оказался более подготовленным. Еще бы, система оценивала 200 млн. позиций в секунду. И хотя Гарри хотел позже отыграться, в IBM отказались, считая это бессмысленным.

Чекерс (разновидность шашек)
Марион Тинсли был чемпионом чекерс на протяжении всей карьеры. И когда в 1992 году он встретился с системой, разработанной в Альбертском университете (Канада), победа осталась за ним. Из 39 партий — 4 победы, 2 проигрыша и 33 ничьи.


Спустя 2 года состоялся реванш, но Тинсли снялся с соревнования из-за проблем со здоровьем (на момент отказа было 6 ничейных партий), и победа досталась системе. С того момента, искусственный интеллект стал намного сильнее: в 2007 году канадцы объявили о создании идеальной системы, и уже никто из людей не пытается превзойти его в чекерс.

Скрэббл
Триумф компьютеру в этой игре дался легко и в первом же туре: чемпион мира Дэвид Бойс был обыгран в 2006 году робо-соперником Quackle.


Кстати, эта программа доступна в Сети, и вы можете с ней помериться силами, и может вы принесете победу команде «Человек».

Го
Эта игра появилась в Древнем Китае больше двух тысяч лет назад, но, несмотря на такой продолжительный опыт в игре, человек все равно уступил. На площадке (19×19) два игрока располагают свои камни (черные/белые), кто наберет больше очков (считаются фишки составленные в линию), тот и победил. С одной стороны все просто, но интерес кроется в многообразии возможных вариантов и ходов.


Интересно было и разработчикам AlphaGo (создавалась под эгидой Google) — создать систему, которая способна просчитать тысячи вариантов. Сначала искусственный интеллект опробовал свои силы с другими ПО, и когда из 500 партий 499 были за AlphaGo, он взялся за трехкратного чемпиона Европы Фань Хуэя. У чемпиона не было шансов: 5:0.

TV
Любите отвечать на вопросы в телевикторинах? Разработчики робота Watson от компании IBM тоже не смогли удержаться, и в 2011 году Watson выступил в качестве участника интеллектуальной телевикторины «Jeopardy!». Несмотря на то, что его оппонентами были рекордсмены шоу — Брэд Руттер и Кен Дженнингс – победа досталась , а выигранный миллион долларов передан на благотворительность.


И хотя компьютер уже показал свое интеллектуальное и логическое превосходство над человеком, он продолжает развиваться. Так компания Alibaba Group и Microsoft (разработки велись параллельно) представили искусственный интеллект, который оказался сильнее человека в понимании прочитанной информации.
Тест Стэнфордского университета это больше 100 тысяч вопросов, которые основываются на пяти сотнях статей из библиотеки Википедии.

Лучший показатель у человека 82,304 балла, итог Alibaba – 82,44, нейронная сеть Microsoft – 82,605. результаты свидетельствуют о том, что искусственный разум способен с высокой точностью отвечать на любые вопросы, а значит, технологии могут быть использованы для обслуживания клиентов, пациентов, посетителей музеев и т.п.

Компьютерные игры также были покорены программой. Программа победила программу: кто бы мог подумать, что это будущее так близко? Популярная игра Quake III, где игроки – гладиаторы, очень популярна в киберспорте. Но лучшими здесь оказались не люди, а команда ботов DeepMind, созданная подразделением Google. И хотя бой проводился в урезанном варианте, по подсчетам с 73 % вариантностью бот победил бы в любом состязании.


Опасно или нет такое превосходство искусственного разума? Никто не может ответить точно. Да и в конечном счете не этот ответ будет ключевым, ведь главным остается не тот факт, что человек уступает компьютеру, а сможем ли мы использовать этот потенциал на собственное благо. Как мы видим искусственный интеллект обыгрывает человека и не оставляет никаких шансов на победу.

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

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

Из названия следует, что в алгоритме проводится отсекание по каким-то двум параметрам - альфа и бета. Главная идея отсечения в том, что теперь мы будем держать интервал отсечений (нижняя и верхняя границы - альфа и бета соответственно - ваш К.О.) и оценки всех узлов, какие не попадают в интервал снизу мы рассматривать не будем (так как они не влияют на результат - это просто худшие ходы, чем уже найденный), а сам интервал будем сужать по мере нахождения лучших ходов. Хотя и альфа-бета отсечение намного лучше минимикса, все же время его работы тоже очень большое. Если принять, что в середине партии в одной стороны есть приблизительно 40 разных ходов, то время алгоритма можно оценить как O(40^P), где P - глубина дерева ходов. Конечно, при минимаксе может быть такая последовательность рассмотрения ходов, когда мы не будем делать никаких отсечений, тогда альфа-бета отсечение просто превратится в минимакс. В лучшем случае с помощью альфа-бета отсечения можно избежать проверки корня из числа всех ходов в минимаксе. Для того, чтоб избежать долгого времени работы (при такой О-большое сложности алгоритма), перебор в дереве делают на какую-то фиксированную величину и там проводят оценку узла. Вот эта оценка есть очень великое приближение к реальной оценке узла (то есть, перебора до конца дерева, а там результат - «выиграл, проиграл, ничья»). Насчет оценки узла есть просто кипа различных методик (можно прочесть в линках в конце статьи). Если кратко - то, естественно, подсчитываю материал игрока (согласно одной системе - целыми числами пешка - 100, конь и слон - 300, ладья - 500, ферзь - 900; согласно другой системе - действительными в частях от единицы) + позиция на доске данного игрока. Насчет позиции - то здесь начинается один из кошмаров написания шахмат, так как скорость работы проги будет в основном зависеть от оценочной функции и, если точнее, то от оценки позиции. Тут уже кто во что горазд. За спаренных тур игроку +, за прикрытость короля своими пешками +, за пешку возле другого конца доски + и т.д., а минусуют позицию висячие фигуры, открытый король и т.д. и т.п. - факторов можно написать кучу. Вот для оценки позиции в игре строится оценка позиции игрока, что делает ход, и от нее отнимается оценка соответствующей позиции противника. Как говорят, одна фотография иногда лучше тысячи слов, и, может, кусок кода на псевдо C# тоже будет лучше объяснений:

Enum CurentPlayer {Me, Opponent}; public int AlphaBetaPruning (int alpha, int beta, int depth, CurrentPlayer currentPlayer) { // value of current node int value; // count current node ++nodesSearched; // get opposite to currentPlayer CurrentPlayer opponentPlayer = GetOppositePlayerTo(currentPlayer); // generates all moves for player, which turn is to make move / /moves, generated by this method, are free of moves // after making which current player would be in check List moves = GenerateAllMovesForPlayer(currentPlayer); // loop through the moves foreach move in moves { MakeMove(move); ++ply; // If depth is still, continue to search deeper if (depth > 1) value = -AlphaBetaPruning (-beta, -alpha, depth - 1, opponentPlayer); else // If no depth left (leaf node), evalute that position value = EvaluatePlayerPosition(currentPlayer) - EvaluatePlayerPosition(opponentPlayer); RollBackLastMove(); --ply; if (value > alpha) { // This move is so good that caused a cutoff of rest tree if (value >= beta) return beta; alpha = value; } } if (moves.Count == 0) { // if no moves, than position is checkmate or if (IsInCheck(currentPlayer)) return (-MateValue + ply); else return 0; } return alpha; }

Думаю, не будут излишними некоторые объяснения насчет кода:

  • GetOppositePlayerTo() просто меняет CurrentPlayer.Me на CurrentPlayer.Opponent і наоборот
  • MakeMove() делает следующий ход из списка ходов
  • ply - глобальная переменная (часть класса), которая держит в себе количество полуходов, сделанных на данной глубине
Пример использования метода:

{ ply = 0; nodesSearched = 0; int score = AlphaBetaPruning (-MateValue, MateValue, max_depth, CurrentPlayer.Me); }
где MateValue - достаточно большое число.
Параметр max_depth - максимальная глубина, на которую опустится алгоритм в дереве. Следует иметь в виду, что псевдокод чисто демонстративный, но вполне рабочий.

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

Во-первых, применяется очень известная эвристика «нулевой ход» . В спокойной позиции противнику дают сделать два хода вместо одного и после этого рассматривают дерево на глубину (depth-2), а не (depth-1). Если после оценки такого поддерева окажется, что у текущего игрока все равно есть преимущество, то нет смысла рассматривать поддерево далее, так как после своего следующего хода игрок только сделает свою позицию лучше. Так как перебор полиномиальный, то выигрыш в скорости ощутимый. Иногда бывает так, что противник выровняет свое преимущество, тогда надо рассматривать все поддерево до конца. Пустой ход надо делать не всегда (например, когда один из королей под шахом, в цугцванге или в ендшпиле).

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

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

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

Все было бы хорошо, если бы альфа-бета отсечение гарантировано давало бы лучший ответ. Даже учитывая долгое время на перебор. Но не тут то было. Проблема в том, что после перебора на фиксированную величину проводится оценка позиции и все, а, как оказалось, в некоторых игровых позициях нельзя прекращать перебор. После многих попыток выяснилось, что перебор можно прекращать только в спокойных позициях. Поэтому в основном переборе дописали дополнительный перебор, в котором рассматриваются только взятия, promotions и шахи (называется форсированный перебор ). Также заметили, что некоторый позиции с разменом в середине также надо рассматривать поглубже. Так появились идеи насчет extensions і reductions , то есть углублений и укорачиваний дерева перебора. Для углублений найболее подходящие позиции типа ендшпиля с пешками, ухода от шаха, размен фигуры в середине перебора и т.д. Для укорачиваний подходят «абсолютно спокойные» позиции. В советской программе Каисса форсированный перебор был немного особенным - там после взятия во время перебора сразу начинался форсированный и его глубина не ограничивалась (так как за некоторое время он сам себя исчерпает в спокойной позиции).

Как говорил Энтони Хоар : "Premature optimization is the root of all evil in programming. " (примечание: для тех, кто считает, что данная цитата принадлежит Кнуту, есть интересные дискусии



Предыдущая статья: Следующая статья:

© 2015 .
О сайте | Контакты
| Карта сайта