GrabDuck

Крестики-нолики на Erlang

:

Вступление


В статье мы попробуем написать игру крестики-нолики на поле размером 10x10, игрока (человека) с ботом (компьютер) с возможностью игры через браузер , игра считается законченной, в случае одного из 3-ох исходов:

1) Победил игрок
2) Победил компьютер
3) Ничья

Такие моменты как: установка, проверка, настройка пакетов заведомо упущены, об установке Erlang'a неоднократно писали, еще, данная программа не построена по принципам OTP. Все значимые моменты я буду сопровождать схематическими картинками.

Все тесты проводились на железе:

RAM 4 GB, i5, MAC OS X

Игра корректно работает в браузерах (в остальных проверка не производилась):
Chrome 19.0.1084.56
FF 13.0.1
Safari 5.1.6 (7534.56.5)
Opera 11.64

Небольшой словарь:

Список — можно рассматривать как массив;
Символ — крестик или нолик;
Клетка, точка — ячейка для хода, имеет координаты (X;Y), где 0 < X и Y <= 10;
Направление — любое из 4 вариаций: горизонтали, вертикали, первой диагонали или второй диагонали;
Последовательность — список из 5 координат.

Сетевое взаимодействие


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

Немаловажный момент — сторона пользователя(браузер) должна поддерживать keep-alive(постоянные) соединения, дело в том, что все взаимодействия игрока с программой реализуется посредством ajax get запросов, при такой реализации все последующие ajax get запросы будут происходят через одно соединение(socket) в неограниченном количестве*.

* Конкретной цифры после какой браузеры принудительно рвут соединение я не нашел, но однозначно могу утверждать, что до 1000 ajax get запросов через одно соединение браузеры не инициализируют закрытие сокета, а в самом худшем варианте на 1 игру понадобится 50 щапросов к серверу.

Фрагмент кода, который отвечает за обработку клиентов:

s(Port)-> 
	spawn(
		fun () -> 
			{ok, Socket} = gen_tcp:listen(Port, [list,{active, false},{packet, http}]),  
			accept_loop(Socket) 
		end).
accept_loop(Socket) ->
	{ok, CSocket} = gen_tcp:accept(Socket),
    Pid = spawn(
			fun () -> 
				client_socket() 
			end),
	gen_tcp:controlling_process(CSocket, Pid),
	Pid ! {take_socket, Csocket}, % race condition
accept_loop(Socket).
client_socket() ->
	Socket = receive {take_socket, S} -> S end,
	client_loop(Socket, [], []).

Алгоритм


Основная идея алгоритма основана на оценочной функции, просматриваются все пустые клетки и вычисляется коэффициент эффективности для данной клетки, это та выгода, которую мы получим, если сделаем ход в данную клетку, аналогичные действия и для соперника, какую выгоду он получит сделав ход в данную клетку.

Бзаовая формула:

G = M + A*N

M — выгода бота в данной клетки
N — выгода игрока в данной клетки
A — коэффициент агрессивности, если коэффициент увеличивать, бот будет переходить в защитную стратегию, если уменьшать, бот будет стремиться перехватить инициативу.

Теперь рассмотрим подробней:

Представим типичную игровую ситуацию:

Для начала нужно сгенерировать все близлежащие координаты для одной клетки, их может быть соответственно:

3 — если клетка угловая
5 — если клетка начальная или конечная
8 — при всех остальных вариантах

Код, который отвечает за генерацию:

get_all_empty_points([]) -> [];
get_all_empty_points([Head | Tail]) -> lists:usort(get_nearby_points(Head) ++ get_all_empty_points(Tail)).


%угловые координаты
get_nearby_points({X,Y}) when X =:= 1 andalso Y =:=1  -> [{X, Y+1}, {X+1, Y+1}, {X+1, Y}];
get_nearby_points({X,Y}) when X =:= 1 andalso Y =:=10  -> [{X+1, Y}, {X+1, Y-1}, {X, Y-1}];
get_nearby_points({X,Y}) when X =:= 10 andalso Y =:=10 -> [{X-1, Y}, {X-1, Y-1}, {X, Y-1}];
get_nearby_points({X,Y}) when X =:= 10 andalso Y =:=1 -> [{X, Y+1}, {X-1, Y+1}, {X-1, Y}];

