Gomoku Game III
Content of the lesson:
- Principle of Gomoku
- Main Steps of Program
- Initializing Game Environment
- Inserting Names of Players
- One Move
- Displaying Game Status
- End of Game Evaluation
Summary of the Current State
We got to the step when we are able to place one of two possible types of stones inside the grid (according to which player is on move).
Your homework was to write a simple evaluation for the 3x3 grid. The game ends when any 3 stones of the same color (symbol) are placed in a row (horizontally, vertically or diagonally).
The solution is not difficult, theoretically you can browse every row and column and diagonals because the size of the array was set to 3x3 and find out if the whole row or column contains the same symbols (stones of the same color). If it is true then the game is over and the owner of these symbols (stones) wins.
When checking the diagonal sequences in the 3x3 array you only have to check the both diagonals.
We are going to solve a more difficult problem - we will be interested in the fact that a sequence of 3-5 stones (the value of variable delka) might form somewhere inside the array. We will also use our array which is bigger than 3x3 (generally its size is m x n).
End of Game Evaluation
Before creating an algorithm it is a good idea to think about it. :)
The first "violent" variant is to browse every column, row and diagonal and try to find a sequence of stones of required length. This solution is possible but needs much performance (CPU time) because the computer needs to do many steps to browse the whole array.
Which part of the array is required to be browsed to check whether the game is over or not?
Consider any layout of stones inside the array. We will set the delka variable to 4 for this example (a player will need a sequence of 4 stones to win the game).
You can see a situation when every player placed 7 stones (black symbols) in the following image. This is a situation when both players can win after placing one stone (red symbols). You should realize that the current layout is never important for the evaluation because the game can only be ended by placing a new stone which WILL FORM the winning sequence and also must be a PART OF IT. If you want to test the game because of its possible end, you only have to test whether a sequence was formed by the last added stone. There is no need to browse the whole array, you should only check every sequence which contains the last added stone (sequences of all directions).
We will explain every winning situation which can be formed by placing stones A, B and C.
Stone A
After placing this stone (consider its coordinates (i,j)=(3,4)) a winning sequence of 4 stones will be formed in the north-southern direction (according to the compass). How can we compute that a sequence in this direction was formed?
The last added stone is one of those 4 stones. We can continue browsing every field above it (to the north) where stones of the same color are located (without an empty field) and we count them. There is one stone in the field with coordinates (2,4), generally (i-1,j) - we moved one row upwards where the number of column is i-1=2.
Using the same method we have to count the stones below the last added one (in the south) - count all fields with stones of the same color without an empty field until you get to a field with the other color. The stones of the winning sequence are placed in fields with coordinates (i+1,j) and (i+2,j). The number of the row is increased in general.
If you count the number of winning stones while browsing the array, you find out that the number is GREATER THAN or EQUAL TO the value of delka (the length of a winning sequence to win the game).
Stone B
This is a similar situation; you only have to check another direction (North-West). You have to realize that you move to the field (2,2)=(i-1,j-1) and then to (1,1)=(i-2,j-2). Decrease the value of row (i) and column (j) by one in the NW direction.
After reaching the end of grid you have to also check the SE direction. There is one stone in the field (i+1, j+1).
Stone C
Describe the procedure as in the previous situations.
When testing other winning sequences in other directions the situation is the same.
You can describe the algorithm used after placing every stone using these steps in general:
- Take the coordinates of the last added stone (i,j)
- Until you find a winning sequence or make sure there is no such a sequence in every direction (containing the last added stone)
- Check every direction for a winning sequence (horizontal, vertical, diagonal).
Realizing the Algorithm for the NS Direction
Assume we want to write the part of the program to detect a winning sequence in the NS direction.
The last added stone is available in the variables r, s (row, column). The core of searching is the cycle (while stones of the same color are found in that direction). Create a new variable hledatdal which will be true in case that searching in the N direction should continue. Otherwise, it will be set to false and searching in that direction will be ended. You should set this variable to true at the beginning (we assume that searching should be started).
//(the same stones in the N direction)
hledatdal:=true;
while (hledatdal=true) do
begin
end;
We need to check whether there is a stone of the same color above the last added one (r,s). You need the program to remember the last added stone so create two new variables pomr and poms which will be used to store the coordinates of fields which will be browsed while searching. Set them to the same coordinates as the last added stone in the beginning - you set the starting point.
//(the same stones in the N direction)
hledatdal:=true;
pomr:=r;
poms:=s;
while (hledatdal=true) do
begin
end;
You have to move to the N direction in the body so decrease the value of the vertical coordinate by one (pomr variable).
//(the same stones in the N direction)
hledatdal:=true;
pomr:=r;
poms:=s;
while (hledatdal=true) do
begin
pomr:=pomr-1;
end;
To be able to ask whether there is a stone of the same color in the next field, you have to check if such a field exists at first (you can get out of bounds of array). Use a condition to find out if the new coordinate is greater than zero (the array has the size of 1..m, 1..n). In case that the value of pomr variable is zero, it means you are out of bounds and you cannot continue searching in this direction (set hledatdal to false).
pocetkamenu:= 1; //1 because of the last added stone
//(the same stones in the N direction)
hledatdal:=true;
pomr:=r;
poms:=s;
while (hledatdal=true) do
begin
pomr:=pomr-1;
if (pomr>0) then
begin
end
else
hledatdal:=false;
end;
If you reach the bounds of the array then the situation is clear. On the other hand, if you reach another field (pomr, poms) you have to analyze its content (3 values are possible: X stone, O stone and empty field). The last added type of stone is stored inside the variable typkamene so you can compare the content of this field (r,s) with each browsed field (pomr, poms). In case the contents are equal, you can continue searching next fields with the same color of stones (do not forget to increase the variable pocetkamenu by one).
pocetkamenu:= 1; //1 because of the last added stone
//(the same stones in the N direction)
hledatdal:=true;
pomr:=r;
poms:=s;
while (hledatdal=true) do
begin
pomr:=pomr-1;
if (pomr>0) then
begin
if (p[pomr,poms]=typkamene) then pocetkamenu:=pocetkamenu+1
else
hledatdal:=false
end
else
hledatdal:=false;
end;
The previous code computes the number of stones of the same color in the north direction from the last added stone. What next? It is necessary to continue using the same procedure in the south direction (BELOW the last added stone). Both directions (N and S) count the number of stones of the type saved inside variable typkamene. If the number of stones is equal to or greater than the value of variable delka (length of a winning sequence), then your algorithm has found the winning sequence and game is over. Using the similar procedure you should add the previous code once again (change the line pomr:pomr-1 to pomr:pomr+1 because of the change of direction). The variable pocetkamenu will be used from the previous direction without any changes.
//(the same stones in the S direction)
hledatdal:=true;
pomr:=r;
poms:=s;
while (hledatdal=true) do
begin
pomr:=pomr+1;
if (pomr>0) then
begin
if (p[pomr,poms]=typkamene) then pocetkamenu:=pocetkamenu+1
else
hledatdal:=false
end
else
hledatdal:=false;
end;
In the end you have to compare the value of variable pocetkamenu with the length of a winning sequence and end the game if necessary (using the variable konec:boolean).
if (pocetkamenu>=delka) then konec:=true;
In this moment, the algorithm to detect a winning sequence in the NS direction is complete. You have to add the remaining three directions and check if game is not over in each of them. In case that the winning sequence is found, the program does not have to browse other directions.
Homework
Complete the whole game and debug the final program to run correctly.