OpenCores
URL https://opencores.org/ocsvn/connect-6/connect-6/trunk

Subversion Repositories connect-6

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /connect-6/trunk/CONNECTK/connectk-2.0/src/ai
    from Rev 3 to Rev 4
    ↔ Reverse comparison
  •

Rev 3 → Rev 4

/serial_port.c
0,0 → 1,188
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <termios.h>
#include <sys/time.h>
#include "../shared.h"
 
 
/* All serial functions work on this board */
static Board *myboard = NULL;
static port=0;
// The AI has as much time as it wants, but moves after 1 second. Default is to wait 2 seconds
#define AI_WAIT_TIME 0.5
 
// FPGA has 1 second to make its move
#define MOVE_TIME_LIMIT 0.5
static int char_to_int(short x){
if(x>=48)
return x-48;
else
return 0;
}
//void wait(double seconds){
// timeval tim;
// gettimeofday(&tim, NULL);
// double t1=tim.tv_sec+(tim.tv_usec/1000000.0);
// while (1){
// gettimeofday(&tim, NULL);
// double t2=tim.tv_sec+(tim.tv_usec/1000000.0);
// if (t2-t1 >= seconds)
// break;
// }
//}
 
void setup_port(int fd) {
struct termios options;
fcntl(fd, F_SETFL, 0);
tcgetattr(fd, &options);
cfsetispeed(&options, B115200);
cfsetospeed(&options, B115200);
options.c_cflag |= (CLOCAL | CREAD);
tcsetattr(fd, TCSANOW, &options);
 
// set up non-blocking port, so that we can time out
int opts;
opts = fcntl(fd,F_GETFL);
if (opts < 0) {
perror("fcntl(F_GETFL)");
exit(EXIT_FAILURE);
}
opts = (opts | O_NONBLOCK);
if (fcntl(fd,F_SETFL,opts) < 0) {
perror("fcntl(F_SETFL)");
exit(EXIT_FAILURE);
}
return;
}
 
 
 
void move_to_ascii(int x,int y, char move[4]){
if (y >= 10){
move[0] = '1';
y -= 10;
} else {
move[0] = '0';
}
if (y == 0) move[1] = '0';
else if (y == 1) move[1] = '1';
else if (y == 2) move[1] = '2';
else if (y == 3) move[1] = '3';
else if (y == 4) move[1] = '4';
else if (y == 5) move[1] = '5';
else if (y == 6) move[1] = '6';
else if (y == 7) move[1] = '7';
else if (y == 8) move[1] = '8';
else if (y == 9) move[1] = '9';
 
// Do same for x.
if (x >= 10){
move[2] = '1';
x -= 10;
} else {
move[2] = '0';
}
if (x == 0) move[3] = '0';
else if (x == 1) move[3] = '1';
else if (x == 2) move[3] = '2';
else if (x == 3) move[3] = '3';
else if (x == 4) move[3] = '4';
else if (x == 5) move[3] = '5';
else if (x == 6) move[3] = '6';
else if (x == 7) move[3] = '7';
else if (x == 8) move[3] = '8';
else if (x == 9) move[3] = '9';
 
}
 
 
 
 
 
 
 
 
 
 
 
AIMoves *ai_serial(const Board *b){
int i,j,firstmove=0;
char move[4];
 
AIMoves *moves = aimoves_new();
AIMove fpgamove;
for(i=0;i<board_size;i++){
for(j=0;j<board_size;j++){
if (piece_at(b,i,j)!=PIECE_NONE) firstmove++;
}
}
if(firstmove<=1){
port = open("/dev/ttyS0", O_RDWR | O_NOCTTY | O_NONBLOCK);
setup_port(port);
if(b->turn==PIECE_WHITE){
write(port, "L",1);
}else{
write(port, "D",1);
}
printf("firstmove %d\n",firstmove);
if(!myboard){
myboard=board_new();
}else{
board_free(myboard);
myboard=board_new();
}
}
if(b->moves_left >1 || (firstmove<=1)){
for(i=0;i<board_size;i++){
for(j=0;j<board_size;j++){
if ((piece_at(myboard,i,j)==PIECE_NONE) && (piece_at(b,i,j)!=PIECE_NONE)){
printf("%d,%d\n",i+1,j+1);
move_to_ascii(i+1,j+1,move);
write(port,&move[0],1);
write(port,&move[1],1);
write(port,&move[2],1);
write(port,&move[3],1);
printf("AI move %c%c %c%c\n", move[2],move[3],move[0],move[1] );
}
}
}
}
sleep(1);
//move[0] = 0; move[1] = 0; move[2] = 0; move[3] = 0;
////////// Get Opponent's move
read(port,&move[0],1);
read(port,&move[1],1);
read(port,&move[2],1);
read(port,&move[3],1);
fpgamove.y=char_to_int(move[0])*10 + char_to_int(move[1])-1;
fpgamove.x=char_to_int(move[2])*10 + char_to_int(move[3])-1;
printf("FPGA move %d %d\n", fpgamove.x, fpgamove.y);
aimoves_append(moves, &fpgamove);
//move[0] = 0; move[1] = 0; move[2] = 0; move[3] = 0;
//read(port,&move[0],1);
//read(port,&move[1],1);
//read(port,&move[2],1);
//read(port,&move[3],1);
// printf("FPGA move %c%c %c%c\n", move[2],move[3],move[0],move[1] );
//fpgamove.x=char_to_int(move[2])*10 + char_to_int(move[3]) - 1;
//fpgamove.y=char_to_int(move[0])*10 + char_to_int(move[1]) - 1;
//printf("FPGA move %d %d\n", fpgamove.x, fpgamove.y);
//aimoves_append(moves, &fpgamove);
board_copy(b,myboard);
place_piece_type(myboard,fpgamove.x,fpgamove.y,b->turn);
return moves;
}
/montec.c
0,0 → 1,147
 
/*
 
connectk -- a program to play the connect-k family of games
Copyright (C) 2007 Jeff Deitch
 
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
 
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 
*/
 
#include "config.h"
#include <glib.h>
#include "../shared.h"
 
#define MONTE_N 10
#define MONTE_NUM_RUNS 1000
 
// sequences.c
AIMoves *move_utilities(const Board *b);
 
AIMoves *empty_cells(Board *b)
/* returns an array of the empty locations on board b */
{
int i, j;
AIMoves *empties = aimoves_new();
AIMove move;
 
for (i = 0; i < board_size; i++) {
for (j = 0; j < board_size; j++) {
if (piece_at(b, i, j) == PIECE_NONE) {
move.x = i;
move.y = j;
move.weight = 0.f;
aimoves_add(empties, &move);
}
}
}
return empties;
}
 
