«Умная» змейка на JavaScript используя QLearning
Ожидает приглашения
Здравствуйте, сегодня я хочу вам поведать о том как быстро написать ИИ на JavaScript.
Для начала напишем основу сайта на HTML.
Загружаем bootstrap, и фавиконку(иконку сайта):
Создаем «Контейнер» и заголовок.
Создаем таблицу:
Заполняем таблицу:
Закрываем теги и загружаем скрипты:
Отлично, с самым простым разобрались…
теперь время JavaScript…
Я просто вставлю код с комментариями вы же не против?
Кстати, для упрощения жизни себе и вам, я использовал JQuery.
Те, кто просто хотел код, вы можете идти, а тем, кому интересны подробности, прошу останьтесь.
Благодарю Вас всех за внимание, оставляйте комментарии, спрашивайте, я постараюсь ответить, вносите правки, я буду благодарен!
Для начала напишем основу сайта на 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 эпох — Она живет очень долго.
после большого количества эпох(попыток), перестает врезаться в стену и себя, и быстро обнаруживает еду, незамедлительно её поедая
Qlearning
NEAT
Первое обозначает обучение путём “пряника и кнута”.
То есть когда ИИ делает что то хорошее, например, в моей программе – змейка не врезается в стену; в другой программе — отличает кекс от собаки, то мы “поощряем” его, давая ему “Пряник” (хорошее число). И такой алгоритм помечается как “Хороший” и его следует придерживается.
А если же ИИ делает что то плохое, например, врезается в себя или ошибается в ответе, то мы “наказываем” его, давая “Кнут” (плохое число). И такие действия помечаются как плохие и их повторять не стоит.
NEAT в свою очередь, это скорее симуляция естественного отбора, чем обучение, так что мы ее не используем в нашей программке.
Информация о проекте
Для создания змейки я использовал следующие:
JavaScript – Описание алгоритма принятия решений для змейки.
HTML – Описание интерфейса пользователя:
Задержку скорости движения змейки, скорости обучения и силу поощрения/наказания
СSS – А именно Bootstrap, необходим для создания приятного глазу интерфейса.
Jquery – Для упрощения работы с JavаScript.
ВЫВОДЫ
Змейка после(при скорости 100):
1 эпохи – погибает почти сразу
10 эпох – живет 1-2 секунды
100 эпох – живет 10 секунд
1000 эпох – живет больше минуты
10000 эпох — Она живет очень долго.
после большого количества эпох(попыток), перестает врезаться в стену и себя, и быстро обнаруживает еду, незамедлительно её поедая
Благодарю Вас всех за внимание, оставляйте комментарии, спрашивайте, я постараюсь ответить, вносите правки, я буду благодарен!