%начальные и конечные X,Y
get_nearby_points({X,Y}) when X =:= 1  -> [{X, Y-1}, {X+1, Y-1}, {X+1, Y}, {X+1, Y+1}, {X, Y+1}];
get_nearby_points({X,Y}) when Y =:= 10 -> [{X+1, Y}, {X+1, Y-1}, {X, Y-1}, {X-1, Y-1}, {X-1, Y}];
get_nearby_points({X,Y}) when X =:= 10 -> [{X, Y-1}, {X-1, Y-1}, {X-1, Y}, {X-1, Y+1}, {X, Y+1}];
get_nearby_points({X,Y}) when Y =:= 1  -> [{X-1, Y}, {X-1, Y+1}, {X, Y+1}, {X+1, Y+1}, {X+1, Y}];

%остальные точки
get_nearby_points({X,Y}) -> [{X-1, Y+1}, {X, Y+1}, {X+1, Y+1}, {X+1,Y}, {X+1, Y-1}, {X, Y-1}, {X-1, Y-1}, {X-1, Y}].

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

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

Нужно сгенерировать все продолжения (ну или конец, как угодно) текущей клетки: горизонталь, вертикаль, первая диагональ, вторая диагональ, на рисунке обозначены точками — результат, который мы должны получить:

Код, который отвечает за генерация координат:

generate_point (horizontal, {X, Y}) -> [{X2,Y} || X2<-lists:seq(X-4, X+4, 1), X2 > 0, X2 < 11];
generate_point (vertical, {X, Y}) -> [{X,Y2} || Y2<-lists:seq(Y-4, Y+4, 1), Y2 > 0, Y2 < 11];
generate_point (fdiagonal, {X, Y}) -> [{X2,Y2} || X2<-lists:seq(X-4, X+4, 1), Y2<-lists:seq(Y-4,Y+4, 1), X2 > 0, Y2 > 0, X2 < 11, Y2 < 11, X2-Y2 == X-Y];
generate_point (sdiagonal, {X, Y}) -> [{X2,Y2} || X2<-lists:seq(X-4, X+4, 1), Y2<-lists:seq(Y-4,Y+4, 1), X2 > 0, Y2 > 0, X2 < 11, Y2 < 11, X2+Y2 == X+Y].

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

Необходимо просмотреть все отрезки длиной в 5 клеток, для этого находим самую крайнюю точку, отсчитываем 5 клеток, а далее со сдвигом в одну клетку просматриваем еще 4 отрезка, наглядно можно посмотреть на картинке:

На картинке выше, показан простой пример только для наглядности, не имеющий отношения к игровой ситуации. Когда мы просматриваем отрезок из 5 клеток, мы должны выполнять некоторые инструкции для каждой из 5 последовательностей:

1) Если последовательность прерывается противоположным символом, вес данной последовательности приравнивается к нулю.
2) Если в последовательности встречается клетка с текущем символом, значение счетчика увеличивается на 1, и выполняем переход на следующую позицию.
3) Если в последовательности присутствует пустая клетка, мы ее пропускаем и переходим на следующую позицию, при этом не увеличиваем значение счетчика.
4) Если собрана последовательность из 5 текущих символов, последовательности приравнивается большой вес, если последовательность собрал бот — ее вес приравниваем к 10 000, если последовательность собрал игрок — ее вес приравниваем к 1 000, дело в том, что бот должен оценивать свою победу выше, чем свою защиту в данной ситуации.
5) Если длина последовательности равна 1, приравниваем ее к 0, это только наш мнимый ход.

Формула оценочной функции:

          L
Gh = ∑ KC
i=1

L — общее количество ненулевых последовательностей
K — коэффициент, в нашем случае — 3
C — общее количество символов в последовательности, пункт 2.

Аналогично вычисляем для всех направлений: вертикали, для 2-ух диагоналей, далее суммируем все значения, это и есть выгода в численном эквиваленте:

M, N = Ghor + Gver + Gfdiag + Gsdiag

Код, который отвечает за подсчет эффективности:

calculate_point_gravity(_, _, [], _) -> [];
calculate_point_gravity(MovesX , MovesY, [Move | Rest], Aggress) -> 

