| 1 |
5 |
sumanta.chaudhuri |
/*
|
| 2 |
|
|
connect6.cpp
|
| 3 |
|
|
June 9, 2011
|
| 4 |
|
|
This file contains the game AI
|
| 5 |
|
|
By Kevin Nam
|
| 6 |
|
|
|
| 7 |
|
|
*/
|
| 8 |
|
|
|
| 9 |
|
|
#include <time.h>
|
| 10 |
|
|
#include <stdlib.h>
|
| 11 |
|
|
|
| 12 |
|
|
#include "util.h"
|
| 13 |
|
|
#include "connect6.h"
|
| 14 |
|
|
|
| 15 |
|
|
// Subtract this many points for moves at the edges.
|
| 16 |
|
|
#define EDGEPENALTY 5
|
| 17 |
|
|
|
| 18 |
|
|
using namespace std;
|
| 19 |
|
|
|
| 20 |
|
|
/* The cost function simply counts all of the consecutive stones of same colour in
|
| 21 |
|
|
every direction from the spot for which the points is being calculated.
|
| 22 |
|
|
|
| 23 |
|
|
Ex:
|
| 24 |
|
|
|
| 25 |
|
|
.DDLL
|
| 26 |
|
|
.DLDD
|
| 27 |
|
|
DXDDD
|
| 28 |
|
|
...D.
|
| 29 |
|
|
|
| 30 |
|
|
Above, X is the spot being calculated.
|
| 31 |
|
|
The points would be 2 (above) + 2(topright) + 3(right) + 1 (left) = 8.
|
| 32 |
|
|
It treats opponent's stones and own stones with equal weighting.
|
| 33 |
|
|
|
| 34 |
|
|
Return 0 if the spot y,x is already taken, else return the calculated value
|
| 35 |
|
|
|
| 36 |
|
|
*/
|
| 37 |
|
|
static int calculatepoints_golden(char board[][19], int y, int x, char colour){
|
| 38 |
|
|
int pts = 0, tempx = x, tempy = y, tcount = 0,bcount = 0;
|
| 39 |
|
|
int lcount = 0,rcount = 0,trcount = 0,tlcount = 0,brcount = 0,blcount = 0;
|
| 40 |
|
|
char tcolour = 0,bcolour = 0,lcolour = 0,rcolour = 0,tlcolour = 0,trcolour = 0,brcolour = 0,blcolour = 0;
|
| 41 |
|
|
|
| 42 |
|
|
if (board[y][x] != 0)
|
| 43 |
|
|
return 0;
|
| 44 |
|
|
|
| 45 |
|
|
// scan column above
|
| 46 |
|
|
if (y > 0){
|
| 47 |
|
|
tempy = y-1;
|
| 48 |
|
|
tempx = x;
|
| 49 |
|
|
tcolour = board[tempy][tempx];
|
| 50 |
|
|
while (1){
|
| 51 |
|
|
if (board[tempy][tempx] != tcolour || board[tempy][tempx] == 0) break;
|
| 52 |
|
|
tcount++;
|
| 53 |
|
|
if (tempy == 0) break;
|
| 54 |
|
|
tempy--;
|
| 55 |
|
|
}
|
| 56 |
|
|
}
|
| 57 |
|
|
// scan column below
|
| 58 |
|
|
if (y < 18){
|
| 59 |
|
|
tempy = y+1;
|
| 60 |
|
|
tempx = x;
|
| 61 |
|
|
bcolour = board[tempy][tempx];
|
| 62 |
|
|
while (1){
|
| 63 |
|
|
if (board[tempy][tempx] != bcolour || board[tempy][tempx] == 0) break;
|
| 64 |
|
|
bcount++;
|
| 65 |
|
|
if (tempy == 18) break;
|
| 66 |
|
|
tempy++;
|
| 67 |
|
|
}
|
| 68 |
|
|
}
|
| 69 |
|
|
// scan row to left
|
| 70 |
|
|
if (x > 0){
|
| 71 |
|
|
tempy = y;
|
| 72 |
|
|
tempx = x-1;
|
| 73 |
|
|
lcolour = board[tempy][tempx];
|
| 74 |
|
|
while (1){
|
| 75 |
|
|
if (board[tempy][tempx] != lcolour || board[tempy][tempx] == 0) break;
|
| 76 |
|
|
lcount++;
|
| 77 |
|
|
if (tempx == 0) break;
|
| 78 |
|
|
tempx--;
|
| 79 |
|
|
}
|
| 80 |
|
|
}
|
| 81 |
|
|
// scan row to right
|
| 82 |
|
|
if (x < 18){
|
| 83 |
|
|
tempy = y;
|
| 84 |
|
|
tempx = x+1;
|
| 85 |
|
|
rcolour = board[tempy][tempx];
|
| 86 |
|
|
while (1){
|
| 87 |
|
|
if (board[tempy][tempx] != rcolour || board[tempy][tempx] == 0) break;
|
| 88 |
|
|
rcount++;
|
| 89 |
|
|
if (tempx == 18) break;
|
| 90 |
|
|
tempx++;
|
| 91 |
|
|
}
|
| 92 |
|
|
}
|
| 93 |
|
|
// scan diagonal topleft
|
| 94 |
|
|
if (x > 0 && y > 0){
|
| 95 |
|
|
tempy = y-1;
|
| 96 |
|
|
tempx = x-1;
|
| 97 |
|
|
tlcolour = board[tempy][tempx];
|
| 98 |
|
|
while (1){
|
| 99 |
|
|
if (board[tempy][tempx] != tlcolour || board[tempy][tempx] == 0) break;
|
| 100 |
|
|
tlcount++;
|
| 101 |
|
|
if (tempx == 0 || tempy == 0) break;
|
| 102 |
|
|
tempx--;
|
| 103 |
|
|
tempy--;
|
| 104 |
|
|
}
|
| 105 |
|
|
}
|
| 106 |
|
|
// scan diagonal bottomright
|
| 107 |
|
|
if (x < 18 && y < 18){
|
| 108 |
|
|
tempy = y+1;
|
| 109 |
|
|
tempx = x+1;
|
| 110 |
|
|
brcolour = board[tempy][tempx];
|
| 111 |
|
|
while (1){
|
| 112 |
|
|
if (board[tempy][tempx] != brcolour || board[tempy][tempx] == 0) break;
|
| 113 |
|
|
brcount++;
|
| 114 |
|
|
if (tempx == 18 || tempy == 18) break;
|
| 115 |
|
|
tempx++;
|
| 116 |
|
|
tempy++;
|
| 117 |
|
|
}
|
| 118 |
|
|
}
|
| 119 |
|
|
// scan diagonal topright
|
| 120 |
|
|
if (x < 18 && y > 0){
|
| 121 |
|
|
tempy = y-1;
|
| 122 |
|
|
tempx = x+1;
|
| 123 |
|
|
trcolour = board[tempy][tempx];
|
| 124 |
|
|
while (1){
|
| 125 |
|
|
if (board[tempy][tempx] != trcolour || board[tempy][tempx] == 0) break;
|
| 126 |
|
|
trcount++;
|
| 127 |
|
|
if (tempx == 18 || tempy == 0) break;
|
| 128 |
|
|
tempx++;
|
| 129 |
|
|
tempy--;
|
| 130 |
|
|
}
|
| 131 |
|
|
}
|
| 132 |
|
|
// scan diagonal bottomleft
|
| 133 |
|
|
if (y < 18 && x > 0){
|
| 134 |
|
|
tempy = y+1;
|
| 135 |
|
|
tempx = x-1;
|
| 136 |
|
|
blcolour = board[tempy][tempx];
|
| 137 |
|
|
while (1){
|
| 138 |
|
|
if (board[tempy][tempx] != blcolour || board[tempy][tempx] == 0) break;
|
| 139 |
|
|
blcount++;
|
| 140 |
|
|
if (tempy == 18 || tempx == 0) break;
|
| 141 |
|
|
tempy++;
|
| 142 |
|
|
tempx--;
|
| 143 |
|
|
}
|
| 144 |
|
|
}
|
| 145 |
|
|
|
| 146 |
|
|
/// Now calculate the points
|
| 147 |
|
|
// Check if this is a winning move. Priority #1.
|
| 148 |
|
|
if ((tcount >= 5 && tcolour == colour) ||
|
| 149 |
|
|
(bcount >= 5 && bcolour == colour) ||
|
| 150 |
|
|
(lcount >= 5 && lcolour == colour) ||
|
| 151 |
|
|
(rcount >= 5 && rcolour == colour) ||
|
| 152 |
|
|
(tlcount >= 5 && tlcolour == colour) ||
|
| 153 |
|
|
(trcount >= 5 && trcolour == colour) ||
|
| 154 |
|
|
(brcount >= 5 && brcolour == colour) ||
|
| 155 |
|
|
(blcount >= 5 && blcolour == colour) ||
|
| 156 |
|
|
(tcount + bcount >= 5 && tcolour == colour && bcolour == colour) ||
|
| 157 |
|
|
(lcount + rcount >= 5 && lcolour == colour && rcolour == colour) ||
|
| 158 |
|
|
(tlcount + brcount >= 5 && tlcolour == colour && brcolour == colour) ||
|
| 159 |
|
|
(trcount + blcount >= 5 && trcolour == colour && blcolour == colour))
|
| 160 |
|
|
return 1000;
|
| 161 |
|
|
|
| 162 |
|
|
// Check if this move can stop opponent from winning. This move is priority #2.
|
| 163 |
|
|
if ((tcount >= 4 && tcolour != colour) ||
|
| 164 |
|
|
(bcount >= 4 && bcolour != colour) ||
|
| 165 |
|
|
(lcount >= 4 && lcolour != colour) ||
|
| 166 |
|
|
(rcount >= 4 && rcolour != colour) ||
|
| 167 |
|
|
(tlcount >= 4 && tlcolour != colour) ||
|
| 168 |
|
|
(trcount >= 4 && trcolour != colour) ||
|
| 169 |
|
|
(brcount >= 4 && brcolour != colour) ||
|
| 170 |
|
|
(blcount >= 4 && blcolour != colour) ||
|
| 171 |
|
|
(tcount + bcount >= 4 && tcolour != colour && bcolour != colour) ||
|
| 172 |
|
|
(lcount + rcount >= 4 && lcolour != colour && rcolour != colour) ||
|
| 173 |
|
|
(tlcount + brcount >= 4 && tlcolour != colour && brcolour != colour) ||
|
| 174 |
|
|
(trcount + blcount >= 4 && trcolour != colour && blcolour != colour))
|
| 175 |
|
|
return 500;
|
| 176 |
|
|
|
| 177 |
|
|
// Else sum up the counts, use this as the points.
|
| 178 |
|
|
pts = tcount + bcount + lcount + rcount + tlcount + trcount + blcount + brcount + 1;
|
| 179 |
|
|
// If at an edge, lower the points
|
| 180 |
|
|
if (x == 0 || x == 18 || y == 0 || y == 18){
|
| 181 |
|
|
if (pts >= EDGEPENALTY)
|
| 182 |
|
|
pts -= EDGEPENALTY;
|
| 183 |
|
|
else
|
| 184 |
|
|
pts = 0;
|
| 185 |
|
|
}
|
| 186 |
|
|
return pts;
|
| 187 |
|
|
}
|
| 188 |
|
|
|
| 189 |
|
|
/*
|
| 190 |
|
|
The AI Function that calls the cost function for every spot on the board.
|
| 191 |
|
|
It returns the location with the highest points. In the event of a tie, randomly decide.
|
| 192 |
|
|
Input the board and the colour being played.
|
| 193 |
|
|
Puts the move (in ASCII chars) inside move[4]. This is from [1 ... 19]
|
| 194 |
|
|
Puts the move (in integers) in moveY and moveX. This is from [0 ... 18]
|
| 195 |
|
|
*/
|
| 196 |
|
|
int connect6ai_golden(char board[][19], char colour, char move[4]){
|
| 197 |
|
|
int x,y,highx = 0, highy = 0,currenthigh = 0, temp;
|
| 198 |
|
|
srand(time(NULL));
|
| 199 |
|
|
int highRandom = 1;//rand();
|
| 200 |
|
|
// Sweep the entire board with the cost function
|
| 201 |
|
|
for (x = 0; x <= 18; x++){
|
| 202 |
|
|
for (y = 0; y <= 18; y++){
|
| 203 |
|
|
|
| 204 |
|
|
temp = calculatepoints_golden(board,y,x, colour);
|
| 205 |
|
|
if (temp > currenthigh){
|
| 206 |
|
|
highx = x;
|
| 207 |
|
|
highy = y;
|
| 208 |
|
|
currenthigh = temp;
|
| 209 |
|
|
highRandom = 1;//rand();
|
| 210 |
|
|
}
|
| 211 |
|
|
// If a tie happens, pseudo-randomly choose one between them
|
| 212 |
|
|
if (temp == currenthigh && temp != 0){
|
| 213 |
|
|
int tempRandom = 1;//rand();
|
| 214 |
|
|
if (tempRandom > highRandom){
|
| 215 |
|
|
highx = x;
|
| 216 |
|
|
highy = y;
|
| 217 |
|
|
highRandom = tempRandom;
|
| 218 |
|
|
}
|
| 219 |
|
|
}
|
| 220 |
|
|
}
|
| 221 |
|
|
}
|
| 222 |
|
|
|
| 223 |
|
|
// Modify the board based on current move.
|
| 224 |
|
|
//board[highy][highx] = colour;
|
| 225 |
|
|
|
| 226 |
|
|
// Increment by 1 because indexing starts at 1.
|
| 227 |
|
|
highy++;
|
| 228 |
|
|
highx++;
|
| 229 |
|
|
|
| 230 |
|
|
/// Convert the int coordinates to corresponding ASCII chars
|
| 231 |
|
|
if (highy >= 10){
|
| 232 |
|
|
move[0] = '1';
|
| 233 |
|
|
highy -= 10;
|
| 234 |
|
|
} else {
|
| 235 |
|
|
move[0] = '0';
|
| 236 |
|
|
}
|
| 237 |
|
|
if (highy == 0) move[1] = '0';
|
| 238 |
|
|
else if (highy == 1) move[1] = '1';
|
| 239 |
|
|
else if (highy == 2) move[1] = '2';
|
| 240 |
|
|
else if (highy == 3) move[1] = '3';
|
| 241 |
|
|
else if (highy == 4) move[1] = '4';
|
| 242 |
|
|
else if (highy == 5) move[1] = '5';
|
| 243 |
|
|
else if (highy == 6) move[1] = '6';
|
| 244 |
|
|
else if (highy == 7) move[1] = '7';
|
| 245 |
|
|
else if (highy == 8) move[1] = '8';
|
| 246 |
|
|
else if (highy == 9) move[1] = '9';
|
| 247 |
|
|
|
| 248 |
|
|
// Do same for x.
|
| 249 |
|
|
if (highx >= 10){
|
| 250 |
|
|
move[2] = '1';
|
| 251 |
|
|
highx -= 10;
|
| 252 |
|
|
} else {
|
| 253 |
|
|
move[2] = '0';
|
| 254 |
|
|
}
|
| 255 |
|
|
if (highx == 0) move[3] = '0';
|
| 256 |
|
|
else if (highx == 1) move[3] = '1';
|
| 257 |
|
|
else if (highx == 2) move[3] = '2';
|
| 258 |
|
|
else if (highx == 3) move[3] = '3';
|
| 259 |
|
|
else if (highx == 4) move[3] = '4';
|
| 260 |
|
|
else if (highx == 5) move[3] = '5';
|
| 261 |
|
|
else if (highx == 6) move[3] = '6';
|
| 262 |
|
|
else if (highx == 7) move[3] = '7';
|
| 263 |
|
|
else if (highx == 8) move[3] = '8';
|
| 264 |
|
|
else if (highx == 9) move[3] = '9';
|
| 265 |
|
|
|
| 266 |
|
|
return 0;
|
| 267 |
|
|
}
|
| 268 |
|
|
|
| 269 |
|
|
|
| 270 |
|
|
|
