Информация
Отчет

Конкурс на кращий алгоритм для гри Реверсі на JavaScript

Микола Сеник

reversi_othelloJavaScript наразі — це друга мова програмування майже кожного розробника. Чому б не перевірити — наскільки добре ви знаєте JavaScript?
Прийміть участь у конкурсі на кращу реалізацію алгоритму пошуку наступного кроку для гри Реверсі. Завдання цікаве ще й тим, що це наче «штучний інтелект», а робочі проекти, як правило, позбавлені цього.
Переможець конкурсу буде визначений шляхом проведення «битви» між учасниками (битися будуть алгоритми звичайно). Найкращий алгоритм буде розміщено на нашому сайті з посиланням на його автора і кожен зможе позмагатися з ним в онлайн грі «Реверсі».
Увага, було зайдено помилку у реалізації допоміжної функції getLastMoves(). Помилку було виправлено, але це створило певні незручності для учасників.
Оновлений термін розміщення конкурсних робіт — до 22 лютого 2015 року.

Грати в Реверсі проти алгоритму, який переміг у битві.

Умови конкурсу

Ваш варіант алгоритму потрібно оформити у вигляді функції. Ця функція має повертати об’єкт з наступною структурою:

  • name — обов’язкове текстове поле з Вашим іменем;
  • move — обов’язковий метод з одним параметром. Якщо параметр дорівнює true — ваш хід чорними, якщо false — ви граєте за білих. Ця функція має повернути об’єкт з двома полями, наприклад, {col: «c», row: 4}. Що і буде варіантом Вашого ходу;
  • init — необов’язковий метод. Його система викликатиме на початку кожної партії.

Найпростіша реалізація може виглядати так:

var simplePlayer = function() {
    return {
        name: "Simple",
        move: function(isBlack) {
            for (var ci=0; ci<8; ci++) {
                for (var row=1; row<9; row++) {
                    var col = String.fromCharCode(ci + 97);
                    if ( isMoveValid(col, row) ) {
                        return {col: col, row: row};
                    }
                }
            }
        }
    };
};

Нічого складного, всього кілька рядків коду.

Перевірити свій варіант ви можете у тестовій битві. Достатньо перейти на сторінку http://jsfiddle.net/MykolaSenyk/yrd40x31/3/ і додати власну реалізацію.

Допоміжні функції

Вашим алгоритмам доступні 3 допоміжні глобальні функції:

1) getCell(col, row) — повертає поточне значення клітинки ігрового поля за координатами, наприклад, getCell(‘a’, 1). Тип клітинки — це одне з трьох значень:

    • e — порожня клітинка
    • b — чорна фішка
    • w — біла фішка

2) isMoveValid(col, row) — перевіряє чи можна зараз ходити за вказаними координатами. Викликайте цю функцію щоб остаточно переконатися, що обрали дозволений варіант ходу (true — хід дозволено, false — так ходити не можна).

3) getLastMoves() — повертає останні ходи у вигляді масиву об’єктів  - [{col: 'a', row: 1}]. Як правило, це один хід вашого супротивника. Але якщо останньому нікуди ходити, то ця функція поверне Ваш останній хід або декілька.

Особливості реалізації алгоритму

Координати клітин — це літера стовпця від «a» до «h» та число рядка від 1 до 8.

Гру завжди починають чорні, тому враховуйте цю обставину, коли викликаєте функцію getLastMoves(). Виклик її на першому ході чорних поверне порожній масив [], а вже для білих вона повідомить реальне значення.

Алгоритм битви автоматично визначає як переможця так і обставини зміни поточного гравця, коли йому не має куди ходити. Тому ваш алгоритм має розуміти, що метод move: function(isBlack) може бути викликаний декілька разів підряд без зміни поточного гравця. Про це буде свідчити запис «pass» у історії ходів. Пам’ятайте, що у такому випадку getLastMoves() — це саме ваші останні ходи.

Намагайтеся уникати надскладних комбінаторних реалізацій. Якщо алгоритм буде «думати» над ходом понад 3 секунди — його буде знято з конкурсу.

У випадку здійснення недопустимого ходу, наприклад, хід до вже зайнятої клітинки чи хід який не призводить до перевертання фішок — алгоритму зараховується технічна поразка. Тому перш ніж зробити хід, завжди перевіряйте його на коректність - isMoveValid(col, row).

Тестова битва складається з декількох партій. Гравці по черзі ходять чорними та білими. Якщо ви зберігаєте стан дошки у власній функції, то вам може знадобитися реалізація методу init(). Його буде викликано на початку кожної партії, ще до того як гравці зроблять перший хід.

Як користуватися тестовою битвою?

За посиланням http://jsfiddle.net/MykolaSenyk/yrd40x31/3/ Ви знайдете тестову битву з 2-ма простими алгоритмами, що збережені у змінних:

  • randomPlayer
  • simplePlayer

Створіть власний алгоритм у вигляді функції. Асоціюйте його з будь-якою глобальною зміною та встановіть цю змінну замість simplePlayer чи randomPlayer у останньому рядку.

Все. Натискайте кнопку Run і дивіться хто переміг.

Як буде відбуватись «битва»?

Це залежить від кількості учасників. Скоріше за все буде груповий етап. А вже переможці кожної групи будуть змагатися у грі на виліт. В будь-якому випадку детальні результати битви будуть опубліковані на нашому сайті.

Куди надсилати роботи?

Ваші роботи надсилайте на електрону пошту — msenyk@malkosua.com

Якщо маєте питання чи пропозиції — теж пишіть, із задоволенням їх розгляну.

Успіхів Вам та творчої наснаги!

13.01.2015

Добавить комментарий

Для отправки комментария вы должны авторизоваться.