# # othello.py # # 2007/08/01 18:29 othello project start # 2007/08/02 0:53 change 1dim_array # 2007/08/03 0:44 computer thinking algorithm # 2007/08/06 3:38 AI program start # 2007/08/06 7:09 Black AI only??? # # ABCDEFGH # 1 # 2 # ... # 8 board =[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] BLANK = 0 WHITE = 1 BLACK = 2 BOARD_SIZE = 8 black_num = 2 white_num = 2 MY_TURN = 1 ENEMY_TURN = -1 print len(board) # # print board # def print_board(board): print " a b c d e f g h " print " 0 1 2 3 4 5 6 7 " for y in range(BOARD_SIZE): print y+1,y, for x in range(BOARD_SIZE): peace = board[x+(y*BOARD_SIZE)] if peace == BLANK: print "-", if peace == WHITE: print "O", if peace == BLACK: print "*", print print # # set piece # def set_piece(board, x, y, piece): board[x+(y*8)] = piece def reverse(board, PIECE, x, y, dir_x, dir_y): count = 0 c_x = x c_y = y tmp_board = board[:] while 1: c_x = c_x + dir_x c_y = c_y + dir_y #board out end if (c_x < 0) or (c_x >= BOARD_SIZE) or (c_y < 0) or (c_y >= BOARD_SIZE): ###print "NG c_x c_y:", c_x, c_y count_board = (0, board) return count_board ###print "OK c_x c_y:", c_x, c_y check_point = c_x+(c_y*BOARD_SIZE) check_piece = tmp_board[check_point] #print check_point #BLANK end if check_piece == BLANK: count_board = (0, board) return count_board #PIECE end if check_piece == PIECE: if count > 0 : tmp_board[x+(y*BOARD_SIZE)] = PIECE board = tmp_board[:] count_board = (count, board) return count_board tmp_board[check_point] = PIECE count += 1 def check_blank(board, x, y): check_piece = board[x+(y*BOARD_SIZE)] if check_piece == BLANK: return 1 return 0 def all_reverse(board, PIECE, x, y): count = 0 tmp_count = 0 if check_blank(board, x, y) == 0: count_board = (count, board) return count_board tmp_count, board = reverse(board, PIECE, x, y, 1, 0) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y,-1, 0) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y, 0, 1) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y, 0,-1) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y, 1, 1) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y,-1, 1) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y, 1,-1) count += tmp_count tmp_count, board = reverse(board, PIECE, x, y,-1,-1) count += tmp_count count_board = (count, board) return count_board def possible_point(board, PIECE): count = 0 stack = [] tmp_board = board[:] for x in range(BOARD_SIZE): for y in range(BOARD_SIZE): count, tmp_board = all_reverse(board, PIECE, x, y) if count > 0 : stack.append([x,y,count]) #print "x y count:", x,y,count return stack def depth_search(board, PIECE, depth): replica = board[:] pp = possible_point(replica, PIECE) if depth == 0: pack_value = (len(pp), 0, 0) return pack_value pp_num = 0 max = -999 max_x = 0 max_y = 0 if len(pp) == 0: #PIECE is pass if PIECE == BLACK: pp_num,trash,trash = depth_search(replica, WHITE, depth-1) else: pp_num,trash,trash = depth_search(replica, BLACK, depth-1) pp_num = pp_num * -1 if pp_num > max: max = pp_num while len(pp) > 0: x, y, count = pp.pop() ans, replica = all_reverse(replica, PIECE, x, y)#my turn if PIECE == BLACK: pp_num, trash, trash = depth_search(replica, WHITE, depth-1) else: pp_num, trash, trash = depth_search(replica, BLACK, depth-1) replica = board[:] pp_num = pp_num * -1 if pp_num > max: max = pp_num max_x = x max_y = y pack_value = (max, max_x, max_y) return pack_value def last_search(COUNT, board, PIECE, depth): if depth == 0: pack_value = (board.count(COUNT), 0, 0) #print "board.count(PIECE):", board.count(PIECE) return pack_value replica = board[:] pp = possible_point(replica, PIECE) pp_num = 0 max = -999 max_x = 0 max_y = 0 if len(pp) == 0: #PIECE is pass if PIECE == BLACK: pp_num,trash,trash = last_search(COUNT, replica, WHITE, depth-1) else: pp_num,trash,trash = last_search(COUNT, replica, BLACK, depth-1) pp_num = pp_num * -1 if pp_num > max: max = pp_num while len(pp) > 0: x, y, count = pp.pop() ans, replica = all_reverse(replica, PIECE, x, y)#my turn if PIECE == BLACK: pp_num,trash,trash = last_search(COUNT, replica, WHITE, depth-1) else: pp_num,trash,trash = last_search(COUNT, replica, BLACK, depth-1) replica = board[:] pp_num = pp_num * -1 if pp_num > max: max = pp_num max_x = x max_y = y pack_value = (max, max_x, max_y) return pack_value max, x, y = depth_search(board, BLACK, 5) print "max, x, y:", max, x, y print "start othello" print_board(board) x, y = 0, 0 turn_num = 64 - 4 #8x8 - start stone while x < BOARD_SIZE or y < BOARD_SIZE: ans = 0 pass_flg = 0 while ans == 0: #print "BLACK turn" pp = possible_point(board, BLACK) if len(pp) == 0: print "BLACK pass" pass_flg += 1 break #print pp #x = input("enter x: ") #y = input("enter y: ") #x, y, count = pp.pop() if turn_num > 6: x, y, count = pp.pop() max, x, y = depth_search(board, BLACK, 2) else: print "last_search:" print_board(board) max, x, y = last_search(BLACK, board, BLACK, 6) print "max, x, y:", max, x, y if max == -999: x, y, count = pp.pop() ans, board = all_reverse(board, BLACK, x, y) #print ans turn_num -= 1 print_board(board) ans = 0 while ans == 0: #print "WHITE turn" pp = possible_point(board, WHITE) if len(pp) == 0: print "WHITE pass" pass_flg += 1 break #print pp x = input("enter x: ") y = input("enter y: ") #if turn_num > 10: # max, x, y = depth_search(board, WHITE, 2) #else: # #print "last_search:" # print_board(board) # max, x, y = last_search(WHITE, board, WHITE, 10) #if max == -999: # x, y, count = pp.pop() #print "max, x, y:", max, x, y ans, board = all_reverse(board, WHITE, x, y) #print ans turn_num -= 1 print_board(board) if pass_flg >= 2: break print turn_num, "w:", board.count(WHITE), "b:", board.count(BLACK) #board = all_reverse(board, BLACK, 2, 3) print "end game" print turn_num, "w:", board.count(WHITE), "b:", board.count(BLACK) print_board(board)