Пользователь
0,0
рейтинг
18 января 2014 в 23:20

Разработка → Небольшая игра «Крестики-нолики» на JavaScript


Это пост про небольшую игру «Крестики-нолики», которая была написана в целях пополнения опыта программирования на JS. Здесь применяются canvas и DojoBase. Библиотека используется для работы с событиями и для нахождения элементов по id(это очень удобно). Сanvas используется для отрисовки игрового поля.
Сама игра

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

Создание AI(тут и далее под AI подрузмевается комплекс алгоритмов перебора)

Тут самое интересное, конечно, это — AI. Я его «обучал» ходить более менее правильно в несколько этапов… Сначала, AI ставил свой значок на первой свободной клетке, которую находил. Немного потестировав, мне стало понятно, что это не интересно. Оно работает, но что-то тут не так. Поразмыслив, что лучше случай, чем такое, я прикрутил rand. После этого, стало чуточку по веселее, но все равно — не интересно.
Так, ладно, пусть сначала найдет все клетки, в которые можно(и нужно) сходить. То есть, что-то подобное(выделены синим).

Эти "нужные" клетки определяются по такому алгоритму"
Тут вся информация о игровом поле(что на нем происходит) содержится в двумерном глобальном массиве, значения элементов которого, показывают состояния клеток. Используется полный набор направлений, то есть проверяются все соседние клетки с данной. В массив_2 записываются результаты поиска «нужных» клеток.


Так, определили и что дальше с ними делать? Можно в любую из этих клеток ставить рандомно элемент. А можно и назначить каждой клетки оценки и на их основе выбрать наиболее лучший вариант, а затем его использовать. Звучит хорошо. Но, сначала надо решить другой вопрос.
При ходе AI за нолики, может возникнуть ситуация, что «нужных» клеток просто не будет. Например, при первом ходе раунда. Теперь надо придумать алгоритм по нахождению лучшего варианта в этой ситуации(или когда нет свободных клеток у крестиков или ноликов). И я считаю, что хорошо ходить туда, где наиболее просторно.
Поэтому тут реализован такой алгоритм
В м_отрезки записываются промежуточные данные, то есть ряды свободных клеток(вертикальных и горизонтальных) в определенном формате. В объект о_координата будет записан результат работы данной функции. Если отрезок является диаметром «пустого» квадрата, то это означает, что его центральная точка(клетка) — это центр квадрата свободных клеток, при том его стороны равны этому отрезку.


И настало время алгоритму, который выбирает ход на основе оценок.
Вот он

На вход этого алгоритма подается массив с «нужными» точками. Массив м_оценок, вспомогательный и суда записываются оценки клеток. Здесь, как и в предыдущем примере, используется полный перебор всех направлений вокруг клетки. Оценка осуществляется по двум параметрам: тип хода(блокирование или дополнение своего ряда) и длина линии элементов(1, 2, 3 или 4 клетки). Назначение происходит специальной функцией, где можно менять критерии. Эти оценки(критерии) суммируются по всем направлениям для данной клетки.


Заключение

