[Londerings-commits] CVS: go/simple_go proof.c, NONE, 1.1 proof.h, NONE, 1.1 Makefile, 1.9, 1.10 al
Brought to you by:
aloril
Menu
▾
▴
[Londerings-commits] CVS: go/simple_go proof.c, NONE, 1.1 proof.h, NONE, 1.1 Makefile, 1.9, 1.10 alphabeta.c, 1.6, 1.7 alphabeta.h, 1.4, 1.5 c_boardmodule.c, 1.25, 1.26 montecarlo.c, 1.32, 1.33 montecarlo.h, 1.28, 1.29 random_uct.c, 1.4, 1.5 test_c_board.py, 1.48, 1.49
|
From: Aloril <al...@us...> - 2006-11-18 17:58:24
|
Update of /cvsroot/londerings/go/simple_go In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv20149 Modified Files: Makefile alphabeta.c alphabeta.h c_boardmodule.c montecarlo.c montecarlo.h random_uct.c test_c_board.py Added Files: proof.c proof.h Log Message: move ordering added to alpha-beta; proof verification code --- NEW FILE: proof.c --- #include "alphabeta.h" #include "montecarlo.h" #define MAX_DEPTH 60 void show_error(int color, int proof_color, char *msg) { simple_showboard(stdout); printf("\n\n"); dump_stack(); mprintf("%o%s: %C %C\n", msg, color, proof_color); } int find_proof_recursive(int color, int proof_color, int ply, SearchInfo *info) { int move_list[MAX_DEPTH + 1]; int move_list_depth; int depth, score; int result; int i, move; if(ply >= MAX_DEPTH) { show_error(color, proof_color, "too deep"); return FALSE; } if(get_pass_count() >= 2) { double score_d = score_board_color(color); int ok1 = score_d > 0; int ok2 = color == proof_color; if(ok1 == ok2) { return TRUE; } show_error(color, proof_color, "wrong final score"); return FALSE; } if(color==proof_color) { depth = 1; for(depth = 1; depth <= MAX_DEPTH; depth++) { score = alpha_beta_search_recursive(PASS_MOVE, color, depth, -1, 1, move_list, &move_list_depth, ply, info->hash_history); if(score) { break; } } if(score <= 0) { show_error(color, proof_color, "wrong score from search"); return FALSE; } move = move_list[0]; if(!trymove_superko(move, color, ply, info->hash_history)) { mprintf("%omove: %1m\n", move); show_error(color, proof_color, "failed to make search move"); return FALSE; } info->count++; result = find_proof_recursive(OTHER_COLOR(color), proof_color, ply + 1, info); popgo(); return result; } else { for(i = 0; i < info->move_list_max; i++) { move = info->move_list[i]; if(trymove_superko(move, color, ply, info->hash_history)) { info->count++; result = find_proof_recursive(OTHER_COLOR(color), proof_color, ply + 1, info); popgo(); if(!result) { return FALSE; } } } return TRUE; } } int find_proof(int color, int proof_color) { int result; SearchInfo info; info.move_list_max = list_board_and_pass(info.move_list); info.count = 0; result = find_proof_recursive(color, proof_color, 0, &info); printf("Count: %lli\n", info.count); return result; } --- NEW FILE: proof.h --- #ifndef PROOF_H int find_proof(int color, int proof_color); #endif Index: Makefile =================================================================== RCS file: /cvsroot/londerings/go/simple_go/Makefile,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -r1.9 -r1.10 *** Makefile 17 Nov 2006 03:57:37 -0000 1.9 --- Makefile 18 Nov 2006 17:58:05 -0000 1.10 *************** *** 9,14 **** gcc -g -O2 -Wall -fPIC ${PYTHON_INCLUDE_DIR} -c cpatternsmodule.c ! c_boardmodule.so: c_boardmodule.o montecarlo.o alphabeta.o patterns.o random_uct.o weakbot.o ! gcc -g -shared -o c_boardmodule.so patterns.o montecarlo.o alphabeta.o random_uct.o weakbot.o c_boardmodule.o gnugo/engine/libboard.a gnugo/engine/libengine.a gnugo/sgf/libsgf.a gnugo/utils/libutils.a -lncurses -lm montecarlo.o: montecarlo.c montecarlo.h patterns.h c_board.h weakbot.h --- 9,14 ---- gcc -g -O2 -Wall -fPIC ${PYTHON_INCLUDE_DIR} -c cpatternsmodule.c ! c_boardmodule.so: c_boardmodule.o montecarlo.o alphabeta.o patterns.o random_uct.o weakbot.o proof.o ! gcc -g -shared -o c_boardmodule.so patterns.o montecarlo.o alphabeta.o random_uct.o weakbot.o proof.o c_boardmodule.o gnugo/engine/libboard.a gnugo/engine/libengine.a gnugo/sgf/libsgf.a gnugo/utils/libutils.a -lncurses -lm montecarlo.o: montecarlo.c montecarlo.h patterns.h c_board.h weakbot.h *************** *** 24,27 **** --- 24,30 ---- gcc -g -O2 -Wall -Ignugo -Ignugo/utils -Ignugo/engine -Ignugo/sgf -c alphabeta.c + proof.o: proof.c proof.h alphabeta.h montecarlo.h + gcc -g -O2 -Wall -Ignugo -Ignugo/utils -Ignugo/engine -Ignugo/sgf -c proof.c + patterns.o: patterns.c patterns.h gcc -g -O2 -Wall -Ignugo -Ignugo/utils -Ignugo/engine -Ignugo/sgf -c patterns.c Index: alphabeta.c =================================================================== RCS file: /cvsroot/londerings/go/simple_go/alphabeta.c,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -r1.6 -r1.7 *** alphabeta.c 17 Nov 2006 03:57:37 -0000 1.6 --- alphabeta.c 18 Nov 2006 17:58:05 -0000 1.7 *************** *** 10,13 **** --- 10,125 ---- enum {resultAccurate, resultAlpha, resultBeta, resultUnkown}; + typedef struct + { + int state; + int seen_moves[FLAG_BOARDSIZE]; + int hash_move; + int atari_count; + int atari_list[MAX_BOARD * MAX_BOARD + 1]; + int history_ind; + } MoveInfo; + + #define STATE_HASH_MOVE 0 + #define STATE_ATARI_MOVES 1 + #define STATE_PLACE_STONE 2 + #define STATE_DONE 3 + + int history_size = 0; + int history_max; + int history_table[BOARDMAX]; + + void initialize_history() + { + history_size = board_size; + history_max = 0; + #define M(i, j) history_table[history_max++] = POS(i, j); + switch(board_size) { + case 3: + M(1, 1); + M(1, 0); M(2, 1); M(1, 2); M(0, 1); + M(0, 0); M(2, 0); M(2, 2); M(0, 2); + break; + case 4: + M(2, 1); M(1, 2); M(2, 2); M(1, 1); + M(1, 0); M(2, 3); M(0, 1); M(3, 2); + M(0, 2); M(1, 3); M(3, 1); M(2, 0); + M(0, 0); M(3, 3); M(3, 0); M(0, 3); + break; + case 5: + M(2, 2); + M(2, 1); M(3, 2); M(2, 3); M(1, 2); + M(1, 1); M(3, 1); M(3, 3); M(1, 3); + M(2, 0); M(4, 2); M(2, 4); M(0, 2); + M(1, 0); M(3, 0); M(4, 1); M(4, 3); M(3, 4); M(1, 4); M(0, 3); M(0, 1); + M(0, 0); M(4, 0); M(4, 4); M(0, 4); + break; + default: + ASSERT1(FALSE, NO_MOVE); // not yet defined for other sizes + } + history_table[history_max++] = PASS_MOVE; + } + + void init_move_info(MoveInfo *minfo, int hash_move) + { + memset(minfo->seen_moves, 0, sizeof(minfo->seen_moves)); + minfo->history_ind = 0; + minfo->atari_count = -1; + if(hash_move >= 0) { + minfo->state = STATE_HASH_MOVE; + minfo->hash_move = hash_move; + } else { + minfo->state = STATE_ATARI_MOVES; + } + } + + int get_next_move(MoveInfo *minfo) + { + int move = -1; + while(move < 0 && minfo->state != STATE_DONE) { + switch(minfo->state) { + case STATE_HASH_MOVE: + move = minfo->hash_move; + minfo->state = STATE_ATARI_MOVES; + break; + case STATE_ATARI_MOVES: + if(minfo->atari_count < 0) { + double available_score[MAX_BOARD * MAX_BOARD + 1]; + minfo->atari_count = get_random_1_tactic_moves(minfo->atari_list, available_score); + } + if(minfo->atari_count) { + move = -minfo->atari_list[--minfo->atari_count]; + if(GET_FLAG(minfo->seen_moves, move)) { + move = -1; + } + } else { + move = -1; + minfo->state = STATE_PLACE_STONE; + } + break; + case STATE_PLACE_STONE: + if(history_size != board_size) { + initialize_history(); + } + // start from middle and spiral out + while(TRUE) { + if(minfo->history_ind >= history_max) { + minfo->state = STATE_DONE; + move = -1; + break; + } + move = history_table[minfo->history_ind++]; + if(!GET_FLAG(minfo->seen_moves, move)) { + break; + } + } + break; + } + } + if(move >= 0) { + SET_FLAG(minfo->seen_moves, move); + } + return move; + } + int find_alpha_beta_position(int pos, int color, int depth, int alpha, int beta, int *best_score, int *best_move) { *************** *** 51,55 **** } ! int alpha_beta_search_recursive(int pos, int color, int depth, int alpha, int beta, int *pv, int *pv_depth, int ply, Hash_data *hash_history) --- 163,183 ---- } ! int trymove_superko(int move, int color, int ply, Hash_data *hash_history) ! { ! int ok; ! ok = trymove(move, color, NULL, NO_MOVE); ! if(ok && move!=PASS_MOVE) { ! int k; ! for(k = 0; k < ply; k++) { ! if(hashdata_is_equal(hash_history[k], board_hash)) { ! ok = FALSE; ! popgo(); ! break; ! } ! } ! } ! hash_history[ply] = board_hash; ! return ok; ! } int alpha_beta_search_recursive(int pos, int color, int depth, int alpha, int beta, int *pv, int *pv_depth, int ply, Hash_data *hash_history) *************** *** 64,69 **** int move_list[depth], move_list_depth; int hash_type = resultAlpha; *pv_depth = 0; ! pv[0] = PASS_MOVE; if(pos) { if(board[pos]==EMPTY) { --- 192,202 ---- int move_list[depth], move_list_depth; int hash_type = resultAlpha; + MoveInfo minfo; *pv_depth = 0; ! pv[0] = -1; ! hash_type = find_alpha_beta_position(pos, color, depth, alpha, beta, &best_score, &pv[0]); ! if(hash_type != resultUnkown) { ! return best_score; ! } if(pos) { if(board[pos]==EMPTY) { *************** *** 84,141 **** return 0; } ! hash_type = find_alpha_beta_position(pos, color, depth, alpha, beta, &best_score, &pv[0]); ! if(hash_type != resultUnkown) { ! return best_score; ! } hash_type = resultAlpha; best_score = WORST_SCORE; other_color = OTHER_COLOR(color); ! for (i = 0; i <= board_size; i++) { ! for (j = 0; j < board_size; j++) { ! if(i==board_size) { ! if(j) { ! break; ! } ! move = PASS_MOVE; ! } else { ! move = POS(i, j); ! } ! int ok; ! ok = trymove(move, color, NULL, NO_MOVE); ! counter++; ! if(counter & 0xFFFF) {get_trymove_counter2();} ! if(ok && move!=PASS_MOVE) { ! int k; ! for(k = 0; k < ply; k++) { ! if(hashdata_is_equal(hash_history[k], board_hash)) { ! ok = FALSE; ! popgo(); break; } } } - if(ok) { - hash_history[ply] = board_hash; - score = alpha_beta_search_recursive(pos, other_color, depth-1, -beta, -alpha, move_list, &move_list_depth, ply + 1, hash_history); - popgo(); - score = -score; - if(score > best_score) { - best_score = score; - pv[0] = move; - memcpy(pv+1, move_list, sizeof(move_list[0]) * move_list_depth); - *pv_depth = 1 + move_list_depth; - if(score >= alpha) { - hash_type = resultAccurate; - alpha = score; - if(score >= beta) { - i = j = board_size + 1; // jump out all loops - hash_type = resultBeta; - break; - } - } - } - } } } if(best_score==WORST_SCORE) { best_score = 0; --- 217,255 ---- return 0; } ! init_move_info(&minfo, pv[0]); hash_type = resultAlpha; best_score = WORST_SCORE; other_color = OTHER_COLOR(color); ! while(TRUE) { ! move = get_next_move(&minfo); ! if(move < 0) { ! break; ! } ! counter++; ! if(counter & 0xFFFF) {get_trymove_counter2();} ! if(trymove_superko(move, color, ply, hash_history)) { ! score = alpha_beta_search_recursive(pos, other_color, depth-1, -beta, -alpha, move_list, &move_list_depth, ply + 1, hash_history); ! popgo(); ! score = -score; ! if(score > best_score) { ! best_score = score; ! pv[0] = move; ! memcpy(pv+1, move_list, sizeof(move_list[0]) * move_list_depth); ! *pv_depth = 1 + move_list_depth; ! if(score >= alpha) { ! hash_type = resultAccurate; ! alpha = score; ! if(score >= beta) { ! i = j = board_size + 1; // jump out all loops ! hash_type = resultBeta; break; } } } } } + if(pv[0]==-1) { + pv[0] = PASS_MOVE; + } if(best_score==WORST_SCORE) { best_score = 0; Index: alphabeta.h =================================================================== RCS file: /cvsroot/londerings/go/simple_go/alphabeta.h,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -r1.4 -r1.5 *** alphabeta.h 17 Nov 2006 03:57:37 -0000 1.4 --- alphabeta.h 18 Nov 2006 17:58:05 -0000 1.5 *************** *** 6,11 **** --- 6,13 ---- #define RAND_FACTOR 1000000 + int alpha_beta_search_recursive(int pos, int color, int depth, int alpha, int beta, int *pv, int *pv_depth, int ply, Hash_data *hash_history); int alpha_beta_search(int pos, int color, int depth, int alpha, int beta, int *pv, int *pv_depth); int alpha_beta_search_random(int pos, int color, int depth, int alpha, int beta, int limit); + int trymove_superko(int move, int color, int ply, Hash_data *hash_history); #endif // ALPHABETA_H Index: c_boardmodule.c =================================================================== RCS file: /cvsroot/londerings/go/simple_go/c_boardmodule.c,v retrieving revision 1.25 retrieving revision 1.26 diff -C2 -r1.25 -r1.26 *** c_boardmodule.c 17 Nov 2006 03:57:38 -0000 1.25 --- c_boardmodule.c 18 Nov 2006 17:58:05 -0000 1.26 *************** *** 5,8 **** --- 5,9 ---- #include "patterns.h" #include "weakbot.h" + #include "proof.h" #define PYTHON_POS2C(i, j) POS(board_size - j, i-1) *************** *** 197,200 **** --- 198,211 ---- } + static PyObject *cboard_find_proof(PyObject *self, PyObject *args) + { + int color, proof_color, result; + if(!PyArg_ParseTuple(args, "ii", &color, &proof_color)) { + return NULL; + } + result = find_proof(color, proof_color); + return PyInt_FromLong(result); + } + static PyObject *cboard_alpha_beta_search_random(PyObject *self, PyObject *args) *************** *** 584,587 **** --- 595,599 ---- {"alpha_beta_search", cboard_alpha_beta_search, METH_VARARGS}, {"alpha_beta_search_random", cboard_alpha_beta_search_random, METH_VARARGS}, + {"find_proof", cboard_find_proof, METH_VARARGS}, {"get_trymove_counter", cboard_get_trymove_counter, METH_VARARGS}, {"simple_showboard", cboard_simple_showboard, METH_VARARGS}, Index: montecarlo.c =================================================================== RCS file: /cvsroot/londerings/go/simple_go/montecarlo.c,v retrieving revision 1.32 retrieving revision 1.33 diff -C2 -r1.32 -r1.33 *** montecarlo.c 17 Nov 2006 03:57:38 -0000 1.32 --- montecarlo.c 18 Nov 2006 17:58:05 -0000 1.33 *************** *** 2629,2639 **** } - typedef struct { - Hash_data hash_history[MAX_MONTE_CARLO_STACK]; - int move_list[MAX_BOARD * MAX_BOARD + 1]; - int move_list_max; - int block_color; - } UctSearchInfo; - #if 0 void show_current(char *msg, int color, double win_score, double lost_score) --- 2629,2632 ---- *************** *** 2650,2654 **** #endif ! void score_final_position(UctSearchInfo *info, int color, double *win_result, double *lost_result) { double score = uct_score(capture_goal, info->block_color, color); --- 2643,2647 ---- #endif ! void score_final_position(SearchInfo *info, int color, double *win_result, double *lost_result) { double score = uct_score(capture_goal, info->block_color, color); *************** *** 2663,2667 **** } ! void score_with_random_game(UctSearchInfo *info, int color, double *win_result, double *lost_result, int depth) { int white_length, black_length; --- 2656,2660 ---- } ! void score_with_random_game(SearchInfo *info, int color, double *win_result, double *lost_result, int depth) { int white_length, black_length; *************** *** 2704,2708 **** } ! void uct_game_recursive(UctSearchInfo *info, int color, int depth, double *win_result, double *lost_result) { double win_count, lost_count; --- 2697,2701 ---- } ! void uct_game_recursive(SearchInfo *info, int color, int depth, double *win_result, double *lost_result) { double win_count, lost_count; *************** *** 2804,2808 **** void uct_game_normal(int block_pos, int color) { ! UctSearchInfo info; double win_result, lost_result; info.block_color = GRAY; --- 2797,2801 ---- void uct_game_normal(int block_pos, int color) { ! SearchInfo info; double win_result, lost_result; info.block_color = GRAY; Index: montecarlo.h =================================================================== RCS file: /cvsroot/londerings/go/simple_go/montecarlo.h,v retrieving revision 1.28 retrieving revision 1.29 diff -C2 -r1.28 -r1.29 *** montecarlo.h 17 Nov 2006 03:57:38 -0000 1.28 --- montecarlo.h 18 Nov 2006 17:58:05 -0000 1.29 *************** *** 124,127 **** --- 124,141 ---- void random_uct_game(int color); long long get_trymove_counter2(); + int list_board_and_pass(int *move_list); + + typedef struct { + Hash_data hash_history[MAX_MONTE_CARLO_STACK]; + int move_list[MAX_BOARD * MAX_BOARD + 1]; + int move_list_max; + int block_color; + long long count; + } SearchInfo; + + #define SET_FLAG(array, pos) (array)[(pos)>>5] = ((array)[(pos)>>5] | (1 << ((pos) & 31))) + #define CLEAR_FLAG(array, pos) (array)[(pos)>>5] = ((array)[(pos)>>5] & (~(1 << ((pos) & 31)))) + #define GET_FLAG(array, pos) ((array)[(pos)>>5] & (1 << ((pos) & 31))) + int get_random_1_tactic_moves(int *available, double *available_score); #endif // MONTECARLO_H Index: random_uct.c =================================================================== RCS file: /cvsroot/londerings/go/simple_go/random_uct.c,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -r1.4 -r1.5 *** random_uct.c 7 Sep 2006 04:27:35 -0000 1.4 --- random_uct.c 18 Nov 2006 17:58:05 -0000 1.5 *************** *** 6,12 **** #define DUMP_SGF FALSE - #define SET_FLAG(array, pos) (array)[(pos)>>5] = ((array)[(pos)>>5] | (1 << ((pos) & 31))) - #define CLEAR_FLAG(array, pos) (array)[(pos)>>5] = ((array)[(pos)>>5] & (~(1 << ((pos) & 31)))) - #define GET_FLAG(array, pos) ((array)[(pos)>>5] & (1 << ((pos) & 31))) int black_available_moves[MAX_AVAILABLE_MOVES]; int black_available_moves_count = 0; --- 6,9 ---- Index: test_c_board.py =================================================================== RCS file: /cvsroot/londerings/go/simple_go/test_c_board.py,v retrieving revision 1.48 retrieving revision 1.49 diff -C2 -r1.48 -r1.49 *** test_c_board.py 17 Nov 2006 03:57:38 -0000 1.48 --- test_c_board.py 18 Nov 2006 17:58:05 -0000 1.49 *************** *** 288,291 **** --- 288,318 ---- print "-"*60 + def report_iteration(limit, undo_count0, depth, score, nodes0, t0, pv): + t1 = time.time() + nodes1 = c_board.get_trymove_counter() + moves = [] + t_used = t1-t0 + t_used = round(t_used, int(-math.log10(t_used) + 2)) + nodes_s = (nodes1-nodes0)/(t1-t0) + if nodes_s >= 1000000: + nodes_s = "%sM" % round(nodes_s/1000000., 1) + else: + nodes_s = "%sK" % round(nodes_s/1000.) + if nodes_s >= 10000: + nodes_s = nodes_s.replace(".0", "") + if limit=="": + limit_s = "" + else: + limit_s = str(limit/1000000.) + limit_s = limit_s.replace(".0", "") + pv_s = move_list_as_string(pv) + s = "%-6s %-4s %-5s %-6s %-11s %-7s %s %s" % (limit_s, undo_count0, depth, score, nodes1-nodes0, t_used, nodes_s, pv_s) + fp = open("t.log", "a") + fp.write(s + "\n") + fp.close() + print s + return s + + def test_c_alpha_beta(name = "kgs/simple_ladders2.sgf", pos_str = "C3", depth = 1, seed = 1, undo_count = 0, limit = 0, print_pos = True, random=True): c_board.set_random_seed(seed) *************** *** 316,339 **** else: score, pv = c_board.alpha_beta_search(pos, g.c_color(), depth, -1, 1) ! t1 = time.time() ! nodes1 = c_board.get_trymove_counter() ! moves = [] ! t_used = t1-t0 ! t_used = round(t_used, int(-math.log10(t_used) + 2)) ! nodes_s = (nodes1-nodes0)/(t1-t0) ! if nodes_s >= 1000000: ! nodes_s = "%sM" % round(nodes_s/1000000., 1) ! else: ! nodes_s = "%sK" % round(nodes_s/1000.) ! if nodes_s >= 10000: ! nodes_s = nodes_s.replace(".0", "") ! limit_s = str(limit/1000000.) ! limit_s = limit_s.replace(".0", "") ! pv_s = move_list_as_string(pv) ! s = "%-6s %-4s %-5s %-6s %-9s %-7s %s %s" % (limit_s, undo_count0, depth, score, nodes1-nodes0, t_used, nodes_s, pv_s) ! fp = open("t.log", "a") ! fp.write(s + "\n") ! fp.close() ! print s return s, score --- 343,347 ---- else: score, pv = c_board.alpha_beta_search(pos, g.c_color(), depth, -1, 1) ! s = report_iteration(limit, undo_count0, depth, score, nodes0, t0, pv) return s, score *************** *** 345,355 **** --- 353,369 ---- def test_ab_score(name): + nodes0 = c_board.get_trymove_counter() + t0 = time.time() for depth in range(1, 40+1): s, score = test_c_alpha_beta(name, pos_str="", random=False, depth=depth, print_pos = False) if score: break + report_iteration("", "", "", "", nodes0, t0, []) def test_ab_score_undo(name): + c_board.clear_result_table() undo_count = 0 + nodes0 = c_board.get_trymove_counter() + t0 = time.time() while True: g = load_sgf.load_file(name) *************** *** 367,375 **** print "Initial length: %i" % len(g.move_history) print ! c_board.clear_result_table() test_ab_score(g) undo_count = undo_count + 1 if not g.move_history: break def test_ab(limit, seed=1, depth=7, undo_count=7): --- 381,393 ---- print "Initial length: %i" % len(g.move_history) print ! #c_board.clear_result_table() test_ab_score(g) undo_count = undo_count + 1 if not g.move_history: break + #if len(g.move_history) <= 20: + # break + print "All undo's done:" + report_iteration("", "", "", "", nodes0, t0, []) def test_ab(limit, seed=1, depth=7, undo_count=7): |