June 30, 2012 at 17:49Tic Tac Toe on Erlang
Introduction
In the article we will try to write a game of tic-tac-toe on a field of 10x10 in size, a player (person) with a bot (computer) with the ability to play through the browser, the game is considered finished, in the case of one of 3 outcomes:
1) The player won
2) The computer won
3) Draw
Such moments as: installation, verification, configuration of packages are deliberately missed, Erlang’s installation has been repeatedly written, moreover, this program is not built on the principles of OTP. I will accompany all significant points with schematic pictures.
All tests were carried out on hardware:
RAM 4 GB, i5, MAC OS X
The game works correctly in browsers (the rest was not checked):
Chrome 19.0.1084.56
FF 13.0.1
Safari 5.1.6 (7534.56.5)
Opera 11.64
A small dictionary:
List - can be considered as an array;
Symbol - a cross or a toe;
A cell, a point is a cell for a move, has coordinates (X; Y), where 0 <X and Y <= 10;
Direction - any of 4 variations: horizontal, vertical, first diagonal or second diagonal;
Sequence - a list of 5 coordinates.
Network connectivity
To interact with the user, the program will listen to the port - 8000, and wait for connections, after the client has connected, initialize the game.
An important point is that the user side (browser) must support keep-alive (permanent) connections, the fact is that all the player’s interactions with the program are implemented via ajax get requests, with this implementation all subsequent ajax get requests will occur through one connection (socket) in unlimited quantities *.
* I didn’t find a specific figure after which browsers forcefully disconnect the connection, but I can unequivocally say that up to 1000 ajax get requests through one connection, browsers do not initiate a socket closure, and in the worst case scenario, 50 game requests will be required per server.
A snippet of code that is responsible for processing clients:
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, [], []).Algorithm
The main idea of the algorithm is based on the evaluation function, all empty cells are scanned and the efficiency coefficient for a given cell is calculated, this is the benefit that we get if we make a move to a given cell, similar actions for an opponent, what benefit will he get by making a move to a given cell .
The basic formula is:
G = M + A * N
M - the profit of the bot in this cell
N - the profit of the player in this cell
A - the coefficient of aggressiveness, if the coefficient is increased, the bot will go into a defensive strategy, if it is reduced, the bot will try to seize the initiative.
Now consider in more detail:
Imagine a typical game situation:
First you need to generate all the nearby coordinates for one cell, they can be, respectively:
3 - if the cell is angular
5 - if the cell is initial or final
8 - with all other options, the
Code that is responsible for generating:
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}].
We perform similar actions for each cell in which the move was made, it does not matter whether it is the player or bot’s move, after which we delete duplicates and the existing moves. As a result, we get a list with the coordinates of all nearby cells, the dots indicate the coordinates that we should get:
Next, we need to directly calculate the benefit of the move to each of the cells. Consider a private option for one cell and apply to all cells in the list that we received earlier.
We need to generate all the extensions (well, or the end, whatever) of the current cell: horizontal, vertical, first diagonal, second diagonal, indicated by dots in the figure - the result we should get:
The code that is responsible for the generation of coordinates:
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].Now we will consider a particular variant of evaluating the effectiveness for the horizontal direction, these actions will be absolutely similar for other directions (vertical, diagonals).
It is necessary to look at all segments with a length of 5 cells, for this we find the most extreme point, count 5 cells, and then with a shift in one cell we look at 4 more segments, you can clearly see the picture:
The picture above shows a simple example for illustrative purposes only, not related to the game situation. When we scan a segment of 5 cells, we must follow some instructions for each of the 5 sequences:
1) If the sequence is interrupted by the opposite symbol, the weight of this sequence is equal to zero.
2) If a cell with the current symbol is found in the sequence, the counter value increases by 1, and go to the next position.
3) If the sequence contains an empty cell, we skip it and move on to the next position, while not increasing the counter value.
4) If a sequence of 5 current symbols is assembled, the sequence equals a lot of weight, if the sequence was assembled by a bot - its weight is equal to 10,000, if the sequence is assembled by a player - its weight is equal to 1,000, the fact is that the bot must evaluate its victory higher than their defense in this situation.
5) If the length of the sequence is 1, equate it to 0, this is only our imaginary move.
Evaluation function formula:
L
Gh = ∑ KC
i = 1
L - the total number of nonzero sequences
K - coefficient, in our case - 3
C - the total number of characters in the sequence, step 2. We
calculate in the same way for all directions: vertical, for 2 diagonals, then summarize all the values, this and there is a benefit in numerical equivalent:
M, N = Ghor + Gver + Gfdiag + Gsdiag
The code that is responsible for calculating the effectiveness:
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).I want to note that in the functions calculate and calculate_point_gravity, tail recursion is not used, I do not think that this will somehow affect performance or memory consumption, due to the fact that the number of iterations is negligible.
When we have calculated the efficiency coefficient for each of the cells, we choose the largest:
lists:max(calculate_point_gravity(PlayerMovesX , PlayerMovesY, AllVariants, Agress)).You can still add randomness, but I found this unnecessary.
Check
Any game loses its meaning, without defining two sides: the winner and the loser, but sometimes the option with a draw.
Now let's briefly review the winning check algorithm, the check is initialized after each subsequent player’s turn, and checks 3 outcomes in the order of the turn: player’s victory, bot’s victory, draw, the test function takes 2 arguments to the input, 1 - all the steps taken by the player, 2 - the last player move.
The basic algorithm is shown in the picture (there are 8 rays in all directions, it is not visible due to compression) - viewing all cells with the current symbol and increasing the counter value, but with a small nuance, each of the 4 directions is divided into two parts: upper and lower, after checking both parts, perform the summation and add one, if the sum is 5, the winning sequence is found.
Rest
And of course, the demo:
http://88.198.65.2:8000/
The complexity of the game is dynamic, you can change it until the next move, by default - 0.8, the greater the difficulty factor - the bot goes into a defensive strategy, the less - the attacking strategy, I I advise you to experiment with complexity, in my opinion, the bot plays quite well within [0.5, 1].
I apologize in advance to people who are behind a proxy, or those whose port 8000 is closed, I now have no way to transfer the game to port 80.
Sources are available on github'e - github.com/Tremax/eTicTacToe I
do not consider the client part, due to the fact that everything is trivial there.
References
algolist.manual.ru/games/fiveinarow.php
I will be glad to hear your feedback.
