最初に #
今回はオセロをビットボードで作成したので紹介したいと思います．参考にさせてもらったサイトのコードをJavaで書いただけであり，コードの詳細やAIのアルゴリズムについては他のサイトにわかりやすい説明がありますので簡単にコードのみ載せたいと思います．
自分は大学の授業で制約があった為，変な書き方をしていることがあるかもしれません．いい感じに書き換えてください．
ボードの空きマスが少なくなると完全探索もするので普通の人だとなかなか勝てないくらいの強さです
今回，参考にさせてもらったサイト一覧
オセロをビットボードで実装する
https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43
オセロ AI の教科書
https://note.com/nyanyan_cubetech/m/m54104c8d2f12
実際のコード #
Boardクラス #
class Board{
long my_board;
long op_board;
int myColor;
int myScore;
int opScore;
Board(long my_board, long op_board, int myColor){
this.my_board = my_board;
this.op_board = op_board;
this.myColor = myColor;
}
void getScore(){
myScore = Long.bitCount(my_board);
opScore = Long.bitCount(op_board);
}
}
- getScore()では盤上の石の数を数えています．
- opはopponentの略として使っています.
- javaのlong型は64bitで一番左のbitが立つと負の数として扱われるため注意が必要な場合があるかもしれません．
- my_boardには64桁の2進数が入ります(自分の石がある場所だけbitが立つ)
- myColorには先行なら1後行なら-1が入ります.
OthelloFuncクラス #
頭が悪そうですがコードをそのまま貼ります．
- xが列，yが行に対応しています.例えばx=0,y=7なら盤の左下，x=7,y=1なら盤の右上の1個下です．
- 関数evaluate_by_point()は簡易AIで使います．
- bitの右シフトは»を使ってしまうと左から1が埋まっていくので注意してください．
class OthelloFunc{//オセロの機構のほとんど
long toBit(int x, int y){//盤の一箇所だけビットを立てる
long result = 0b1000000000000000000000000000000000000000000000000000000000000000L;
switch(y){
case 0:
break;
case 1:
result = result >>> 1;
break;
case 2:
result = result >>> 2;
break;
case 3:
result = result >>> 3;
break;
case 4:
result = result >>> 4;
break;
case 5:
result = result >>> 5;
break;
case 6:
result = result >>> 6;
break;
case 7:
result = result >>> 7;
break;
default:
break;
}
result = result >>> (x * 8);
return result;
}
boolean canPut(Board board, long position){//置けるならtrueを返す
long putable_board = makePutableBoard(board.my_board, board.op_board);
return ((putable_board & position) == position);
}
long makePutableBoard(long my_board, long op_board){
long tmp1 = 0b0000000011111111111111111111111111111111111111111111111100000000L;
long tmp2 = 0b0111111001111110011111100111111001111110011111100111111001111110L;
long tmp3 = 0b0000000001111110011111100111111001111110011111100111111000000000L;
long sayuu = op_board & tmp1;
long jouge = op_board & tmp2;
long hen = op_board & tmp3;
long empty_board = ~(op_board | my_board);
long board_tmp = 0L;
long return_board;
//左
board_tmp = sayuu&(my_board << 8);
for(int i = 0; i < 5; i++){
board_tmp |= sayuu&(board_tmp << 8);
}
return_board = empty_board & (board_tmp << 8);
//右
board_tmp = sayuu&(my_board >> 8);
for(int i = 0; i < 5; i++){
board_tmp |= sayuu&(board_tmp >> 8);
}
return_board |= (empty_board&(board_tmp >> 8));
//上
board_tmp = jouge & (my_board << 1);
for(int i = 0; i < 5; i++){
board_tmp |= jouge&(board_tmp << 1);
}
return_board |= (empty_board&(board_tmp << 1));
//下
board_tmp = jouge & (my_board >> 1);
for(int i = 0; i < 5; i++){
board_tmp |= jouge & (board_tmp >> 1);
}
return_board |= (empty_board & (board_tmp >> 1));
// 右上
board_tmp = hen&(my_board >> 7);
for(int i = 0; i < 5; i++){
board_tmp |= hen&(board_tmp >> 7);
}
return_board |= (empty_board&(board_tmp >> 7));
// 左上
board_tmp = hen&(my_board << 9);
for(int i = 0; i < 5; i++){
board_tmp |= hen&(board_tmp << 9);
}
return_board |= (empty_board&(board_tmp << 9));
//右下
board_tmp = hen&(my_board >> 9);
for(int i = 0; i < 5; i++){
board_tmp |= hen&(board_tmp >> 9);
}
return_board |= (empty_board&(board_tmp >> 9));
//左下
board_tmp = hen&(my_board << 7);
for(int i = 0; i < 5; i++){
board_tmp |= hen&(board_tmp << 7);
}
return_board |= (empty_board&(board_tmp << 7));
return return_board;
}
int isPass(Board board){ //パスなら1を返す 違うなら0
long my_legal = makePutableBoard(board.my_board, board.op_board);
long op_legal = makePutableBoard(board.op_board, board.my_board);
if(my_legal == 0 && op_legal != 0){
return 1;
}
return 0;
}
int isEnd(Board board){//終わりなら1を返す
long my_legal = makePutableBoard(board.my_board, board.op_board);
long op_legal = makePutableBoard(board.op_board, board.my_board);
if(my_legal == 0 && op_legal == 0){
return 1;
}
return 0;
}
Board reverse(Board board, long position){
long my_reversed_board = board.my_board;
long op_reversed_board = board.op_board;
long rev_board = 0L;
for(int i = 0; i < 8; i++){
long rev_board_sub = 0L;
long tmp = transfer(position, i);
while((tmp != 0) && ((tmp & op_reversed_board) != 0)){
rev_board_sub |= tmp;
tmp = transfer(tmp, i);
}
if((tmp & my_reversed_board) != 0){
rev_board |= rev_board_sub;
}
}
my_reversed_board ^= position|rev_board;
op_reversed_board ^= rev_board;
Board return_board = new Board(op_reversed_board, my_reversed_board, -board.myColor);
return return_board;
}
long transfer(long position, int i){//reverse用
switch(i){
case 0://上
long ue = 0b1111111011111110111111101111111011111110111111101111111011111110L;
return (position << 1)&(ue);
case 1://下
long shita = 0b0111111101111111011111110111111101111111011111110111111101111111L;
return (position >>> 1)&(shita);
case 2://右
long migi = 0b0000000011111111111111111111111111111111111111111111111111111111L;
return (position >>> 8)&(migi);
case 3://左
long hidari = 0b1111111111111111111111111111111111111111111111111111111100000000L;
return (position << 8)&(hidari);
case 4://右上
long migiue = 0b0000000011111110111111101111111011111110111111101111111011111110L;
return (position >>> 7)&(migiue);
case 5://右下
long migishita = 0b0000000001111111011111110111111101111111011111110111111101111111L;
return (position >>> 9)&(migishita);
case 6://左上
long hidariue = 0b1111111011111110111111101111111011111110111111101111111000000000L;
return (position << 9)&(hidariue);
case 7://左下
long hidarishita = 0b0111111101111111011111110111111101111111011111110111111100000000L;
return (position << 7)&(hidarishita);
default:
System.out.println("transfer error");
return position;
}
}
int evaluate_by_point(Board board){//my_boardから見た盤の評価
int[] board_point = {
150, -20, 0, -1, -1, 0, -20, 150,
-20, -35, -1, -3, -3, -1, -35, -20,
0, -1, 0, -1, -1, 0, -1, 0,
-1, -3, -1, -1, -1, -1, -3, -1,
-1, -3, -1, -1, -1, -1, -3, -1,
0, -1, 0, -1, -1, 0, -1, 0,
-20, -35, -1, -3, -3, -1, -35, -20,
150, -20, 0, -1, -1, 0, -20, 150};
int sum = 0;
if(Long.bitCount(board.my_board) == 0)return -1000;
if(Long.bitCount(board.op_board) == 0)return 1000;
long hidariue = 0b1000000000000000000000000000000000000000000000000000000000000000L;
long hidarishita = 0b0000000100000000000000000000000000000000000000000000000000000000L;
long migiue = 0b0000000000000000000000000000000000000000000000000000000010000000L;
long migishita = 0b0000000000000000000000000000000000000000000000000000000000000001L;
if((board.my_board & hidariue) != 0){//角を取ったら数値を変更
board_point[1] = 30; board_point[8] = 30;board_point[9] = 30;
}
if((board.my_board & hidarishita) != 0){
board_point[48] = 30; board_point[49] = 30;board_point[57] = 30;
}
if((board.my_board & migiue) != 0){
board_point[6] = 30; board_point[14] = 30;board_point[15] = 30;
}
if((board.my_board & migishita) != 0){
board_point[54] = 30; board_point[55] = 30;board_point[62] = 30;
}
String[] target1_str = Long.toBinaryString(board.my_board).split("");
for(int i = 0; i < target1_str.length; i++){
if(target1_str[target1_str.length - i - 1].equals("1")){
sum += board_point[63 - i];
}
}
// String[] target2_str = Long.toBinaryString(board.op_board).split("");
// for(int i = 0; i < target2_str.length; i++){
// if(target2_str[target2_str.length - i - 1].equals("1")){
// sum -= board_point[63 - i];
// }
// }
int i_can_put = Long.bitCount(makePutableBoard(board.my_board, board.op_board));
int u_can_put = Long.bitCount(makePutableBoard(board.op_board, board.my_board));
return sum + (i_can_put - u_can_put) * 3;
// return sum - (u_can_put);
}
void printBoard(Board board){
String[] my_board_info = Long.toBinaryString(board.my_board).split("");
String[] op_board_info = Long.toBinaryString(board.op_board).split("");
String[] integrated_board_info = {"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","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","0","0","0","0","0","0","0","0","0","0"};
for(int i = 0; i < my_board_info.length; i++){//自分の盤の情報を統合
if(my_board_info[my_board_info.length - i -1].equals("1")){
if(board.myColor == 1)integrated_board_info[64 - i - 1] = my_board_info[my_board_info.length - i - 1];
if(board.myColor == -1)integrated_board_info[64 - i - 1] = "-" + my_board_info[my_board_info.length - i - 1];
}
}
for(int i = 0; i < op_board_info.length; i++){//相手の盤の情報を統合
if(op_board_info[op_board_info.length - i -1].equals("1")){
if(board.myColor == 1)integrated_board_info[64 - i - 1] = "-" + op_board_info[op_board_info.length - i - 1];
if(board.myColor == -1)integrated_board_info[64 - i - 1] = op_board_info[op_board_info.length - i - 1];
}
}
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
if(integrated_board_info[8 * j + i].equals("0"))System.out.print("- ");
if(integrated_board_info[8 * j + i].equals("1"))System.out.print("o ");
if(integrated_board_info[8 * j + i].equals("-1"))System.out.print("x ");
}
System.out.println();
}
System.out.println();
}
}
NegaMaxPlayerクラス #
- 簡易AI用のクラスです．
- 変数time_limitは下で説明します
class NegaMaxPlayer{
int reply = -1;
int index;
OthelloFunc oFunction = new OthelloFunc();
long time_limit;
NegaMaxPlayer(Board board, int index, long time_limit){
this.index = index;
this.time_limit = time_limit;
negaMax_search(6, board);
}
int negaMax(int depth, Board board, int passed, int alpha, int beta){//pass なら1
if(System.currentTimeMillis() > time_limit){System.out.println("途中");return -5000;}
int max = -10000;
if(depth == 0){
return oFunction.evaluate_by_point(board);
}
for(int i = 0; i < 64; i++){
long position = oFunction.toBit(i / 8, i % 8);
if(oFunction.canPut(board, position)){
int negaMax_tmp = -negaMax(depth - 1, oFunction.reverse(board, position), 0, -beta, -alpha);
if(negaMax_tmp >= beta)return negaMax_tmp;
alpha = Math.max(alpha, negaMax_tmp);
max = Math.max(max, negaMax_tmp);
}
}
if(max == -10000){//置ける場所がなかった
if(passed == 1){//自分もパスされてきているとpassedに1が入る
return oFunction.evaluate_by_point(board);
}
return -negaMax(depth, oFunction.reverse(board, 0), 1, -beta, -alpha);
}
// System.out.println("depth : " + depth + " max : " + max);
return max;
}
void negaMax_search(int depth, Board board){
int alpha = -10000;
int beta = 10000;
int score;
for(int i = 0; i < 64; i++){
long position = oFunction.toBit(i / 8, i % 8);
if(oFunction.canPut(board, position)){
score = - negaMax(depth, oFunction.reverse(board ,position), 0, - beta, -alpha);
if(alpha < score){
alpha = score;
reply = i;
}
}
}
System.out.println("depth : " + depth + " max : " + alpha);
}
}
DepthPlayerクラス #
- 完全探索用AI用のクラスです
int reply = -1;
long time_limit;
OthelloFunc oFunction = new OthelloFunc();
DepthPlayer(Board board, long time_limit){
this.time_limit = time_limit;
completeWin_search(board);
}
int completeWin(Board board, int passed, int alpha, int beta){
if(System.currentTimeMillis() > time_limit){System.out.println("途中");return 0;}
int max = -10000;
if(oFunction.isEnd(board) == 1){
board.getScore();
int score = board.myScore - board.opScore;
return score;
// if(score > 0)return 1;
// else if(score < 0)return -1;
// else return 0;
}
for(int i = 0; i < 64; i++){
long position = oFunction.toBit(i / 8, i % 8);
if(oFunction.canPut(board, position)){
int canWin_tmp = -completeWin(oFunction.reverse(board, position), 0, -beta, -alpha);
if(canWin_tmp >= beta)return canWin_tmp;
alpha = Math.max(alpha, canWin_tmp);
max = Math.max(max, canWin_tmp);
}
}
if(max == -10000){//置ける場所がなかった
if(passed == 1){//自分もパスされてきているとpassedに1が入る
board.getScore();
int score = board.myScore - board.opScore;
return score;
// if(score > 0)return 1;
// else if(score < 0)return -1;
// else return 0;
}
return -completeWin(oFunction.reverse(board, 0), 1, -beta, -alpha);
}
return max;
}
void completeWin_search(Board board){
int alpha = -10000;
int beta = 10000;
int score;
for(int i = 0; i < 64; i++){
long position = oFunction.toBit(i / 8, i % 8);
if(oFunction.canPut(board, position)){
score = - completeWin(oFunction.reverse(board ,position), 0, - beta, -alpha);
if(alpha < score){
alpha = score;
reply = i;
}
}
}
System.out.println("score : " + alpha);
}
}
MontePlayerクラス(MonteCarloサブクラス有り) #
- モンテカルロ法のAI用クラスです.
- あんまり強くない気がします.
- マルチスレッドで動きます.
class MontePlayer{
Random rnd = new Random();
ArrayList<Integer> canPutPlace = new ArrayList<>();
int reply = -1;
float max = -1;
OthelloFunc oFunction = new OthelloFunc();
int[] win_count_store;
int[] match_count_store;
long time_limit;
MontePlayer(Board board, int time, long time_limit){
this.time_limit = time_limit;
for(int i = 0; i < 64; i++){
long position = oFunction.toBit(i / 8, i % 8);
if(oFunction.canPut(board, position)){
canPutPlace.add(i);
}
}
int canPutPlace_size = canPutPlace.size();
MonteCarlo[] monteCarlo = new MonteCarlo[canPutPlace_size];
win_count_store = new int[canPutPlace_size];
match_count_store = new int[canPutPlace_size];
for(int i = 0; i < canPutPlace_size; i++){//初期化
win_count_store[i] = 0;
match_count_store[i] = 0;
}
for(int i = 0; i < canPutPlace_size; i++){
monteCarlo[i] = new MonteCarlo(board, canPutPlace.get(i), time_limit, i);
}
try{
for(int i = 0; i < canPutPlace_size; i++){
monteCarlo[i].join();
}
} catch(InterruptedException e){
e.printStackTrace();
}
int match_sum = 0;
for(int i = 0; i < canPutPlace_size; i++){
float winRate_tmp = (float)win_count_store[i] / (float)match_count_store[i];
if(winRate_tmp > max){
max = winRate_tmp;
reply = canPutPlace.get(i);
}
System.out.println(">> (" + canPutPlace.get(i) / 8 + " " + canPutPlace.get(i) % 8 + "): WinRate..." + winRate_tmp * 100 + " winNUM: " + win_count_store[i] + " match " + match_count_store[i] );
match_sum += match_count_store[i];
}
System.out.println("試合施行数: " + match_sum);
}
class MonteCarlo extends Thread{
int winCount;
Board board;
int one_roop = 30;
long time_limit;
long firstHand_bit;
int my_i;
MonteCarlo(Board board, int firstHand, long time_limit, int my_i){
this.board = board;
this.time_limit = time_limit;
this.my_i = my_i;
firstHand_bit = oFunction.toBit(firstHand / 8, firstHand % 8);
start();
}
public void run(){
long now_time = System.currentTimeMillis();
while(now_time < time_limit){
now_time = System.currentTimeMillis();
for(int i = 0; i < one_roop; i++){
Board board_sub = oFunction.reverse(board, firstHand_bit);
one_Result(board_sub);
match_count_store[my_i]++;
}
}
}
void one_Result(Board board){//自分が勝ちなら1 相手が勝ち, ドローなら0
Random rnd = new Random();
int myColor = - board.myColor;//一度ひっくり返したものが渡されているので-1することにより自分の色を保存
// System.out.println("渡されたやつ");
// oFunction.printBoard(board);
while(oFunction.isEnd(board) != 1){
int a = rnd.nextInt(64);
int i;
long pos = 0;
for(i = a; i < a + 64; i++){
int tmp = i;
if(tmp >= 64) tmp -= 64;
pos = oFunction.toBit(tmp / 8, tmp % 8);
if(oFunction.canPut(board, pos)){
// System.out.println(tmp / 8 + " " + tmp % 8);
break;
}
// if(i == a + 64 - 1){System.out.println("PASS");}//パス
pos = 0;
}
board = oFunction.reverse(board, pos);
}
if(myColor != board.myColor){
board = oFunction.reverse(board, 0);
}
// System.out.println("myColor: "+ myColor);
// System.out.println("boardColor: "+ board.myColor);
board.getScore();
// oFunction.printBoard(board);
// System.out.println("my score :" + board.myScore);
// System.out.println();
// System.out.println();
int score = board.myScore - board.opScore;
if(score > 0) win_count_store[my_i]++;
}
}
}
Commanderクラス(オセロAI用クラスの使い方) #
- indexには何手目か，が入ります．(最初に4マス埋まっているはずなので一手目を五手目としています)
- 変数timeには一手の探索に何秒掛けるかを入れてください．例えばtimeを5とすると4.5秒で探索をやめます．(time_limitのところ)
- Commanderクラスをインスタンス化すると探索され，get_reply()関数によって結果を使えます．
class Commander{//indexによって...Playerを使い分ける
int reply = -1;
OthelloFunc of = new OthelloFunc();
Commander(int index, Board board, int time){
long constructed_time = System.currentTimeMillis();
long time_limit = (constructed_time + time * 1000 - 500);
System.out.println("index commander:" + index);
if(index < 28){
// MontePlayer mP = new MontePlayer(board, time, time_limit);
// reply = mP.reply;
NegaMaxPlayer nP = new NegaMaxPlayer(board, index, time_limit);
reply = nP.reply;
} else if(index < 50){
NegaMaxPlayer nP = new NegaMaxPlayer(board, index, time_limit);
reply = nP.reply;
// MontePlayer mP = new MontePlayer(board, time, time_limit);
// reply = mP.reply;
} else {
DepthPlayer dP = new DepthPlayer(board, time_limit);
reply = dP.reply;
}
}
int get_reply(){
return reply;
}
}
最後に #
モンテカルロ法よりも数手先を読みながら戦い，最後は完全探索とした方が強いです．
モンテカルロ法は探索回数が少ないと角への意識が低くなってしまう感じがします．