Ну в итоге у меня у меня получилась небольшая игра с AI, который может обыгрывать новичков. Я его без труда выигрываю, не «в сухую», конечно, но все же. Стоит отметить, что когда играешь за «крестики», то как бы уровень сложности пониже, а вот за «ноликов» играть немного посложнее.
Режим нескольких раундов сделал задачу поинтереснее. Например, тут AI должен находить оптимальную клетку для превого хода. Еще возникла проблема с тем, что одиночные пустые клетки(в которых ходить бессмысленно), необходимо тоже было как-то «заштриховывать». Но, в конце концов я с этим справился.
Артём Бебенин @Arteben
карма
8,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (24)

  • +1
    Забавно, наткнулся на ничью :)


    я ходил вторым, заметив что не засчитала свой выигрыш :)
  • +1
    В Вашей версии крестиков-ноликов рендзю небольшой глюк. Если я выигрываю раунд, но у компьютера есть возможность следующим ходом тоже оформить 5 в ряд, то получается такая вот «боевая ничья».



    Если бы такой финт ушами и я мог делать в случае моего проигрыша, то готов признать это фичей. ;)
    • +1
      выше описал как раз такую ситуацию :) Проиграл по-идее я :)
      • 0
        Да я увидел, надо было мне таки обновить страницу перед тем как постить комментарий.

        По счёту там ничья, если не изменяет память, обоим сторонам начисляется по единице.
      • 0
        Я кстати, не думал что со стороны белкового игрока тоже возможно подобное читерство — у меня пока что программа выигрывала только именно таким способом.
  • 0
    Прочитал в Википедии что в рендзю, начинающий игрок при правильной игре всегда побеждает.

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

    • +1
      В рендзю ходы имеют сквозную нумерацию. Т.е. начинающий игрок — нечетные ходы, его соперник — четные.
      Для компенсации преимущества первого хода третий ход должен быть не ближе чем через две клетки от первого хода.
  • +1
    Ну так не честно :( Ход — мой, а я уже выиграл :(

    Скрытый текст
    image

    Update: еще веселее :( я сходил после того, как выиграл — а получилась ничья :(

    Скрытый текст
    image
    • 0
      В первом случае «Крестики» имеют возможность закончить в ничью, тут или надо дождаться кагда они это сделают или заблокировать. И раунд тут же закончится.
      • 0
        Ясно. То есть недостаточно победить — нужно еще и не дать сыграть в ничью, так?
        • +1
          Если не хотите что бы обоим игрокам довали по очку, то да.
  • +2
    Во-первых, крестики ходят первыми, а не нолики. Во-вторых, ваш алгоритм играет на уровне начинающего новичка (забавно, но бот вообще не реагирует на разрывную открытую тройку — тройка с пустой средней клеткой), я уже не говорю про вилки, обозы и форсированные ви́ны. В-третьих, я не очень понимаю смысл этого поста, какую пользу он несет?
    • +2
      Уровень начинающего новичка — это я еще погорячился, там вообще уровень 5-6 летнего ребенка. Иногда встречаются просто (помягче сказать) нелепые ходы.
      Скрытый текст
      Вот на этом клочке, я и то одержал 16-ю победу
      image
      • 0
        Ну так, вы — профессионал. Мне вас очень не хватало, когда я это писал. А так, уровень AI мне показался достаточным, он меня ведь обыгрывал(я не такой профи, как вы). А насчет ценности, для вас не ценно, а кому-то навьет мысли что-нибудь написать в том же духе, но уже с AI поумнее. Да и просто для развлечения, выходной же.
  • 0
    Я не успел — хабра-эффект, хостинг выдает prevushenie_resursov_processora…
  • +1
    Когда-то на заре обучения программированию, я написал простецкую игру в русские шашки. У нее был очень слабый уровень, но тем не менее, там действительно были небольшие элементы AI. В итоге это дало мне понимание, что игровой AI — штука сложная и пилить ее можно бесконечно. Успокоившись на этом, я к игровым AI больше не возвращался, но в голове кое-что отложилось. То, что в статье называется AI — по сути лишь немного модифицированный алгоритм неполного перебора без вычисления экстремумов фитнесс-функции (ее как таковой тоже нет). Игровой AI для пошаговых стратегий (а это любая настольная игра) должен как минимум рассчитывать ФИ на некоторой глубине ходов, причем для каждого хода должны высчитываться маскимальная ФИ на ходе противника и минимальная ФИ на очередном своем ходе. Таким образом, можно (грубо) взвесить неполный граф ходов (на определенную глубину) и выбрать нужную ветку как минимакс ФИ своих ходов и ходов противника.
    • +1
      А тогда какое слово тут применительно вместо AI, алгоритм перебора? Тут AI используется не в контексте игровых стратегий, а в контексте небольшой игры, и реализован соотвественно. Извините, что применил неподобающие определения. Уже мотаю на ус. В следущий раз буду писать просто «Алгоритм по расчету ходов».
  • 0
    Сначала, AI ставил свой значок на первой свободной клетке, которую находил. Немного потестировав, мне стало понятно, что это не интересно.

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

    И я так понял, что у вас даже не реализован минимакс?
    • +1
      Правильно минимакса нет. Есть грубая оценка ходов на один ход по текущей ситуации.
  • +1
    Правильно минимакса нет. Есть грубая оценка ходов на один ход по текущей ситуации. (ошибся веткой)
  • –1
    Спасибо за пост, я как раз разрабатываю подобную игру под STM32F4, для саморазвития. С Вашего разрешения хотел бы позаимствовать часть алгоритмов из Вашего примера.
    • +1
      Да пожалуйста)
  • +1
    Я недавно just for fun написал крестики нолики на js, что касается AI, то существуют классические подходы по его написанию для подобных игр. Нужно реализовать генератор ходов, построение дерева вариантов и функцию оценки позиции. Для сокращения дерева перебора следует применять эвристики (см. альфа бета отсечение) иначе на поле 19*19 ваша программа даже на один ход с трудом будет считать.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.