PGravityX = calculate(generate_point(horizontal, Move), MovesX ++ [Move], MovesY, [], Move, 1000) +
calculate(generate_point(vertical, Move), MovesX ++ [Move], MovesY, [], Move, 1000) + 
calculate(generate_point(fdiagonal, Move), MovesX ++ [Move], MovesY, [], Move, 1000) + 
calculate(generate_point(sdiagonal, Move), MovesX ++ [Move], MovesY, [], Move, 1000),

PGravityY = calculate(generate_point(horizontal, Move), MovesY ++ [Move], MovesX, [], Move, 10000) +
calculate(generate_point(vertical, Move), MovesY ++ [Move], MovesX, [], Move, 10000) + 
calculate(generate_point(fdiagonal, Move), MovesY ++ [Move], MovesX, [], Move, 10000) + 
calculate(generate_point(sdiagonal, Move), MovesY ++ [Move], MovesX, [], Move, 10000),

PGravity = PGravityY + Aggress * PGravityX,

[{PGravity, Move}] ++ calculate_point_gravity(MovesX, MovesY, Rest, Aggress). 

loop(_,_,_,0, Counter) -> Counter;
loop([],_,_,_, Counter) -> Counter;
loop(_,_,_,_, opponent_point_find) -> 0;

loop([FC | RC], MovesX, MovesY, Num, Counter) ->
	Res = case exist_in_list(MovesX, FC) of
			true -> Counter + 1; % текущая клетка
			false -> % пустая или соперника
				case  exist_in_list(MovesY, FC) of
					true -> opponent_point_find; % соперника выход с цикла
					false -> Counter % пустая, пропускаем
				end
		   end,
loop(RC ,MovesX, MovesY, Num - 1, Res).

calculate(CList, MovesX, MovesY, Current, BreakElement, W) when Current == BreakElement -> 0;
calculate(CList, MovesX, MovesY, Current, BreakElement, W) ->
	Res =  loop(CList, MovesX, MovesY, 5, 0)
	NewRes = case Res of 
				opponent_point_find -> 0;
				0 -> 0; 
				1 -> 0; % 1 своя клетка
				5 -> W; % собрана последовательность из 5, 
				_ -> math:pow(3, Res) % все остальное возводим в степень
			 end,	
	[Head | Rest] = CList,
NewRes + calculate(Rest, MovesX, MovesY, Head, BreakElement, W).

Хочу заметить, что в функциях calculate и calculate_point_gravity, не используется хвостовая рекурсия, я не думаю, что это как-то скажется на производительности или потреблении памяти, из-за того, что количество итераций ничтожно мало.

Когда у нас подсчитан коэффициент эффективности для кажлой из клеток, мы выбираем наибольший:

lists:max(calculate_point_gravity(PlayerMovesX , PlayerMovesY, AllVariants, Agress)).

Можно еще добавить случайности, но я это посчитал излишним.

Проверка


Любая игра теряет смысл, без определения двух сторон: победителя и проигравшего, но иногда и вариант с ничьей.

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

На картинке показан базовый алгоритм (там 8 лучей во все стороны, из-за сжатия не видно) — просмотр всех клеток с текущем символом и увеличением значения счетчика, но с маленьким нюансом, каждое из 4 направлений разбивается на две части: верхнюю и нижнюю, после проверки обоих частей, выполняем суммирование и прибавляем единицу, если сумма равна 5, выигрышная последовательность найдена.

Остальное


Ну и конечно же, демо:

http://88.198.65.2:8000/

Сложность игры динамическая, можно изменять до последующего хода, по дефолту — 0.8, чем больше коэффициент сложности — бот переходит в защитную стратегию, чем меньше — стратегия атакующая, я советую поэкспериментировать с сложностью, по-моему, бот играет достаточно хорошо в пределах [0.5, 1].

Заранее прошу прощения у людей, которые за прокси, или те, у которых порт 8000 закрыт, у меня сейчас нет возможности перекинуть игру на 80 порт.

Исходники доступны на github'e — github.com/Tremax/eTicTacToe

Клиентскую часть не рассматриваю, из-за того, что там все тривиально.

Ссылки

algolist.manual.ru/games/fiveinarow.php

Буду рад услышать Ваши отзывы.