int mc_run(Board *b)
/* plays a random game on board b, returns 1 if the current player wins
and 0 otherwise */
{
Board *new_board = board_new();
board_copy(b, new_board);
 
AIMove move;
AIMoves *empties;
empties = empty_cells(new_board);
int tries = 0;
int i;
 
while ( TRUE ) {
 
/* if the board filled up, start over */
if (empties->len == 0) {
board_copy(b, new_board);
empties = empty_cells(new_board);
tries++;
if (tries == 10) {
g_debug("bailing");
board_free(new_board);
aimoves_free(empties);
return 0;
}
}
 
i = g_random_int_range(0, empties->len);
move = empties->data[i];
aimoves_remove_index_fast(empties, i);
 
place_piece(new_board, move.x, move.y);
 
if (check_win(new_board, move.x, move.y)) {
if (new_board->turn == board->turn) {
board_free(new_board);
aimoves_free(empties);
return 1;
}
else {
board_free(new_board);
aimoves_free(empties);
return 0;
}
}
 
new_board->moves_left--;
if (new_board->moves_left == 0) {
new_board->turn = other_player(new_board->turn);
new_board->moves_left = place_p;
}
}
}
 
AIMoves *ai_monte_carlo(const Board *b)
/* chooses the best move based on which one wins the most random games */
{
int i, k, wins, len;
 
Board *new_board = board_new();
 
AIMove move;
AIMoves *moves = move_utilities(b);
moves->utility = 0;
aimoves_crop(moves, MONTE_N);
 
len = moves->len;
 
for (i = 0; i < len; i++) {
 
move = moves->data[i];
 
board_copy(b, new_board);
place_piece(new_board, move.x, move.y);
 
if (check_win(new_board, move.x, move.y)) {
move.weight = MONTE_NUM_RUNS;
moves->data[i] = move;
moves->utility += MONTE_NUM_RUNS;
} else {
/* run the monte carlo trials */
wins = 0;
for (k = 0; k < MONTE_NUM_RUNS; k++) {
wins += mc_run(new_board);
}
move.weight = wins;
moves->data[i] = move;
moves->utility += wins;
}
}
 
board_free(new_board);
return moves;
}
montec.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: search.c =================================================================== --- search.c (nonexistent) +++ search.c (revision 4) @@ -0,0 +1,234 @@ + +/* + +connectk -- UMN CSci 5512W project + +*/ + +#include "config.h" +#include +#include +#include "../shared.h" +#include "../connectk.h" + +/* Variables required to check for cache hits */ +static int cache_id = -1, cache_depth = -1, cache_branch = -1; +static SEARCH cache_search = -1; +static AIMoves *cache_moves = NULL; +static AIWEIGHT cache_best; +static Player *cache_player; +static AIFunc cache_func; +static BCOORD cache_size; + +void dfs_cache_dump(void) +/* Called from tests.c to print out the DFS cache */ +{ + g_debug("DFS cache: "); + aimoves_print(cache_moves); + g_print("\n"); +} + +static void cache_set(int index, AIMove *move) +{ + if (move->weight < cache_best || index > place_p) + return; + if (cache_moves->len <= index) + cache_moves->len = index + 1; + cache_moves->data[index] = *move; + cache_best = move->weight; +} + +static AIWEIGHT df_search(Board *b, AIMoves *moves, Player *player, + int depth, int cache_index, + PIECE searched, AIWEIGHT alpha, AIWEIGHT beta) +/* Depth is in _moves_ */ +{ + int i, j; + + /* Halt and depth abort */ + if (ai_stop || depth < 1) + return moves->utility; + + /* Alpha-beta sanity check */ + if (alpha >= beta) { + g_warning("DFS alpha-beta failed sanity check"); + return moves->utility; + } + + /* Search only the top moves beyond the minimum */ + aimoves_sort(moves); + if (moves->len > player->branch) { + for (i = player->branch; i < moves->len; i++) + if (moves->data[i].weight != moves->data[0].weight) + break; + moves->len = i; + } + + /* No moves left -- its a draw */ + if (moves->len < 1) + return AIW_DRAW; + + /* Search each move available in depth first order */ + for (i = 0; i < moves->len; i++) { + Board *b_next; + AIMove *aim = moves->data + i; + AIMoves *moves_next; + + /* Did we get a bad move? */ + if (!piece_empty(piece_at(b, aim->x, aim->y))) { + g_warning("DFS utility function suggested a bad move " + "(%s)", bcoords_to_string(aim->x, aim->y)); + continue; + } + + /* Already searched here? */ + if (piece_at(b, aim->x, aim->y) == searched) + continue; + place_piece_type(b, aim->x, aim->y, searched); + + b_next = board_new(); + board_copy(b, b_next); + place_piece(b_next, aim->x, aim->y); + + /* Did we win? */ + if (check_win(b_next, aim->x, aim->y)) + aim->weight = AIW_WIN; + + /* Otherwise, search deeper */ + else { + int next_ci = cache_index + 1; + AIWEIGHT next_alpha = alpha, next_beta = beta; + AIFunc func; + + b_next->moves_left--; + + /* Player has changed */ + if (b_next->moves_left <= 0) { + b_next->moves_left = place_p; + b_next->turn = other_player(b->turn); + next_ci += place_p; + searched++; + next_alpha = -beta; + next_beta = -alpha; + } + + func = ai(player->ai)->func; + if (!func) { + g_warning("DFS player has no AI function"); + return moves->utility; + } + moves_next = func(b_next); + aim->weight = df_search(b_next, moves_next, player, + depth - 1, next_ci, searched, + next_alpha, next_beta); + aimoves_free(moves_next); + if (b_next->turn != b->turn) + aim->weight = -aim->weight; + } + + /* Debug search */ + if (opt_debug_dfsc) { + for(j = MAX_DEPTH - depth; j > 0; j--) + g_print("-"); + g_print("> d=%d, %s, u=%d, a=%d, b=%d %s\n", + depth, bcoords_to_string(aim->x, aim->y), + aim->weight, alpha, beta, + piece_to_string(b->turn)); + } + + board_free(b_next); + if (aim->weight > alpha) { + alpha = aim->weight; + cache_set(cache_index, aim); + + /* Victory abort */ + if (alpha >= AIW_WIN) + return AIW_WIN; + + /* Alpha-beta pruning */ + if (alpha >= beta) + return alpha; + } + } + + return alpha; +} + +void search(const Board *b, AIMoves *moves, Player *player) +{ + Board *copy; + AIFunc move_func = ai(player->ai)->func; + + /* Player is not configured to search */ + if (player->search == SEARCH_NONE) + return; + + /* Moves list does not need to be searched */ + if (moves->len <= b->moves_left) { + if (opt_debug_dfsc) + g_debug("DFS no choice abort"); + return; + } + + /* Board size changed, cache is invalidated */ + if (board_size != cache_size) + cache_moves = NULL; + cache_size = board_size; + + /* Cache hit, last or same board */ + if (player->cache && cache_moves && cache_moves->len && + cache_search == player->search && + cache_depth == player->depth && + cache_player == player && + cache_func == move_func && + cache_branch == player->branch) { + if (b->parent && cache_id == b->parent->ac.id) { + aimoves_remove(cache_moves, b->parent->move_x, + b->parent->move_y); + cache_id = b->ac.id; + } + if (cache_id == b->ac.id && cache_moves->len) { + if (cache_moves->len) { + aimoves_copy(cache_moves, moves); + if (opt_debug_dfsc) + g_debug("DFS cache HIT"); + return; + } + aimoves_free(cache_moves); + cache_moves = NULL; + } + } + + /* Cache miss */ + if (opt_debug_dfsc) + g_debug("DFS cache MISS"); + cache_id = b->ac.id; + if (!cache_moves) + cache_moves = aimoves_new(); + cache_moves->len = 0; + cache_best = AIW_MIN; + copy = board_new(); + board_copy(b, copy); + if (player->search == SEARCH_DFS) { + df_search(copy, moves, player, player->depth, 0, + PIECE_SEARCHED, AIW_LOSE, AIW_WIN); + if (cache_moves->len) + aimoves_copy(cache_moves, moves); + } else { + board_free(copy); + g_warning("Unsupported search type %d", player->search); + return; + } + board_free(copy); + + /* Debug DFS search */ + if (opt_debug_dfsc) + dfs_cache_dump(); + + /* Save params so we can check if we have a hit later */ + cache_player = player; + cache_search = player->search; + cache_depth = player->depth; + cache_branch = player->branch; + cache_func = move_func; +}
search.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: thread.c =================================================================== --- thread.c (nonexistent) +++ thread.c (revision 4) @@ -0,0 +1,181 @@ + +/* + +connectk -- a program to play the connect-k family of games +Copyright (C) 2007 Michael Levin + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + +*/ + +#include "config.h" +#include +#include "../shared.h" +#include "../connectk.h" + +/* FIXME: The AI thread function busy waits on Windows. For some reason, it fails to + deadlock itself on mutex1! */ + +int ai_stop = 0; + +static GMutex *ai_mutex1, *ai_mutex2; +static guint ai_done_source = 0; +static AIMove ai_move; +static GThread *ai_thread; +static int ai_halt = 0; + +static gboolean ai_done(gpointer user_data) +{ + if (opt_debug_thread) + g_debug("ai_done(): making AI move"); + make_move(ai_move.x, ai_move.y); + return FALSE; +} + +AIMoves *run_ai(Player *player) +{ + AIMoves *moves; + AIFunc func; + + if (opt_debug_thread) + g_debug("run_ai(): running AI function"); + ai_stop = FALSE; + func = ai(player->ai)->func; + if (!func) + return NULL; + moves = func(board); + if (player->search) + search(board, moves, player); + + ai_stop = FALSE; + return moves; +} + +static gpointer ai_thread_func(gpointer user_data) +{ + for (;;) { + AIMoves *moves; + + if (opt_debug_thread) + g_debug("ai_thread_func(): locking mutex1"); + g_mutex_lock(ai_mutex1); + if (opt_debug_thread) + g_debug("ai_thread_func(): mutex1 locked"); + if (ai_halt) { + ai_halt = FALSE; + g_mutex_unlock(ai_mutex1); + return NULL; + } + if (opt_debug_thread) + g_debug("ai_thread_func(): locking mutex2"); + g_mutex_lock(ai_mutex2); + if (opt_debug_thread) + g_debug("ai_thread_func(): mutex2 locked"); + if (ai(players[board->turn].ai)->func && !opt_pause_ai && + !board->won) { + ai_move.x = -1; + ai_move.y = -1; + moves = run_ai(players + board->turn); + + /* Choose an adjacent move if the AI returns nothing */ + if (!aimoves_choose(moves, &ai_move)) { + aimoves_free(moves); + moves = ai_adjacent(board); + aimoves_choose(moves, &ai_move); + } + + /* Print the move list utility */ + if (opt_print_u) + g_debug("AI %s utility %d (0x%x)", + ai(players[board->turn].ai)->s_desc, + moves->utility, moves->utility); + + ai_done_source = g_timeout_add(0, ai_done, NULL); + aimoves_free(moves); + } + g_mutex_unlock(ai_mutex2); + if (opt_debug_thread) + g_debug("ai_thread_func(): mutex2 unlocked"); + g_thread_yield(); + } + return NULL; +} + +void stop_ai(void) +{ + ai_stop = TRUE; +#ifndef NO_TRYLOCK + if (opt_debug_thread) + g_debug("stop_ai(): trylocking mutex1"); + g_mutex_trylock(ai_mutex1); +#endif + if (opt_debug_thread) + g_debug("stop_ai(): locking mutex2"); + g_mutex_lock(ai_mutex2); + if (opt_debug_thread) + g_debug("stop_ai(): mutex2 locked"); + if (ai_done_source) { + g_source_remove(ai_done_source); + ai_done_source = 0; + } + g_mutex_unlock(ai_mutex2); + if (opt_debug_thread) + g_debug("stop_ai(): mutex2 unlocked"); +} + +void start_ai(void) +{ + if (players[board->turn].ai == PLAYER_HUMAN) + return; + +#ifndef NO_TRYLOCK + if (opt_debug_thread) + g_debug("start_ai(): trylocking mutex1"); + g_mutex_trylock(ai_mutex1); +#endif + g_mutex_unlock(ai_mutex1); + if (opt_debug_thread) + g_debug("stop_ai(): mutex1 unlocked"); +} + +void halt_ai_thread(void) +{ + if (opt_debug_thread) + g_debug("halt_ai_thread(): unlocking mutex1, joining thread"); + ai_stop = TRUE; + ai_halt = TRUE; + g_mutex_unlock(ai_mutex1); + g_thread_join(ai_thread); + if (opt_debug_thread) + g_debug("halt_ai_thread(): mutex1 unlocked"); +} + +void start_ai_thread(void) +{ + GError *error = NULL; + + g_thread_init(NULL); + ai_mutex1 = g_mutex_new(); + ai_mutex2 = g_mutex_new(); + g_mutex_lock(ai_mutex1); + if (opt_debug_thread) + g_debug("start_ai_thread(): mutex1, mutex2 locked"); + + ai_thread = g_thread_create_full(ai_thread_func, NULL, 0, TRUE, TRUE, + G_THREAD_PRIORITY_NORMAL, &error); + if (error) + g_error("Failed to spawn AI thread"); +} +
thread.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: window.c =================================================================== --- window.c (nonexistent) +++ window.c (revision 4) @@ -0,0 +1,146 @@ + +/* + +connectk -- a program to play the connect-k family of games +Copyright (C) 2007 Michael Levin + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + +*/ + +#include "config.h" +#include +#include +#include "../shared.h" + +static int window_dir(const Board *b, BCOORD x, BCOORD y, PIECE type, + int dx, int dy, int *length, int *count) +{ + int i, j, min_i, max_i, min_block = 0, max_block = 0, max = 0; + PIECE p; + + if (!dx && !dy) + return 0; + + /* Find the lowest index i along our diagonal that is valid and is + still a window containing (x, y) and count the number of pieces + inside */ + for (i = 0; i > -connect_k; i--) { + p = piece_at(b, x + dx * i, y + dy * i); + if (p != type && p != PIECE_NONE) { + min_block = 1; + break; + } + } + min_i = max_i = ++i; + for (j = i; j < i + connect_k; j++) { + p = piece_at(b, x + dx * j, y + dy *j); + if (p == type) + max++; + else if (p != PIECE_NONE) + return 0; + } + + /* Slide out window along and find the smallest and largest maximum + count positions */ + j = max; + for (; i < 0; i++) { + p = piece_at(b, x + dx * i, y + dy * i); + if (p == type) + j--; + p = piece_at(b, x + dx * (i + connect_k), + y + dy * (i + connect_k)); + if (p == type) + j++; + else if (p != PIECE_NONE) { + max_block = 1; + break; + } + if (j == max) + max_i = i + 1; + else if (j > max) { + max = j; + min_i = max_i = i + 1; + } + } + + /* Check if we have blocked multiple threats with this move */ + *count = 1; + if (min_block || min_i > -connect_k + 1 || + ((p = piece_at(b, x - dx * connect_k, y - dy * connect_k)) != + type && p != PIECE_NONE)) + for (i = min_i; i < max_i; i++) { + p = piece_at(b, x + dx * i, y + dy * i); + if (p == PIECE_NONE) + (*count)++; + else if (p == PIECE_ERROR) + break; + } + if (max_block || max_i < 0 || + ((p = piece_at(b, x + dx * connect_k, y + dy * connect_k)) != + type && p != PIECE_NONE)) + for (i = min_i + connect_k; i < max_i + connect_k; i++) { + p = piece_at(b, x + dx * i, y + dy * i); + if (p == PIECE_NONE) + (*count)++; + else if (p == PIECE_ERROR) + break; + } + + *length = max; + return 1; +} + +static AIWEIGHT window(const Board *b, BCOORD x, BCOORD y, PIECE turn) +{ + int lines[MAX_CONNECT_K], xs[] = {1, 1, 0, -1}, ys[] = {0, 1, 1, 1}, i; + AIWEIGHT weight; + PIECE type; + + memset(lines, 0, sizeof (lines)); + type = piece_at(b, x, y); + if (type != PIECE_NONE) + return AIW_NONE; + for (i = 0; i < 4; i++) { + int length, count; + + if (!window_dir(b, x, y, turn, xs[i], ys[i], &length, &count)) + continue; + lines[length] += count; + } + + /* Bit pack the weight */ + weight = AIW_NONE; + for (i = 1; i < connect_k; i++) + weight += lines[i] << ((i - 1) * 6); + return weight; +} + +AIMoves *ai_windows(const Board *b) +{ + AIMoves *moves; + AIMove move; + PIECE opp = other_player(b->turn); + + moves = aimoves_new(); + moves->utility = AIW_NONE; + for (move.y = 0; move.y < board_size; move.y++) + for (move.x = 0; move.x < board_size; move.x++) { + move.weight = window(b, move.x, move.y, opp); + if (move.weight > AIW_NONE) + aimoves_append(moves, &move); + } + return moves; +}
window.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: ai.c =================================================================== --- ai.c (nonexistent) +++ ai.c (revision 4) @@ -0,0 +1,147 @@ + +/* + +connectk -- a program to play the connect-k family of games +Copyright (C) 2007 Michael Levin + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + +*/ + +#include "config.h" +#include +#include +#include +#include "../shared.h" +#include "../connectk.h" + +/* + * AIs + */ + +static AI ais[] = { + { "human", "Human", NULL }, + { "random", "Random", ai_random }, + { "adjacent", "Adjacent", ai_adjacent }, + { "threats", "Threats", ai_threats }, + /*{ "windows", "Windows", ai_windows },*/ + /*{ "priority", "Prioritized Threats", ai_priority },*/ + { "sequences", "Sequences", ai_sequences }, + { "mesh", "Mesh", ai_mesh }, + { "montecarlo", "Monte Carlo", ai_monte_carlo }, + { "serial", "Serial Port", ai_serial }, +}; + +static gboolean is_adjacent(const Board *b, BCOORD x, BCOORD y, int dist) +{ + int dx, dy, count; + PIECE p; + + if (!piece_empty(piece_at(b, x, y))) + return FALSE; + for (dy = -1; dy < 2; dy++) + for (dx = -1; dx < 2; dx++) { + if (!dx && !dy) + continue; + count = count_pieces(b, x, y, PIECE_NONE, dx, dy, &p); + if (count - 1 < dist && p != PIECE_NONE) + return TRUE; + } + return FALSE; +} + +AIMoves *enum_adjacent(const Board *b, int dist) +{ + AIMoves *moves; + AIMove move; + + move.weight = AIW_NONE; + moves = aimoves_new(); + for (move.y = 0; move.y < board_size; move.y++) + for (move.x = 0; move.x < board_size; move.x++) + if (is_adjacent(b, move.x, move.y, dist)) + aimoves_append(moves, &move); + aimoves_shuffle(moves); + return moves; +} + +AIMoves *ai_marks(const Board *b, PIECE min) +{ + AIMoves *moves = aimoves_new(); + AIMove move; + PIECE p; + + for (move.y = 0; move.y < board_size; move.y++) + for (move.x = 0; move.x < board_size; move.x++) + if ((p = piece_at(b, move.x, move.y)) >= min) { + move.weight = p - PIECE_THREAT0; + aimoves_set(moves, &move); + } + return moves; +} + +AIMoves *ai_random(const Board *b) +/* Returns a list of all empty tiles */ +{ + AIMove move; + AIMoves *moves; + + moves = aimoves_new(); + for (move.y = 0; move.y < board_size; move.y++) + for (move.x = 0; move.x < board_size; move.x++) + if (piece_empty(piece_at(b, move.x, move.y))) { + move.weight = + g_random_int_range(AIW_MIN, AIW_MAX); + aimoves_append(moves, &move); + } + return moves; +} + +AIMoves *ai_adjacent(const Board *b) +{ + AIMove move; + AIMoves *moves; + + /* Get all open tiles adjacent to any piece */ + moves = enum_adjacent(b, 1); + printf("ai adjacen move %d %d\n", moves->data[1].x, moves->data[1].y); + if (moves->len) + return moves; + + /* Play in the middle if there are no open adjacent tiles */ + move.x = board_size / 2; + move.y = board_size / 2; + move.weight = AIW_NONE; + aimoves_append(moves, &move); + return moves; +} + +const char *player_to_string(PLAYER p) +{ + return ais[p].l_desc; +} + +int number_of_ais(void) +{ + return sizeof (ais) / sizeof (*ais); +} + +AI *ai(int n) +{ + if (n >= 0 && n < number_of_ais()) + return ais + n; + return NULL; +} +
ai.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: threats.c =================================================================== --- threats.c (nonexistent) +++ threats.c (revision 4) @@ -0,0 +1,346 @@ + +/* + +connectk -- a program to play the connect-k family of games +Copyright (C) 2007 Michael Levin + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + +*/ + +#include "config.h" +#include +#include +#include "../shared.h" + +/* Bits per threat level */ +#define BITS_PER_THREAT 6 + +/* All threat functions work on this board */ +static Board *b = NULL; + +/* This is the line of threats currently being processed */ +static struct { + int threat[2]; + PIECE turn[2]; +} line[MAX_BOARD_SIZE]; + +/* Running tally of threats for both players */ +static int threat_counts[MAX_CONNECT_K + 1][2]; + +static AIWEIGHT threat_bits(int threat, PIECE type) +/* Bit pack the threat value */ +{ + if (threat < 1) + return 0; + + /* No extra value for building sequences over k - p unless it is + enough to win */ + if (b->turn == type && connect_k - threat <= b->moves_left) + threat = connect_k - place_p + 1; + else if (threat >= connect_k - place_p) + threat = connect_k - place_p - (type == b->turn); + + return 1 << ((threat - 1) * BITS_PER_THREAT); +} + +static void threat_mark(int i, int threat, PIECE type) +{ + int j, index = 0; + + if (threat <= 0) + return; + + /* No extra value for building sequences over k - p unless it is + enough to win */ + if (b->turn == type && connect_k - threat <= b->moves_left) + threat = connect_k - place_p + 1; + else if (threat >= connect_k - place_p) + threat = connect_k - place_p - (type == b->turn); + + /* Do not mark if this threat is dominated by a preceeding threat; + Likewise supress any smaller threats */ + for (j = i; j >= 0 && j > i - connect_k; j--) + if (line[j].threat[0] > threat) + return; + else if (line[j].threat[0] < threat) { + line[j].threat[0] = 0; + line[j].threat[1] = 0; + } + + /* Store up to two threats per tile in the line */ + if (line[i].threat[index]) + index++; + line[i].threat[index] = threat; + line[i].turn[index] = type; +} + +static int threat_window(int x, int y, int dx, int dy, + PIECE *ptype, int *pdouble) +{ + int min, max, count = 0; + PIECE p, type = PIECE_NONE; + + /* Check if this tile is empty */ + p = piece_at(b, x, y); + if (!piece_empty(p)) + return 0; + + /* Push forward the max and find the window type */ + for (max = 1; max < connect_k; max++) { + p = piece_at(b, x + dx * max, y + dy * max); + if (p == PIECE_ERROR) + break; + if (!piece_empty(p)) { + if (type == PIECE_NONE) + type = p; + else if (type != p) + break; + count++; + } + } + max--; + + /* Try to push the entire window back */ + for (min = -1; min > -connect_k; min--) { + p = piece_at(b, x + dx * min, y + dy * min); + if (p == PIECE_ERROR || piece_empty(p)) + break; + if (type == PIECE_NONE) + type = p; + else if (type != p) + break; + if (max - min > connect_k - 1) { + p = piece_at(b, x + dx * max, y + dy * max); + if (p == type) + count--; + max--; + } + count++; + } + min++; + + /* Push back min if we haven't formed a complete window, this window + can't be a double */ + if (max - min < connect_k - 1) { + for (min--; min > max - connect_k; min--) { + p = piece_at(b, x + dx * min, y + dy * min); + if (p == PIECE_ERROR) + break; + if (!piece_empty(p)) { + if (type != p) + break; + if (type == PIECE_NONE) + type = p; + count++; + } + } + *pdouble = 0; + min++; + } + + *ptype = type; + if (max - min >= connect_k - 1) + return count; + return 0; +} + +static AIWEIGHT threat_line(int x, int y, int dx, int dy) +{ + int i; + AIWEIGHT weight = 0; + + /* Mark the maximum threat for each */ + for (i = 0; x >= 0 && x < board_size && y >= 0 && y < board_size; i++) { + int count[2], tmp, double_threat = 1; + PIECE type[2]; + + count[0] = threat_window(x, y, dx, dy, type, &double_threat); + count[1] = threat_window(x, y, -dx, -dy, type + 1, + &double_threat); + if (count[1] > count[0]) { + tmp = count[1]; + count[1] = count[0]; + count[0] = tmp; + tmp = type[1]; + type[1] = type[0]; + type[0] = tmp; + } + line[i].threat[0] = 0; + line[i].threat[1] = 0; + threat_mark(i, count[0], type[0]); + if (double_threat) + threat_mark(i, count[1], type[1]); + x += dx; + y += dy; + } + + /* Commit stored line values to the board */ + x -= dx; + y -= dy; + for (i--; x >= 0 && x < board_size && y >= 0 && y < board_size; i--) { + AIWEIGHT bits[2]; + PIECE p; + + bits[0] = threat_bits(line[i].threat[0], line[i].turn[0]); + bits[1] = threat_bits(line[i].threat[1], line[i].turn[1]); + p = piece_at(b, x, y); + if (piece_empty(p) && line[i].threat[0]) { + threat_counts[line[i].threat[0]][line[i].turn[0] - 1]++; + if (line[i].threat[1]) + threat_counts[line[i].threat[1]] + [line[i].turn[1] - 1]++; + if (p >= PIECE_THREAT0) + place_threat(b, x, y, p - PIECE_THREAT0 + + bits[0] + bits[1]); + else + place_threat(b, x, y, bits[0] + bits[1]); + } + if (b->turn != line[i].turn[0]) + bits[0] = -bits[0]; + if (b->turn != line[i].turn[1]) + bits[1] = -bits[1]; + weight += bits[0] + bits[1]; + x -= dx; + y -= dy; + } + + return weight; +} + +AIMoves *ai_threats(const Board *original) +{ + AIMoves *moves; + AIWEIGHT u_sum = 0; + int i; + + b = board_new(); + board_copy(original, b); + + /* Clear threat tallys */ + for (i = 0; i < connect_k; i++) { + threat_counts[i][0] = 0; + threat_counts[i][1] = 0; + } + + /* Horizontal lines */ + for (i = 0; i < board_size; i++) + u_sum += threat_line(0, i, 1, 0); + + /* Vertical lines */ + for (i = 0; i < board_size; i++) + u_sum += threat_line(i, 0, 0, 1); + + /* SE diagonals */ + for (i = 0; i < board_size - connect_k + 1; i++) + u_sum += threat_line(i, 0, 1, 1); + for (i = 1; i < board_size - connect_k + 1; i++) + u_sum += threat_line(0, i, 1, 1); + + /* SW diagonals */ + for (i = connect_k - 1; i < board_size; i++) + u_sum += threat_line(i, 0, -1, 1); + for (i = 1; i < board_size - connect_k + 1; i++) + u_sum += threat_line(board_size - 1, i, -1, 1); + + moves = ai_marks(b, PIECE_THREAT(1)); + moves->utility = u_sum; + board_free(b); + return moves; +} + +void debug_counts(void) +{ + int i, sum = 0; + + if (!b) + return; + + g_debug("Threat counts (black, white):"); + for (i = 1; i < connect_k; i++) { + g_debug("%d: %3d %3d", i, threat_counts[i][0], + threat_counts[i][1]); + sum += threat_counts[i][0] * threat_bits(i, b->turn) - + threat_counts[i][1] * + threat_bits(i, other_player(b->turn)); + } + if (sum > 0) + g_debug("Threat sum: %d (10^%.2f)", sum, log10((double)sum)); + else if (sum < 0) + g_debug("Threat sum: %d (-10^%.2f)", sum, log10((double)-sum)); + else + g_debug("Threat sum: 0"); +} + +static int threat_number(int player, int threat) +{ + return threat_counts[threat][player] / (connect_k - threat); +} + +AIMoves *ai_priority(const Board *b) +{ + AIMoves *moves; + int i, j, stage[2] = {1, 1}, mask, bits; + + moves = ai_threats(b); + + /* Do not prioritize if we've won */ + if (threat_counts[connect_k - place_p + 1][b->turn - 1]) { + moves->utility = AIW_WIN; + return moves; + } + + /* Find the largest supported threat for each player */ + for (i = 2; i < connect_k; i++) { + if (threat_number(0, i - 1) >= place_p && + threat_number(0, i) > place_p) + stage[0] = i; + if (threat_number(1, i - 1) >= place_p && + threat_number(1, i) > place_p) + stage[1] = i; + } + + if (opt_debug_stage) + g_debug("Stages %d/%d", stage[0], stage[1]); + + /* Do not prioritize if we're losing */ + if (stage[b->turn - 1] <= stage[other_player(b->turn) - 1]) { + moves->utility = -stage[other_player(b->turn) - 1]; + return moves; + } + + /* Threats above the player's stage are no more valuable than the + stage */ + bits = 1 << (stage[b->turn - 1] * BITS_PER_THREAT); + mask = bits - 1; + for (i = 0; i < moves->len; i++) { + AIWEIGHT w = moves->data[i].weight, w2; + + if (w < AIW_THREAT_MAX && w >= bits) { + w2 = w & mask; + w = w & ~mask; + for (j = stage[b->turn - 1]; + w && j < connect_k - place_p + 1; j++) { + w = w >> BITS_PER_THREAT; + w2 += w & mask; + } + moves->data[i].weight = w2; + } + } + + /* Stage determines weight */ + moves->utility = stage[b->turn - 1]; + return moves; +}
threats.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: sequences.c =================================================================== --- sequences.c (nonexistent) +++ sequences.c (revision 4) @@ -0,0 +1,381 @@ + +/* + +connectk -- a program to play the connect-k family of games +Copyright (C) 2007 Jeff Deitch + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + +*/ + +#include "config.h" +#include +#include +#include "../shared.h" + +int utility_upper_bound; + +/* arrays for holding the utility and threat values for each window */ +int white_window_sequence_array[MAX_BOARD_SIZE][MAX_BOARD_SIZE][4]; +int black_window_sequence_array[MAX_BOARD_SIZE][MAX_BOARD_SIZE][4]; +int white_window_threat_array[MAX_BOARD_SIZE][MAX_BOARD_SIZE][4]; +int black_window_threat_array[MAX_BOARD_SIZE][MAX_BOARD_SIZE][4]; + +/* arrays for holding the marks used for counting threats */ +int whites_marks[MAX_BOARD_SIZE][MAX_BOARD_SIZE]; +int blacks_marks[MAX_BOARD_SIZE][MAX_BOARD_SIZE]; + +/* the sum of all the windows' values for threats and utility */ +int white_window_sequence_count; +int black_window_sequence_count; +int white_threat_count; +int black_threat_count; + +/* the max sequence on a board */ +int max_white_sequence; +int max_black_sequence; + +/* Returns an integer to identify the window */ +static int window_id(BCOORD x, BCOORD y, int i) +{ + return x * board_size * 4 + y * 4 + i + 1; +} + +static void clear_all() +{ + /* clears all values in the matricies that hold the window scores and threat info */ + int x, y, d; + for (x = 0; x < board_size; x++) { + for (y = 0; y < board_size; y++) { + + blacks_marks[x][y] = 0; + whites_marks[x][y] = 0; + + for (d = 0; d < 4; d++) { + white_window_sequence_array[x][y][d] = 0; + black_window_sequence_array[x][y][d] = 0; + white_window_threat_array[x][y][d] = 0; + black_window_threat_array[x][y][d] = 0; + } + } + } + + white_window_sequence_count = 0; + black_window_sequence_count = 0; + white_threat_count = 0; + black_threat_count = 0; + + max_black_sequence = 0; + max_white_sequence = 0; +} + +/* A utility function of a particular window for a given player */ +static void window_sequence(const Board *b, BCOORD x, BCOORD y, int i, PIECE player) +{ + int sequence, count_sequence, count_threat, dx, dy, ddx, ddy, j, len; + int ddxs[] = {1, 0, 1, 1}; + int ddys[] = {0, 1, 1, -1}; + int to_mark[MAX_CONNECT_K]; + + ddx = ddxs[i]; + ddy = ddys[i]; + + len = 0; + count_sequence = 0; + count_threat = 0; + sequence = 0; + + if (player == PIECE_WHITE) { + // We are recalculating this window's threat level. + // Start be taking this window's previous threat out of the sum + // and reset it to 0. + white_threat_count -= white_window_threat_array[x][y][i]; + white_window_threat_array[x][y][i] = 0; + + // Do the same for the sequence count. + white_window_sequence_count -= white_window_sequence_array[x][y][i]; + white_window_sequence_array[x][y][i] = 0; + + // step through the window. + for (dx = 0, dy = 0; dx < connect_k && dy < (int)connect_k; dx += ddx, dy += ddy) { + if (x + dx < 0 || y + dy < 0 || x + dx >= board_size || y + dy >= board_size) { + break; + } + // If this window was the one that marked this spot, unmark it so we can recheck. + if (whites_marks[x + dx][y + dy] == window_id(x, y, i)) { + whites_marks[x + dx][y + dy] = 0; + } + + if (piece_at(b, x + dx, y + dy) == PIECE_NONE) { + count_sequence++; + if (whites_marks[x + dx][y + dy] == 0) { + count_threat++; + to_mark[len++] = x + dx; + to_mark[len++] = y + dy; + } + } else if (piece_at(b, x + dx, y + dy) == player) { + count_sequence++; + count_threat++; + sequence++; + } + } + + if (count_threat == connect_k) { + /* if this is a threat, update the threat array */ + if (sequence >= (connect_k - place_p)) { + for (j = 0; j < len; j+=2) { + whites_marks[to_mark[j]][to_mark[j+1]] = window_id(x, y, i); + } + white_window_threat_array[x][y][i] = 1; + white_threat_count += 1; + } + } + + if (count_sequence == connect_k) { + + /* if this is the max sequence of the board, update the max_sequence value */ + if (sequence > max_white_sequence) { + max_white_sequence = sequence; + } + + /* if the sequence is greater than connect_k - place_p, set it equal to connect_k - place_p. + This prevents it from giving a sequence of 5 a higher score than a sequence of 4 in the default game. */ + if (sequence > (connect_k - place_p)) { + sequence = (connect_k - place_p); + } + + /* update the utility array values */ + white_window_sequence_array[x][y][i] = sequence * sequence; + white_window_sequence_count += white_window_sequence_array[x][y][i]; + } + + /* Do it all again if we are black. There must be a better way to do this */ + } else if (player == PIECE_BLACK) { + // We are recalculating this window's threat level. + // Start be taking this window's previous threat out of the sum + // and reset it to 0. + black_threat_count -= black_window_threat_array[x][y][i]; + black_window_threat_array[x][y][i] = 0; + + // Do the same for the sequence count. + black_window_sequence_count -= black_window_sequence_array[x][y][i]; + black_window_sequence_array[x][y][i] = 0; + + // step through the window. + for (dx = 0, dy = 0; dx < connect_k && dy < (int)connect_k; dx += ddx, dy += ddy) { + if (x + dx < 0 || y + dy < 0 || x + dx >= board_size || y + dy >= board_size) { + break; + } + // If this window was the one that marked this spot, unmark it so we can recheck. + if (blacks_marks[x + dx][y + dy] == window_id(x, y, i)) { + blacks_marks[x + dx][y + dy] = 0; + } + + if (piece_at(b, x + dx, y + dy) == PIECE_NONE) { + count_sequence++; + if (blacks_marks[x + dx][y + dy] == 0) { + count_threat++; + to_mark[len++] = x + dx; + to_mark[len++] = y + dy; + } + } else if (piece_at(b, x + dx, y + dy) == player) { + count_sequence++; + count_threat++; + sequence++; + } + } + + if (count_threat == connect_k) { + /* if this is a threat, update the threat array */ + if (sequence >= (connect_k - place_p)) { + for (j = 0; j < len; j+=2) { + blacks_marks[to_mark[j]][to_mark[j+1]] = window_id(x, y, i); + } + black_window_threat_array[x][y][i] = 1; + black_threat_count += 1; + } + } + + if (count_sequence == connect_k) { + + /* if this is the max sequence of the board, update the max_sequence value */ + if (sequence > max_black_sequence) { + max_black_sequence = sequence; + } + + /* if the sequence is greater than connect_k - place_p, set it equal to connect_k - place_p. + This prevents it from giving a sequence of 5 a higher score than a sequence of 4 in the default game. */ + if (sequence > (connect_k - place_p)) { + sequence = (connect_k - place_p); + } + + /* update the utility array values */ + black_window_sequence_array[x][y][i] = sequence * sequence; + black_window_sequence_count += black_window_sequence_array[x][y][i]; + } + } else { + g_debug("error in window_sequence(), unknown board turn."); + } +} + +int board_utility(const Board *b, PIECE player) +/* This returns the utility value of the board +It looks for a few things, first if the currently player is on their way to winning +(have enough moves left in given turn to win) it returns a high utility +second if there is a threat on this board from the other player, it gives a very low utility. +Third, if the board is going to force a win for the player, it gives a high utility. +If none of these are true, it adds up the utilities of all the windows and subtracts +the sum of the utilities of the other player times the defensive constant */ +{ + + int utility = 0; + utility_upper_bound = 2 * board_size * board_size * connect_k * connect_k; + + if (b->turn == PIECE_WHITE) { + if ((connect_k - max_white_sequence) <= (b->moves_left)) { + utility = utility_upper_bound; + } else if (black_threat_count) { + utility = -utility_upper_bound - black_threat_count; + } else if (white_threat_count > place_p) { + utility = utility_upper_bound - 1; + } else { + utility = white_window_sequence_count - black_window_sequence_count; + } + } else if (b->turn == PIECE_BLACK) { + if ((connect_k - max_black_sequence) <= (b->moves_left)) { + utility = utility_upper_bound; + } else if (white_threat_count) { + utility = -utility_upper_bound - white_threat_count; + } else if (black_threat_count > place_p) { + utility = utility_upper_bound - 1; + } else { + utility = black_window_sequence_count - white_window_sequence_count; + } + } else { + g_debug("error in board_utility(), unknown board turn."); + } + + if (b->turn != player) + utility = -utility; + + return utility; +} + +int board_update(const Board *b, PIECE player) +{ + /* scans the entire board and returns its utility */ + BCOORD x, y; + int i; + + clear_all(); + + for (y = 0; y < board_size; y++) { + for (x = 0; x < board_size; x++) { + for (i = 0; i < 4; i++) { + window_sequence(b, x, y, i, PIECE_WHITE); + window_sequence(b, x, y, i, PIECE_BLACK); + } + } + } + + return board_utility(b, player); +} + +int incremental_update(const Board *b, BCOORD x, BCOORD y, PIECE player) +/* only scans the windows that have been impacted by a new piece and returns the board's utility */ +{ + int dx, dy, ddx, ddy, i, counter; + int ddxs[] = {1, 0, 1, 1}; + int ddys[] = {0, 1, 1, -1}; + + max_black_sequence = 0; + max_white_sequence = 0; + + for (i = 0; i < 4; i++) { + + ddx = ddxs[i]; + ddy = ddys[i]; + + for (counter = 0, dx = ddx * -connect_k, dy = ddy * -connect_k; + counter < connect_k + 2; + counter ++, dx += ddx, dy += ddy) { + if (x + dx < 0 || y + dy < 0 || x + dx >= board_size || y + dy >= board_size) { + continue; + } + + window_sequence(b, x + dx, y + dy, i, PIECE_WHITE); + window_sequence(b, x + dx, y + dy, i, PIECE_BLACK); + } + } + + return board_utility(b, player); +} + +AIMoves *move_utilities(const Board *b) +{ + /* creates a list of possible moves based on the sequences utility function */ + AIMoves *moves = aimoves_new(); + AIMove move; + + moves->utility = board_update(b, b->turn); + + /* create a new board */ + Board *new_board; + new_board = board_new(); + + for (move.y = 0; move.y < board_size; move.y++) { + + /* bails out if ai_stop is true */ + if (ai_stop) + return moves; + + for (move.x = 0; move.x < board_size; move.x++) { + + if (piece_at(b, move.x, move.y) != PIECE_NONE) + continue; + + /* copy the board into the new board */ + board_copy(b, new_board); + /* Add the piece to the board */ + place_piece(new_board, move.x, move.y); + new_board->moves_left--; + /* find the utility for this new board */ + move.weight = incremental_update(new_board, move.x, move.y, new_board->turn); + + aimoves_add(moves, &move); + + /* undo what we did, so things are correct next time around */ + place_piece_type(new_board, move.x, move.y, PIECE_NONE); + new_board->moves_left++; + incremental_update(new_board, move.x, move.y, new_board->turn); + } + } + + if ((b->turn == PIECE_WHITE && black_threat_count) || (b->turn == PIECE_BLACK && white_threat_count)) { + aimoves_sort(moves); + aimoves_crop(moves, 1); + } + + board_free(new_board); + + return moves; +} + +AIMoves *ai_sequences(const Board *b) +{ + AIMoves *moves = move_utilities(b); + + return moves; +}
sequences.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: mesh.c =================================================================== --- mesh.c (nonexistent) +++ mesh.c (revision 4) @@ -0,0 +1,131 @@ + +/* + +connectk -- a program to play the connect-k family of games +Copyright (C) 2007 Jeff Deitch + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + +*/ + +#include "config.h" +#include +#include "../shared.h" + +int cur_player_weight = 50; +int opp_player_weight = 500; +int mesh_array[19][19]; + +int get_mesh_value(int x, int y) { + if (x < 0 || y < 0 || x >= board_size || y >= board_size) { + /* out of bounds */ + return 0; + } else { + return mesh_array[x][y]; + } +} + +int stone_weight(int x, int y) { + if (piece_at(board, x, y) == board->turn) { + return cur_player_weight; + } else if (piece_at(board, x, y) == other_player(board->turn)) { + return opp_player_weight; + } else { + return 0; + } +} + +int surrounding_weight(int x, int y) { + + int weight = 0; + int n = 4; // number of tiles in each of the 8 radials that contribute to the weight. + + int dx, dy, ddx, ddy, i; + int ddxs[] = {1, 0, 1, 1}; + int ddys[] = {0, 1, 1, -1}; + + for (i = 0; i < 4; i++) { + + ddx = ddxs[i]; + ddy = ddys[i]; + + for (dx = -(ddx * n), dy = -(ddy * n); dx <= n && dy <= n; dx += ddx, dy += ddy) { + if (dx == 0 && dy == 0) { + continue; + } else { + weight += get_mesh_value(x + dx, y + dy); + } + } + } + + return weight / (8 * n); +} + +AIMoves *ai_mesh(const Board *b) +/* imagine the board is elastic and that each stone has a weight. The current players stones have +a different weight than the opposite players stones. Placing a stone on the board creates a depression, +and the more stones in an area, the deeper the depression. This ai chooses the lowest, unplayed tile for +the next move. The idea is to create clumps of stones. */ +{ + AIMove move; + AIMoves *moves = aimoves_new(); + + int i, x, y; + int iterations = 10; + int max_weight = 0; + + /* set all values to 0 */ + for (x = 0; x < board_size; x++) { + for (y = 0; y < board_size; y++) { + mesh_array[x][y] = 0; + } + } + + /* iteratively find the depth of each tile */ + for (i = 0; i < iterations; i++) { + for (x = 0; x < board_size; x++) { + for (y = 0; y < board_size; y++) { + mesh_array[x][y] = stone_weight(x, y) + surrounding_weight(x, y); + } + } + } + + /* find the max weight (i.e. the lowest spot on the board) */ + for (x = 0; x < board_size; x++) { + for (y = 0; y < board_size; y++) { + if (piece_at(b, x, y) == PIECE_NONE) { + move.weight = mesh_array[x][y]; + if (move.weight > max_weight) + max_weight = move.weight; + move.x = x; + move.y = y; + aimoves_add(moves, &move); + } + } + } + + /* if the board is empty, play in the middle */ + if (max_weight == 0) { + move.x = board_size / 2; + move.y = board_size / 2; + move.weight = 1; + aimoves_add(moves, &move); + } + + moves->utility = max_weight; + + /* return the array */ + return moves; +}
mesh.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.