Гра гомоку (хрестики-нулики, 5 в ряд)

image
Читаючи публікації на Хабре знайшов пару статей про алгоритм гри гомоку: цю і цю. У першій статті розібрані різні варіанти рішення задачі, але немає реалізації у вигляді гри, у другій — гра є, але комп'ютер «грає» слабенько. Я вирішив зробити свій варіант гри гомоку блекджеком досить сильною грою комп'ютера. Публікація про те, що в підсумку вийшло. Для тих, хто любить відразу в бій — сама гра.

Для початку хочу визначитися з основними моментами. По-перше, існує безліч різновидів ігри гомоку, я зупинився на такому варіанті: ігрове поле 15х15, хрестики першими ходять, виграє той, хто перший побудує 5 в ряд. По-друге, ігровий алгоритм розрахунку ходу комп'ютером для простоти буду називати AI.

Теорія AI

shebeko у своїй статті розглянув різні алгоритми AI. Зрозуміло, що при простому переборі всіх варіантів ходів при заглибленні на кілька ходів кількість необхідних розрахунків зашкалює. Тому треба реалізувати який-небудь алгоритм по-розумніші перебору в лоб.

Читаючи статтю, я задумався над фразою: «Гомоку — це расходящаяся гра з повною інформацією і раптовою смертю». Як приклад іншої гри з раптовою смертю наводяться шахи. В моєму розумінні між шахами і гомоку є величезна різниця: один хід у шахах може кардинально змінити розклад сил. У шахах фігури можуть ходити далеко і впливати на безліч клітин. Ферзь або човен потенційно можуть атакувати будь-яку клітину поля за 1 хід, т. е. за 1 хід можна поставити так, що будь-яка конкретна клітина буде атакована (якщо вільні лінії ходу і атаки). У гомоку такого ефекту немає, одна фігура («камінь» — хрестик або нулик) може впливати тільки на 5 сусідніх з нею клітин в кожну сторону. Це перша передумова до мого алгоритму AI.

Друге важливе припущення — в гомоку є «эндшпили» — шаблони які ведуть до перемоги. Пам'ятайте риторичне питання Тарантіно: «Як довго людина рахує до 600?» Аналогічно, щоб побудувати переможну лінію з 5 фігур, спочатку треба побудувати лінію з 4 (у загальному випадку: з 5 з 1 пропущеної з краю (лінія 4) або в середині), по іншому — ніяк. Продовжуючи міркування отримуємо що для 4 необхідна трійка, для трійки — двійка.

Я припустив, що такі шаблони ходів є щось аналогічне розрахунку ходів в глибину, т. к. ходи локальні (мають відносно малий радіус впливу на відміну від шахів, наприклад). Отже, можна просто перебрати всі можливі варіанти шаблонів для кожного потенційного ходу. Це друга половина алгоритму AI.

Залишилося визначити потенційні ходи — ті клітини поля в які можна поставити фігуру. У загальному випадку, потенційні ходи — це все порожні (вільні) клітини дошки. Враховуючи що ходи — локальні, то всі клітини нам не потрібні, можна розглянути тільки найближчі до вже стоять на дошці фігур. Це перша половина алгоритму AI.

Алгоритм AI
1. Визначення потенційних ходів
Т. к. вплив фігур локально, то немає сенсу визначати потенційні ходи щоразу заново. Можна їх просто накопичувати.
— Особлива ситуація: якщо на початку гри комп'ютер ходить першим — хід здійснюється в передустановлену клітку — центр дошки (масив потенційних ходів складається з 1 клітки).
— В подальшому, після ходу користувача або AI, масив потенційних ходів додаються поля віддалені на 2 клітини від осередку ходу (сусідні і сусідні з сусідніми), а осередок в яку вчинено хід видаляється з цього масиву.

2. Розрахунок значення важливості кожної клітини потенційних ходів
Для кожної клітини з масиву потенційних ходів:
1) збираються 4 лінії з 9 клітин в середині яких сама обрана клітка (2 діагональних, вертикальна, горизонтальна)
2) кожна лінія порівнюється з усіма наявними шаблонами. При входженні клітини в шаблон її значимість збільшується на вагу цього шаблону. Якщо в клітці є можливість поставити «вилку», то її вага буде в 2 рази більше (він буде просуммирован від ваг шаблонів двох ліній).

3. Вибір клітини з максимальним значенням ваги
Розрахунок ваг здійсняться окремо для атаки (спираючись на фігури AI) і захисту (порівняння ліній з фігур суперника з тими ж шаблонами), далі вони підсумовуються. І клітка з максимальною вагою — це кращий хід з точки зору AI.

Можливі поліпшення AI
Перше поліпшення — це додавання шаблонів, які я пропустив :)
Друге — реалізація алгоритму прорахунку хоча б на пару ходів вперед з метою виявлення потенційних «вилок» та серії переможних ходів в майбутньому. Це, до речі, основний спосіб як мені вдається обіграти AI — створення серії ходів в яких AI змушений закривати 4, щоб не програти (у нього по суті немає альтернативи ходу) і в результаті цієї серії ходів створюється вилка з двох предфинальных ліній (наприклад, з двох четвірок), так що зарити їх за один хід не можливо.

Реалізація гри
Гра написана на чистому JavaScript (без фреймворків типу jQuery). Графічний інтерфейс гри реалізований на Canvas.

Результат
Сама гра, вихідний код на гітхабі (MIT).

Дякую за увагу. Сподіваюся, вам було також приємно читати і грати, як мені — реалізовувати :)

P. S. Невелика прохання, якщо будете легко вигравати — прикріпіть, будь ласка, скріншот гри і ходи (з логів консолі) для аналізу і поліпшення алгоритму.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.