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

[@sidristij]

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


я ходил вторым, заметив что не засчитала свой выигрыш :)

[@valemak]

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



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

[@sidristij]

выше описал как раз такую ситуацию :) Проиграл по-идее я :)

[@valemak]

Да я увидел, надо было мне таки обновить страницу перед тем как постить комментарий.

По счёту там ничья, если не изменяет память, обоим сторонам начисляется по единице.

[@valemak]

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

[@valemak]

Прочитал в Википедии что в рендзю, начинающий игрок при правильной игре всегда побеждает.

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

[@Idalgo]

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

[@backmeupplz]

Ну так не честно :( Ход — мой, а я уже выиграл :(

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

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

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

[@Arteben]

В первом случае «Крестики» имеют возможность закончить в ничью, тут или надо дождаться кагда они это сделают или заблокировать. И раунд тут же закончится.

[@backmeupplz]

Ясно. То есть недостаточно победить — нужно еще и не дать сыграть в ничью, так?

[@Arteben]

Если не хотите что бы обоим игрокам довали по очку, то да.

[@chibiryaev]

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

[@chibiryaev]

Уровень начинающего новичка — это я еще погорячился, там вообще уровень 5-6 летнего ребенка. Иногда встречаются просто (помягче сказать) нелепые ходы.

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

Вот на этом клочке, я и то одержал 16-ю победу

[@Arteben]

Ну так, вы — профессионал. Мне вас очень не хватало, когда я это писал. А так, уровень AI мне показался достаточным, он меня ведь обыгрывал(я не такой профи, как вы). А насчет ценности, для вас не ценно, а кому-то навьет мысли что-нибудь написать в том же духе, но уже с AI поумнее. Да и просто для развлечения, выходной же.

[@SuperKolobok]

Я не успел — хабра-эффект, хостинг выдает prevushenie_resursov_processora…

[@Arteben]

GitHub есть

[@gasizdat]

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

[@Arteben]

А тогда какое слово тут применительно вместо AI, алгоритм перебора? Тут AI используется не в контексте игровых стратегий, а в контексте небольшой игры, и реализован соотвественно. Извините, что применил неподобающие определения. Уже мотаю на ус. В следущий раз буду писать просто «Алгоритм по расчету ходов».

[@KvanTTT]

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

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

И я так понял, что у вас даже не реализован минимакс?

[@Arteben]

Правильно минимакса нет. Есть грубая оценка ходов на один ход по текущей ситуации.

[@Arteben]

Правильно минимакса нет. Есть грубая оценка ходов на один ход по текущей ситуации. (ошибся веткой)

[@czuryk]

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

[@Arteben]

Да пожалуйста)

[@Neir0]

Я недавно just for fun написал крестики нолики на js, что касается AI, то существуют классические подходы по его написанию для подобных игр. Нужно реализовать генератор ходов, построение дерева вариантов и функцию оценки позиции. Для сокращения дерева перебора следует применять эвристики (см. альфа бета отсечение) иначе на поле 19*19 ваша программа даже на один ход с трудом будет считать.