-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathplan.txt
executable file
·132 lines (98 loc) · 6.69 KB
/
plan.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
--- Board Rendering and Game Playing ---
The board is to be rendered on the screen as such:
\\\\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\
\\ [ ] [ ] [ ] [ ] [ ] [ ] [ ] \\
\\ \\
\\ [ ] [ ] [ ] [ ] [ ] [ ] [ ] \\
\\ \\
\\ [ ] [ ] [ ] [ ] [ ] [ ] [ ] \\
\\ \\
\\ [ ] [ ] [ ] [ ] [ ] [ ] [ ] \\
\\ \\
\\ [ ] [ ] [ ] [ ] [ ] [ ] [ ] \\
\\ \\
\\ [ ] [ ] [ ] [ ] [ ] [ ] [ ] \\
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
When the cells are populated with a token, the " █ " character will be used. It will be colored according to the player that placed it.
Each cell will be stored as a cell object. Each cell object will include an array of related cells, which includes all cells adjacent to and diagonal to said cell.
If a cell is fewer than eight cells away from a wall in any given direction, the the cell in said direction is removed from the array of related cells because that cell does not need to be considered when checking if the game has been won.
To check if the game is won:
I. Iterate through each cell
II. Iterate through each cell in the array of related cells
III. Check if the cell's color is the same as the original cell
IV. If so, continue in the same direction until a cell of a different color or a cell without a token is found.
V. If the system iterates through four cells as such without conflict, count the game as a win in the corresponding color's favour.
VI. If not, continue to the next cell until all cells are checked
To generate the array of related cells:
I.
--- Solving Algorithm ---
The algorithm will have a few preliminary checks to see if its hand is forced
I. Check if a win for the AI is possible with one move; if so, make the move
II. Check if the opponent can win with one move; if so, block the opponent from making said move
Next, the algorithm will generate a list of all possible next moves it can make.
This effectively opens a simulation of the game being played.
For each move the algorithm will check if
I. The opponent will be able to win on their turn after the move is made
II. The algorithm will open a situation where it has two or more possible places it can win so that the opponent cannot possibly counter it
In the first case the algorithm will rule out the choice right away; in the second, it will make the move immediately.
SCORING
Before anything else can happen, the scoring for each board must be determined.
Positive Scores
Opponent Forced Hand - A case where the opponent cannot make a move because of an AI victory on next turn - +25pts
Blockade - Two-in-a-row - +10pts
Threat - Three-in-a-row - +30pts
Attack - Three-in-a-row that can turn into a win in one turn - +50pts
Forced Win - Situation where win for AI is inevitable; overrides all other items - +125pts
Negative Scores
Impossible Move - A case where the AI cannot make a move because of a filled column or an opponent victory on next turn - -15pts
Opponent Blockade - Two-in-a-row - -10pts
Opponent Threat - Three-in-a-row - -30pts
Opponent Attack - Three-in-a-row that can turn into a win in one turn - -50pts
Opponent Forced Win - Situation where win for opponent is inevitable; overrides all other items - -125pts
Note that threast and blockades are only considered as such if they would be able to be made into a connect four in the future
SEARCHING PROCESS
Now that we know how to evaluate board states, we need to also determine how to search into the future.
This will use a recursive algorithm. Here is the basic setup for the method:
I.Evaluate boardstate (go through regular scoring)
A. In case of an attack from the opponent side, continue scoring as usual and make the appropriate move immediately after
B. In case only one move is possible, continue scoring as usual and then make the move
C. In case the the human player has an inevitable win, immediately return -125. Inevitable win is:
1. Possibility to win with one move (if it is player's turn currently)
2. Two seperate attacks at the same time (regardless of turn)
3. Same applies for AI
D. In case the AI has an inevitable win, return 125
II. Calculate all possible moves the other team can make and prune as such:
A. Remove 'suicide moves' that result in the other player winning on the next move
B. Remove moves in columns that are already full
III. Deploy a new instance of the method on each of the child board states
A. In case of base case (maximum tree depth), immediately return the score of the current board state
IV. Each instance of the function will return an average score:
A. Averages all child node average scores...
B. With its own score
V. Average the scores given by the child nodes with the current board state's score
VI. Return the new score rounded to the nearest whole.
Minimax Searching Outline - No Pruning
I. Take the board, the current player, and the current tree depth as parameters
II. Determine which columns cannot be moved in
III. Duplicate the game board, once for each legal move
IV. Make the move on the game board
V. Passing the board, the other player, and the tree depth + 1 as a parameter, call upon the minimax algorithm again
VI. If this node is a leaf node, i.e, bottom of the tree or terminal state, calculate the score of the node. Return this score
VII. If not, compare the scores of all the children.
A. If playing as YELLOW, choose the lowest score and return it
B. If playing as RED, choose the highest score and return it
Minimax Special Scoring
When scoring for a minimax algorithm, it is essential that a victory state counts for the highest possible number of points and a defeat state counts for the lowest possible. Thus to score for minimax we will use a -10 - +10 range where it is impossible to achieve either extreme except through a win or loss. This will be achieved by using diminishing returns; as the score gets higher it becomes increasingly difficult to increase it. This will be achieved by a multiplier that approaches zero as the score approaches ten. As such, it will be impossible to reach ten or negative ten without a win or loss.
The multiplier will start at one. As the percentage of progress towards either extreme increases, the multiplier will decrease by an equivalent amount. In pseudocode:
float multiplier;
float score;
float percent;
if (score >= 0)
{
percent = score / 10;
}else
{
percent = score / (-10);
}
multiplier = 1.0m - percent;
This calculation is performed after every scoreable item is added to the score. As a backup, there will also be a check to see if the score is greater than ten; if it is, it is set back to 9.95. Scores are rounded to the nearest thousandth.