«Умная» змейка на JavaScript используя QLearning

Здравствуйте, сегодня я хочу вам поведать о том как быстро написать ИИ на JavaScript.

Для начала напишем основу сайта на HTML.

Загружаем bootstrap, и фавиконку(иконку сайта):

<!DOCTYPE html> 
<head> 
    <link rel="stylesheet" href="bootstrap.css"> <!--Вот здесь импортируем bootstrap-->
    <favicon src="FAV.ico" class="ico"></favicon><!--А здесь фавиконку(иконку сайта)-->
</head>

Создаем «Контейнер» и заголовок.


<body><!--Открываем тег body -->
        <br><!-- переносим строку -->
        <div class="container"><!-- Создаем элемент контейнер -->
            <H4>Qnake - made with Qlearning</H4><!-- Создаем заголовок -->

Создаем таблицу:


 <div class="row"> <!-- Создаем элемент строк -->
                    <div class="col-sm-6" id="game"> <!-- Здесь оставляем место где будет сама змейка -->
                    </div>
                        <div class="col-sm-8">  <!-- открываем место для таблицы -->
                        <table class="table table-bordered"> <!-- Создаем таблицу -->                           
                                <thead class="thead-dark"><tr><th>Control Panel</th><th>Value</th> </tr></thead> <!-- Делаем верх таблицы -->


Заполняем таблицу:

                                    <tbody>
                                    <tr><td>Highest Score</td><td> <input type="text" id="hscore" disabled="true" value="0"></td></tr>  <!-- Делаем строку таблицы и заблокированный ввод Высшего балла змейки -->
                                    <tr><td>No. Epochs</td><td> <input type="text" id="epoch" disabled="true" value="0"></td></tr> <!-- Делаем строку таблицы и заблокированный ввод Количества эпох змейки -->
                                    <tr><td>Rules Learnt</td><td> <input type="text" id="rlearnt" disabled="true" value="0"></td></tr> <!-- Делаем строку таблицы и заблокированный ввод количества правил что выучила змейка -->
                                    <tr><td>Game Speed(ms)</td><td> <input onchange="u1();" type="text" id="gspeed" value="0"></td></tr> <!-- Делаем строку таблицы и разблокированный ввод задержки движения змейки -->
                                    <tr><td>Learning Rate</td><td> <input onchange="u2();" type="text" id="lrate" value="1"></td></tr> <!-- Делаем строку таблицы и разблокированный ввод скорости обучения  змейки -->
                                    <tr><td>Discount Factor</td><td> <input onchange="u3();" type="text" id="dfactor" value="1"></td></tr> <!-- Делаем строку таблицы и разблокированный ввод  Коэффициента скидки  змейки -->
                                    </tbody>

Закрываем теги и загружаем скрипты:

                                    </tbody>
                                </table>
                            </div>
                        </div>
                    </div>
                    <script src="jquery-2.1.0.js"></script>
                    <script src="script.Js"></script> 
                </body>
            </html>


Отлично, с самым простым разобрались…

теперь время JavaScript…

Я просто вставлю код с комментариями вы же не против?

Много Букв

//Переменные
var env, lv_state = [],
    lv_action, lv_reward, lv_score = 0,
    lv_init = 'X',
    Q_table = {},
    gspeed = 100,
    started = true,
    maxScore = 0,
    epochs = 0,
    lv_reset = '';
document.getElementById("game").innerHTML = '<canvas id="canvas" width="500" height="500"></canvas>';

var canvas = $("#canvas")[0];
var ctx = canvas.getContext("2d");
var w = $("#canvas").width();
var h = $("#canvas").height();

//Создадим переменную с шириной ячейки для удобства управления
var cw = 10;
var d;
var food;
var score;


//Создаем змейку
var snake_array; //массив клеток, из которых состоит змея



