Comments 21
Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов:
Все, хорошо, но есть два замечания:
Игра известна под названием "пять в ряд"
Вот не надо приплетать эти популярные слова — ИИ — да не смешите меня, тогда шахматные программы вообще можно называть НАДМОЗГ, да реализовав алгоритм на R, можно было-бы сказать что проект из области bigdata.
В свое время данную игру даже на бейсике писали(просто брейпоинты по-другому звались ;-), а так, статье ставлю положительную оценку — "за волю к победе"
Гомоку и рэндзю грустно переминаются в углу.
В английском языке словосочетание artificial intelligence не имеет антропоморфной окраски, которую оно приобрело в традиционном русском переводе: слово intelligence в используемом контексте скорее означает «умение принимать разумные решения», а вовсе не «интеллект» (для которого есть английский аналог intellect).
В данном конкретном случае «интеллект» — вычислительная составляющая способности программы достигать своей цели (обыгрывать человека)
в своей узкой области применения.
В данном конкретном случае «интеллект» — вычислительная составляющая способности программы достигать своей цели (обыгрывать человека)
в своей узкой области применения.
Компьютерных соперников для игр испокон веков называли ИИ.
даже на бейсике писали
Вы так говорите, как будто написать игру на бейсике намного проще, чем не на бейсике.
Насколько я помню, в рэндзю начинающий выигрывает, если не ограничить его второй ход. У Вас программа научилась выигрывать при отсутствии ограничений?
Неверно, в рэндзю есть фолы и дебютный регламент.
Неверно,"Глубокая истина".
В «советском» рэндзю было ограничение на второй ход чёрных и не было фолов.
Программа не выигрывает гарантировано — ее можно улучшить
Крестики-нолики не шахматы и программа может гарантированно всегда выигрывать на таком большом поле. Я как то делал подобное обычным брутфорсом, используя оптимизацию альфа-бета отсечением. И даже не на полную глубину, а всего на несколько шагов. Чем эффективнее эвристическая функция, тем на меньшую глубину нужно сканировать игровое дерево. Уже плохо помню и если не ошибаюсь обыграть или достигнуть ничьи, можно было только на поле из 3 клеток при первом ходе игрока.
Минимакс совсем не страшен, просто попробуйте реализовать. Цель этого метода — выбрать последовательность ходов бота, которая при самых сильных ходах игрока-соперника приведет к лучшему для бота результату. Достигается эта цель путем «заглядывания в будущее» на некоторое количество ходов вперед и оценки состояния игровой доски в каждом из вариантов будущего. Реализовать минимакс можно рекурсивной функцией, в которой вы перебираете все варианты хода из некоторого набора для бота (копируете состояние поля, делаете ход) и, рекурсивно спускаясь, вызываете эту же функцию, но перебираете ходы игрока. Продолжаете рекурсию… Остается только вовремя остановиться, оценить, используя ваши эвристики, все позиции на нижнем уровне рекурсии и выбрать ход, который привел к наилучшей для бота позиции при любых ходах игрока.
В своё время в 70-х развлекались с этим на фортране. Оценочная функция была аналитической. Рекурсию позволить себе не могли. Играла программа безобразно.
Так что уважуха автору.
Так что уважуха автору.
Сначала мне показалось, что это действительно другая игра: слова
Только на словах «Кто-то из игроков делает ход (пускай крестики)» стало понятно, что нет.
Побеждает тот, кто поставит 5 фигур (если их можно так назвать) в ряд.можно понять и так, что каждый игрок может ставить любую «фигуру» по своему выбору.
Только на словах «Кто-то из игроков делает ход (пускай крестики)» стало понятно, что нет.
Очень слабо играет.
Неплохая попытка. Для курсовой и начинающего игрока — действительно «Сойдет!» Но, знаете, почему сильнейшие программы были написаны при помощи сильных игроков? Именно потому что программа играет на уровне своего хозяина. Отвлеченный математик не всегда способен уловить нюансы игры — что именно нужно анализировать и на что обращать внимание, сводя всё к тупому перебору вариантов. Вероятно поэтому долго не могли написать бота для Го, играющего на уровне выше первых любительских данов — профи игроки этим не занимались, а начинающий или даже средний игрок просто не способен алгоритмизировать сильную игру без тупого перебора, на который уходит много времени. АльфаГо справилась только с привлечением гигантских мощностей и огромных объемов обучения, а также с привлечением к разработке сильных игроков, которые указали узкие места. Кстати, у меня была идея, в каких случаях АльфаГо будет трудно одолеть человека (версии, игравшей с Ли Седолем).
Ваше честное «его можно обыграть, однако сделать это немножко проблематично лично для меня» — подтверждает правило. Попробуйте дойти в рэндзю или гомоку до уровня I дана — вы совсем по другому станете смотреть на свои «брейкпоинты» и возможно сможете написать более-менее сильного бота. Подскажу со своего среднего уровня — сильный игрок будет искать скорее «двойное обозначение» (т.е. позицию, в которой противник не может защититься от построения вилки, т.к. позиция позволяет построить две вилки в разных частях позиции), чем отыгрывать четверки (уменьшая комплексность позиции и теряя возможные линии атаки).
Ну и конечно изучите хотя бы историю вопроса — начиная с названия игр, которые вы пытаетесь алгоритмизировать (гомоку, пять в ряд) и их терминологии, их тактики и стратегии. Вступление в стиле «еще в древнем Китае была известна игра, в которую школьники и студенты всего мира играли на уроках в 20-м веке» определенно лучше вступления «не знаю кто придумал играть в крестики-нолики на доске 9х9». )) 9х9 — это обучающая доска в Го (на которой обычно не играли, просто показывали правила, начинающим), то есть это минимальная доска в играх с камнями (Го, Гомоку, Рэндзю). Для ускорения партии («сбацаем по быстрому, пока учитель не смотрит») играли и на такой маленькой доске, но играть на ней сложно, обычно использовали ученическую 13х13, которую японцы немного увеличили до 15х15 для игры в рэндзю, а нормальная доска для гомоку — 19х19 (обычная доска в Го).
Ваше честное «его можно обыграть, однако сделать это немножко проблематично лично для меня» — подтверждает правило. Попробуйте дойти в рэндзю или гомоку до уровня I дана — вы совсем по другому станете смотреть на свои «брейкпоинты» и возможно сможете написать более-менее сильного бота. Подскажу со своего среднего уровня — сильный игрок будет искать скорее «двойное обозначение» (т.е. позицию, в которой противник не может защититься от построения вилки, т.к. позиция позволяет построить две вилки в разных частях позиции), чем отыгрывать четверки (уменьшая комплексность позиции и теряя возможные линии атаки).
Ну и конечно изучите хотя бы историю вопроса — начиная с названия игр, которые вы пытаетесь алгоритмизировать (гомоку, пять в ряд) и их терминологии, их тактики и стратегии. Вступление в стиле «еще в древнем Китае была известна игра, в которую школьники и студенты всего мира играли на уроках в 20-м веке» определенно лучше вступления «не знаю кто придумал играть в крестики-нолики на доске 9х9». )) 9х9 — это обучающая доска в Го (на которой обычно не играли, просто показывали правила, начинающим), то есть это минимальная доска в играх с камнями (Го, Гомоку, Рэндзю). Для ускорения партии («сбацаем по быстрому, пока учитель не смотрит») играли и на такой маленькой доске, но играть на ней сложно, обычно использовали ученическую 13х13, которую японцы немного увеличили до 15х15 для игры в рэндзю, а нормальная доска для гомоку — 19х19 (обычная доска в Го).
Спасибо за комментарий.
Каюсь, я действительно не знал об истории вопроса. Впредь буду внимательнее.
К слову сказать, началось все с небольшого негласного спора с другом, и со своей первостепенной задачей движок справился — он обыграл его.
В то же время, я остался доволен результатом и решил им поделиться.
Каюсь, я действительно не знал об истории вопроса. Впредь буду внимательнее.
К слову сказать, началось все с небольшого негласного спора с другом, и со своей первостепенной задачей движок справился — он обыграл его.
В то же время, я остался доволен результатом и решил им поделиться.
Поделитесь пожалуйста идеей, как играть с АльфаГо.
Только с помощью АльфаГо
Сами создатели утверждали, что АльфаГо стремится не к преимуществу, а к результату — поэтому играет очень осторожно, а следовательно предпочитает уклоняться от прямых атак, значит это и надо использовать против нее.
В единственной партии где Ли Седоль смог обыграть ИИ — возникла комплексная позиция и бот совершил ряд ошибок. Это может указывать на то, что комплексные позиции со множеством вариантов пересекающихся групп боту просчитывать гораздо труднее, т.к. увеличивается количество вариантов и сложность расчетов из-за взаимного влияния камней (они почти каждый следующий ход могут представляться то как почти окруженные, то как съедающие тех, кто их почти окружил — это затрудняет линейный расчет на несколько ходов вперед).
Как примеры комплексных позиций:
1) на доске множество отдельных «кусочков»/кирпичей по 2-3 камня («стенок»), которые могут быть соединены во множестве разных вариантов. Я видел подобные позиции и они чрезвычайно сложны для расчета, т.к. готовых групп нет, а соединить их можно множеством различных вариантов.
2) группы взаимно пересекаются («разрезаниями») во многих местах (обычно такие формы можно встретить при убегании от края доски, или когда гонят противника вдоль края) — если таких взаимных разрезаний много и они достаточно близко друг к другу — позиция становится сложной для простого расчета новичком или ботом, т.к. взаимно пересеченные группы камней могут быть окружены то одним, то другим противником и почти каждый ход такая группа меняет свой вес с «почти окруженная» на «почти окружившая» — компьютеру считать такое очень сложно.
Для проверки моих предположений — Ли Седолю нужно было попробовать намеренно усложнять позицию на доске, делая множество разрезаний, не доводя формы до соединения, вбрасывая камни во все сколько-нибудь уязвимые места и атакуя все что можно. Профессионалу легко держать в голове конечный вариант, как будет соединена группа и как соединятся разрезания, а компьютер обычно создает себе некий слепок позиции с весами пунктов и камней/групп, не пересчитывая этот слепок каждый ход.
В единственной партии где Ли Седоль смог обыграть ИИ — возникла комплексная позиция и бот совершил ряд ошибок. Это может указывать на то, что комплексные позиции со множеством вариантов пересекающихся групп боту просчитывать гораздо труднее, т.к. увеличивается количество вариантов и сложность расчетов из-за взаимного влияния камней (они почти каждый следующий ход могут представляться то как почти окруженные, то как съедающие тех, кто их почти окружил — это затрудняет линейный расчет на несколько ходов вперед).
Как примеры комплексных позиций:
1) на доске множество отдельных «кусочков»/кирпичей по 2-3 камня («стенок»), которые могут быть соединены во множестве разных вариантов. Я видел подобные позиции и они чрезвычайно сложны для расчета, т.к. готовых групп нет, а соединить их можно множеством различных вариантов.
2) группы взаимно пересекаются («разрезаниями») во многих местах (обычно такие формы можно встретить при убегании от края доски, или когда гонят противника вдоль края) — если таких взаимных разрезаний много и они достаточно близко друг к другу — позиция становится сложной для простого расчета новичком или ботом, т.к. взаимно пересеченные группы камней могут быть окружены то одним, то другим противником и почти каждый ход такая группа меняет свой вес с «почти окруженная» на «почти окружившая» — компьютеру считать такое очень сложно.
Для проверки моих предположений — Ли Седолю нужно было попробовать намеренно усложнять позицию на доске, делая множество разрезаний, не доводя формы до соединения, вбрасывая камни во все сколько-нибудь уязвимые места и атакуя все что можно. Профессионалу легко держать в голове конечный вариант, как будет соединена группа и как соединятся разрезания, а компьютер обычно создает себе некий слепок позиции с весами пунктов и камней/групп, не пересчитывая этот слепок каждый ход.
Спасибо за ответ.
Смотрел игру в шахматы программы AlphaZero. Это универсальный алгоритм, который одинаково хорошо постигает го, сёги и шахматы, и для этого ему не требуется никаких дополнительных начальных знаний, кроме правил игры. Разработка компании Deep Mind. Просто фантастика.
В опубликованном документе (PDF, на английском) подробно описывается алгоритм самообучения гиганта и приводятся в пример десять партий.
Смотрел игру в шахматы программы AlphaZero. Это универсальный алгоритм, который одинаково хорошо постигает го, сёги и шахматы, и для этого ему не требуется никаких дополнительных начальных знаний, кроме правил игры. Разработка компании Deep Mind. Просто фантастика.
В опубликованном документе (PDF, на английском) подробно описывается алгоритм самообучения гиганта и приводятся в пример десять партий.
Sign up to leave a comment.
Крестики нолики «Без границ»