Subversion Repositories connect-6

/connect-6/trunk/BUILD_SCC/synth_src/search.cpp File deleted

connect-6/trunk/BUILD_SCC/synth_src/search.cpp Property changes : Deleted: svn:executable ## -1 +0,0 ## -* \ No newline at end of property Index: connect-6/trunk/BUILD_SCC/synth_src/search.c =================================================================== --- connect-6/trunk/BUILD_SCC/synth_src/search.c (nonexistent) +++ connect-6/trunk/BUILD_SCC/synth_src/search.c (revision 9) @@ -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; +}

connect-6/trunk/BUILD_SCC/synth_src/search.c Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: connect-6/trunk/BUILD_SCC/synth_src/threats.cpp =================================================================== --- connect-6/trunk/BUILD_SCC/synth_src/threats.cpp (revision 10) +++ connect-6/trunk/BUILD_SCC/synth_src/threats.cpp (revision 9) @@ -348,7 +348,7 @@ #pragma fifo_length pico_stream_output_queue 800 #pragma bandwidth pico_stream_input_queue 1 #pragma bandwidth pico_stream_output_queue 1 -/*AIMoves*/int ai_threats(Board *board,AIMoves *moves,unsigned int *index) +/*AIMoves*/int ai_threats(Board *board,AIMove *move) { //#pragma read_write_ports board.data combined 2 //#pragma internal_blockram board @@ -369,12 +369,12 @@ #pragma internal_blockram bwrite //#pragma multi_buffer bwrite 22 //#pragma no_memory_analysis b - ///*static*/ AIMoves moves;//={0,0,0,{{0,0,0}}}; + /*static*/ AIMoves moves;//={0,0,0,{{0,0,0}}}; //#pragma read_write_ports moves.data combined 3 #pragma internal_blockram moves //#pragma no_memory_analysis moves - moves->len=0; + moves.len=0; //AIMoves moves; AIWEIGHT u_sum = 0; int i; @@ -523,17 +523,16 @@ //PICO_finalize_PPA(id); /*---------------------------------------------------------------------------*/ //board_copy(&b,&b_marks); - //unsigned int index[max_size]={0}; + unsigned int index[max_size]={0}; #pragma bitsize index 9 #pragma internal_fast index AIMoves moves1; - moves1.len=0; #pragma internal_blockram moves1 - /*moves = */ ai_marks(&bwrite, PIECE_THREAT(1),&moves1); + /*moves = */ ai_marks(&bwrite, PIECE_THREAT(1),&moves); //test(ready); - streamsort(moves,index); - moves1.utility = u_sum; - moves->utility = u_sum; + streamsort(&moves1,&index[0]); + //moves1.utility = u_sum; + //moves.utility = u_sum; /*---------------------------- rewritten for hardware ----------------------------*/ @@ -540,11 +539,11 @@ //if (!aimoves_choose(&moves1, move)) // return 0; //else return 1; - //int ret_val; - //ret_val=aimoves_choose(&moves1, move,&index[0]); - //if (!ret_val) - // return 0; - //else return 1; + int ret_val; + ret_val=aimoves_choose(&moves1, move,&index[0]); + if (!ret_val) + return 0; + else return 1; /*---------------------------- end rewritten for hardware ----------------------------*/

/connect-6/trunk/BUILD_SCC/synth_src/connect6_synth.cpp

/connect-6/trunk/BUILD_SCC/synth_src/shared.h

/connect-6/trunk/BUILD_SCC/synth_src/util.cpp

/connect-6/trunk/BUILD_SCC/Makefile