$(document).ready(function () {
    //CANVAS

    var keys = [];
    window.addEventListener("keydown",
        function (e) {
            keys[e.keyCode] = true;
            switch (e.keyCode) {
                case 37:
                case 39:
                case 38:
                case 40: // кнопки стрелок
                case 32:
                    e.preventDefault();
                    break; // пробел
                default:
                    break; // не блокируем другие кнопки
            }
        },
        false);
    window.addEventListener('keyup',
        function (e) {
            keys[e.keyCode] = false;
        },
        false);


    function init() {
        d = "справа"; //Стандартное направление
        create_snake();
        create_food(); // Теперь мы видим частицу еды
        // наконец-то покажем счет
        score = 0;


        // Теперь переместим змейку с помощью таймера, который запустит функцию рисования
        // каждые 60 мс

        if (typeof game_loop != "undefined") clearInterval(game_loop);
        game_loop = setInterval(runGame, gspeed);
    }
    init();


    function create_snake() {
        var length = 1; //Длинна змейки
        snake_array = []; //пустой массив для начала
        for (var i = length - 1; i >= 0; i--) {
            // Это создаст горизонтальную змейку, начиная с верхнего левого угла
            snake_array.push({
                x: i,
                y: 0
            });
        }
    }

    // Давайте теперь создадим еду

    function create_food() {
        food = {
            x: Math.round(Math.random() * (w - cw) / cw),
            y: Math.round(Math.random() * (h - cw) / cw),
        };
        // Это создаст ячейку с x / y от 0 до 44
        // Потому что в строках и столбцах 45 (450/10) позиций
    }

    //Давайте покажем змейку теперь
    function runGame() {

        //инициализируем среду
        if (lv_init) {
            lv_init = '';
            env = new QnakeLearning();

            paint();
            lv_state = env.getState();
            lv_action = env.getAction(lv_state);
            env.implementAction(lv_action);
            paint();
        } else {
            if (!lv_reset) {
                env.reward(lv_state, lv_action); // Вознаграждай и учись
            } else {
                paint();
                lv_reset = '';
            }
            if (started == true) {
                lv_state = env.getState();
                lv_action = env.getAction(lv_state);
                env.implementAction(lv_action);
                paint();
                updateScore();

            } else {
                updateScore();
                checkGame();
                lv_reset = 'X';
            }
        }

    }

    function updateScore() {
        if (score > maxScore) {
            maxScore = score;
        }
        if (started == false) {
            epochs += 1;
        }
        document.getElementById("hscore").value = maxScore;
        document.getElementById("epoch").value = epochs;
        document.getElementById("rlearnt").value = Object.keys(Q_table).length;
        if (document.getElementById("gspeed").value == "0") {
            document.getElementById("gspeed").value = gspeed;
            document.getElementById("lrate").value = env.LearningRate;
            document.getElementById("dfactor").value = env.DiscountFactor;
        }
    }

    function paint() {
        // Чтобы избежать змеиного следа, нам нужно рисовать BG на каждом кадре
        // Давайте теперь раскрасим холст
        ctx.fillStyle = "black";
        ctx.fillRect(0, 0, w, h);
        ctx.strokeStyle = "white";
        ctx.strokeRect(0, 0, w, h);


        // Код движения змеи, чтобы двигаться.
        // Логика проста
        // Выдвигаем хвостовую ячейку и помещаем ее перед головной ячейкой
        var nx = snake_array[0].x;
        var ny = snake_array[0].y;
        // Это положение ячейки головы.
        // Мы увеличим его, чтобы получить новую позицию головы
        // Давайте теперь добавим правильное движение на основе направления
        if (d == "справа") nx++;
        else if (d == "слева") nx--;
        else if (d == "up") ny--;
        else if (d == "down") ny++;

        // Давайте теперь добавим предложения о завершении игры
        // Это перезапустит игру, если змея ударится о стену
        // Добавим код столкновения тела
        // Теперь, если голова змеи врезается в ее тело, игра перезапустится
        if (nx == -1 || nx == w / cw || ny == -1 || ny == h / cw || check_collision(nx, ny, snake_array)) {
            //перезагрузим игру
            started = false;
            // Давайте теперь немного упорядочим код.

        }

        // Давайте напишем код, чтобы змея съела еду
        // Логика проста
        // Если новое положение головы совпадает с положением еды,
        // Создаем новую голову вместо движения хвоста
        if (nx == food.x && ny == food.y) {
            var tail = {
                x: nx,
                y: ny
            };
            score++;
            //Создаем новую еду
            create_food();
        } else {
            var tail = snake_array.pop(); //Добавляем в массив новую часть
            tail.x = nx;
            tail.y = ny;
        }
        //Теперь добавим в змейку функцию поедания
        snake_array.unshift(tail); // возвращает хвост как первую ячейку
        for (var i = 0; i < snake_array.length; i++) {
            var c = snake_array[i];
            //Создадим клетки С  cw.px размером
            paint_cell(c.x, c.y);
        }

        //Рисуем еду
        paint_cell(food.x, food.y);
        //ПОказываем счет
        var score_text = "Score: " + score;
        ctx.fillText(score_text, 5, h - 5);

    }

    //Давайте сначала создадим общую функцию для рисования ячеек

    /* Функция проверки игры */
    function checkGame(){
        if(!started){
            init();
            started = true;
        }
    }
  
    function paint_cell(x, y) {
        ctx.fillStyle = "green";
        ctx.fillRect(x * cw, y * cw, cw, cw);
        ctx.strokeStyle = "black";
        ctx.strokeRect(x * cw, y * cw, cw, cw);
    }

    function check_collision(x, y, array) {
        // Эта функция проверяет, существуют ли предоставленные координаты x / y
        // в массиве ячеек или нет
        for (var i = 0; i < array.length; i++) {
            if (array[i].x == x && array[i].y == y) return true;
        }
        return false;
    }

    //Создаем контроль клавишами для подталкивания змеи
    $(document).keydown(function (e) {
        var key = e.which;
        // Мы добавим еще один пункт, чтобы предотвратить передачу заднего хода
        if (key == "37" && d != "справа") d = "слева";
        else if (key == "38" && d != "down") d = "up";
        else if (key == "39" && d != "слева") d = "справа";
        else if (key == "40" && d != "up") d = "down";
        // Теперь змейкой можно управлять с клавиатуры
    })


    //ОБУЧЕНИЕ ЗМЕИ
    var QnakeLearning = function () {
        this.reset();
    }
    QnakeLearning.prototype = {
        reset: function () {
            this.LearningRate = 0.1; //Скорость обучения 0 - 1
            this.DiscountFactor = 1; // Коэффициент скидки 0 - 1
            this.aLoop = 0;
            this.food = {};
        },
        getState: function () {
        //вектор состояния:
        //Впереди все чисто ?
        //Чисто слева ?
        //Впереди чисто ?
        //Впереди ли еда ?
        //Еда слева ?
        //Еда справа ?
            var s = [];
            var px = snake_array[0].x;
            var py = snake_array[0].y;
            var p1 = 0,
                p2 = 0,
                p3 = 0;

            if (started == false) { // Состояние игры окончено
                return [0, 0, 0, 0, 0, 0];
            }

            // Чисто ли слева? 0 - Нет 1 - Да
            if (d == "right") { //Движение вперед:x++;влево=y--;право=y++
                p1 = px + 1;
                p2 = py - 1;
                p3 = py + 1;
                s.push(checkIfClear(p1, py)); //Чисто ли передо мной
                s.push(checkIfClear(px, p2)); //Чисто ли слева от меня
                s.push(checkIfClear(px, p3)); //Чисто ли справа от меня

                s = s.concat(checkIfFood(px, py, d)); //проверка еды
            }
            if (d == "left") { //прямо:x--;слева=y++;справа=y--
                p1 = px - 1;
                p2 = py + 1;
                p3 = py - 1;
                s.push(checkIfClear(p1, py)); //Чисто ли передо мной
                s.push(checkIfClear(px, p2)); //Чисто ли слева от меня
                s.push(checkIfClear(px, p3)); //Чисто ли справа от меня

                s = s.concat(checkIfFood(px, py, d)); //проверка еды
            }
            if (d == "up") { //прямо:y--;слева=x--;справа=x++
                p1 = py - 1;
                p2 = px - 1;
                p3 = px + 1;
                s.push(checkIfClear(px, p1)); //Чисто ли передо мной
                s.push(checkIfClear(p2, py)); //Чисто ли слева от меня
                s.push(checkIfClear(p3, py)); //Чисто ли справа от меня

                s = s.concat(checkIfFood(px, py, d)); //проверка еды
            }
            if (d == "down") { //прямо:y++;слева=x++;справа=x--
                p1 = py + 1;
                p2 = px + 1;
                p3 = px - 1;
                s.push(checkIfClear(px, p1)); //Чисто ли передо мной
                s.push(checkIfClear(p2, py)); //Чисто ли слева от меня
                s.push(checkIfClear(p3, py)); //Чисто ли справа от меня

                s = s.concat(checkIfFood(px, py, d)); //проверка еды
            }
            return s;
        },
        getAction: function (state) {

            var q = [],
                qmax = 0,
                qf = [];
            for (l = 0; l < 3; l++) {
                q.push({
                    "a": l,
                    "q": this.getQ(state, l)
                });
            }
            q = sortByKey(q, 'q');
            q.reverse();

            qf.push(q[0]);
            if (q[0]["q"] == q[1]["q"]) {
                qf.push(q[1]);
            }
            if (q[0]["q"] == q[2]["q"]) {
                qf.push(q[2]);
            }


            if (food.x === this.food.x && food.y === this.food.y) {
                this.aLoop++;
            } else if (food.x != this.food.x || food.y != this.food.y) {
                this.food = food;
                this.aLoop = 1;
            }
            if (this.aLoop > 100) {
                this.food = {};
                this.aLoop = 1;
                return q[Math.floor(Math.random() * q.length)]["a"];
            }

            return qf[Math.floor(Math.random() * qf.length)]["a"];
        },
        implementAction: function (a) {
            //Движение 0 - прямо, 1 - слева, 2 - справа
            if (d == "up") {
                if (a == 1) {
                    d = "left";
                }
                if (a == 2) {
                    d = "right";
                }
            } else if (d == "down") {
                if (a == 1) {
                    d = "right";
                }
                if (a == 2) {
                    d = "left";
                }
            } else if (d == "right") {
                if (a == 1) {
                    d = "up";
                }
                if (a == 2) {
                    d = "down";
                }
            } else if (d == "left") {
                if (a == 1) {
                    d = "down";
                }
                if (a == 2) {
                    d = "up";
                }
            }
        },
        getQ: function (s, a) {
            var config = s.slice();
            config.push(a);
            if (!(config in Q_table)) {
                // Если в данной Q-таблице нет записи для данного действия-состояния
                // пара, возвращаем оценку вознаграждения по умолчанию как 0
                return 0;
            }
            return Q_table[config];
        },
        setQ: function (s, a, r) {
            var config = s.slice();
            config.push(a);
            if (!(config in Q_table)) {
                Q_table[config] = 0;
            }
            Q_table[config] += r;
        },
        reward: function (s, a) {
            var rewardForState = 0;
            var futureState = this.getState();

            var lv_string_c = JSON.stringify(s);
            var lv_string_f = JSON.stringify(futureState);
            if (lv_string_c != lv_string_f) {
            // Если змея сталкивается, награда = -1
                 // Если змея приближается к еде, награда = 1
                if ((s[0] == 0 && a == 0) || (s[1] == 0 && a == 1) || (s[2] == 0 && a == 2)) {
                    rewardForState = -1;
                }
                if ((s[0] == 1 && a == 0 && s[3] == 1) || (s[1] == 1 && a == 1 && s[4] == 1) || (s[2] == 1 && a == 2 && s[5] == 1)) {
                    rewardForState = 1;
                }

                var optimalFutureValue = Math.max(this.getQ(futureState, 0),
                    this.getQ(futureState, 1),
                    this.getQ(futureState, 2));
                var updateValue = this.LearningRate* (rewardForState + this.DiscountFactor * optimalFutureValue - this.getQ(s, a));

                this.setQ(s, a, updateValue);
            }
        }
    }

    function sortByKey(array, key) {
        return array.sort(function (a, b) {
            var x = a[key];
            var y = b[key];
            return ((x < y) ? -1 : ((x > y) ? 1 : 0));
        });
    }

    function checkIfClear(x1, y1) {
        if (x1 == -1 || x1 == w / cw || y1 == -1 || y1 == h / cw || check_collision(x1, y1, snake_array)) {
            return 0;
        } else {
            return 1;
        }
    }

    function checkIfFood(lx1, ly1, j) {

        var lv_s = [];

        if (j == "справа") { //прямо:x++;слева=y--;справа=y++
            //----------  ПРЯМО  ---------------
            if (food.y == ly1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СЛЕВА  ---------------
            if (food.y < ly1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СПРАВА  ---------------
            if (food.y > ly1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
        }
        if (j == "слева") { //прямо:x--;слева=y++;справа=y--
            //----------  ПРЯМО  ---------------
            if (food.y == ly1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СЛЕВА  ---------------
            if (food.y > ly1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СПРАВА  ---------------
            if (food.y < ly1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
        }
        if (j == "up") { //прямо:y--;слево=x--;справа=x++
            //----------  ПРЯМО  ---------------
            if (food.x == lx1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СЛЕВА  ---------------
            if (food.x < lx1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СПРАВА  ---------------
            if (food.x > lx1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
        }
        if (j == "down") { //прямо:y++;слево=x++;справа=x--
            //----------  ПРЯМО  ---------------
            if (food.x == lx1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  СЛЕВА  ---------------
            if (food.x > lx1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
            //----------  ПРАВО  ---------------
            if (food.x < lx1) {
                lv_s.push(1);
            } else {
                lv_s.push(0);
            }
            //----------------------------------
        }

        return lv_s;
    }

})



Кстати, для упрощения жизни себе и вам, я использовал JQuery.

Те, кто просто хотел код, вы можете идти, а тем, кому интересны подробности, прошу останьтесь.

Подробности здесь
Есть две популярные модели обучения:
Qlearning
NEAT
Первое обозначает обучение путём “пряника и кнута”.

То есть когда ИИ делает что то хорошее, например, в моей программе – змейка не врезается в стену; в другой программе — отличает кекс от собаки, то мы “поощряем” его, давая ему “Пряник” (хорошее число). И такой алгоритм помечается как “Хороший” и его следует придерживается.

А если же ИИ делает что то плохое, например, врезается в себя или ошибается в ответе, то мы “наказываем” его, давая “Кнут” (плохое число). И такие действия помечаются как плохие и их повторять не стоит.

NEAT в свою очередь, это скорее симуляция естественного отбора, чем обучение, так что мы ее не используем в нашей программке.

Информация о проекте


Для создания змейки я использовал следующие:

JavaScript – Описание алгоритма принятия решений для змейки.
HTML – Описание интерфейса пользователя:
Задержку скорости движения змейки, скорости обучения и силу поощрения/наказания
СSS – А именно Bootstrap, необходим для создания приятного глазу интерфейса.
Jquery – Для упрощения работы с JavаScript.

ВЫВОДЫ


Змейка после(при скорости 100):
1 эпохи – погибает почти сразу
10 эпох – живет 1-2 секунды
100 эпох – живет 10 секунд
1000 эпох – живет больше минуты
10000 эпох — Она живет очень долго.

после большого количества эпох(попыток), перестает врезаться в стену и себя, и быстро обнаруживает еду, незамедлительно её поедая

Благодарю Вас всех за внимание, оставляйте комментарии, спрашивайте, я постараюсь ответить, вносите правки, я буду благодарен!
Tags:
ai, javascript, js, змейка, искусственный интеллект.

You can't comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author's username will be hidden by an alias.