MATLAB でオセロの次に置ける場所を判定し、描画してみた

# はじめに
この記事は 「[法政大学情報科学部 Advent Calendar 2022](https://qiita.com/advent-calendar/2022/cis_hosei)」 23日目の記事です。

こんにちは、学部 3 年の Ryusei です。
今回は学部 2 年の講義の最終課題で取り組んだ MATLAB によるオセロの判定について紹介していきたいと思います。

# やろうとしていること

オセロの盤面を真上から見た画像を読み込んで、次どこに置くことができるのか判定し、置ける場所に円を描画して出力します。
加えて、現在の白と黒の枚数と置ける場所の数も出力します。
言葉で説明するよりも実際に見てもらった方がわかりやすいと思うので画像を載せておきます。

- 入力画像
![オセロ1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/3e92c41f-d62f-9093-0fc9-0a89f31b01b6.png)
- 白が置ける場所
![実行結果1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/7452b921-9590-9eca-b74f-0d8f3069f0a3.png)
- 黒が置ける場所
![実行結果2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/18bece79-7896-3764-b9b3-3fbd20d0e7d0.png)

このようなことができるコードを実装していきます。

# 実装
初めに言っておきます。とても汚いコードです。変数もテキトウでとても読みにくいですが、良ければ追ってみてください。

## 画像の読み込み
まずは画像を読み込みます。
置ける場所が描画された画像を出力する main 関数があるため、そこに読み込んだ画像を渡してあげます。main 関数の引数は、<b>読み込んだ画像</b>、<b>白と黒どちらを判定するか(0 が白、1 が黒)</b>、<b>置ける場所を描画する色の指定</b>になっています。

```: MATLAB
clear
% 真上からのオセロの画像を読み込む 
I=imread('オセロ1.png');

main(I,0,'b');
main(I,1,'m');
```

## main 関数
main 関数の中を見ていきます。

### すでに置かれているオセロの判定
すでに置いてあるオセロを調べます。1 行目で入力画像を出力しています。最後にこの画像に重ねて置ける場所を描画します。
imfindcircles という関数で円を抽出することができます。この関数は抽出したい円の半径の最大値と最小値を指定する必要があるため 2-4 行目で求めています。
5, 6 行目で円を抽出しています。centB, centD はそれぞれ centerBright, centerDark のことで白の円の中心座標と黒の円の中心座標のことを言っています。centWhite, centBlack のように分かりやすくすればよかったと反省しています。radB, radD はそれぞれ白の円の半径と黒の円の半径を表しています。のちほどまとめて扱いたいため、最後の 2 行で cent と rad をそれぞれまとめています。

```: MATLAB
figure; imshow(I,"InitialMagnification",'fit')
R=(max(size(I))-18)/8;   % 枠線分の大きさ(18)を引いている。
Rmax = floor(R/2);
Rmin = floor(R/4);
[centB, radB] = imfindcircles(I,[Rmin Rmax],'ObjectPolarity','bright');
[centD, radD] = imfindcircles(I,[Rmin Rmax],'ObjectPolarity','dark','EdgeThreshold',0.1);
centBD=[centB; centD];
radBD=[radB; radD];
```

### オセロの行列表現
オセロのマスは 8×8 ですが、外枠も表現したいため 10×10 で行列を作成します。
計画的に書いていなかったため、外枠が 2 、オセロを置ける場所が 100 、白が 0 、黒が 1 という統一感のない表現になっています。
抽出した円の中心座標を 1 マス分の大きさで割ることで行列表現に変換しています。それをやっているのが aa, bb, cc の部分です。


```: MATLAB
% 現在の白黒を10×10の配列で表現する。
% 外枠の分も含めるため8×8ではなく10×10である。
A=ones(10)+1;
A(2:9,2:9)=A(2:9,2:9)+98;
aa=round(centB/R);
bb=round(centD/R);
cc=[aa;bb];
for i=1:length(aa)
    a=aa(i,:)+1;  % 外枠分、ずれているため +1
    A(a(2),a(1))=0;
end
for i=1:length(bb)
    b=bb(i,:)+1;  % 外枠分、ずれているため +1
    A(b(2),b(1))=1;
end
```
こんな感じです。↓

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/dd416136-7294-e85a-643a-4f97be95bc2c.png)


### 置ける場所の探索

置ける場所を探索します。
最初の cent は、検出した置ける場所の中心座標を入れておく変数です。
count_main は置ける場所を座標に変換する際に使用します。
1 マスずつみていき、横方向、縦方向、斜め 2 方向を探索します。
探索した結果、どこかで置けると判定した場合は count_main を 1 増やします。

```: MATLAB
cent=zeros(64,2);
count_main=1;
for i=2:9
    for j=2:9
        tf_row=check_search(A,i,j,0,1,judge);  % 横方向の探索。tf_row=true なら置ける。
        tf_col=check_search(A,i,j,1,0,judge);  % 縦方向の探索。tf_col=true なら置ける。
        tf_dd=check_search(A,i,j,1,1,judge);  % 左上から右下方向の探索。tf_dd=true なら置ける。
        tf_du=check_search(A,i,j,1,-1,judge);  % 左下から右上方向の探索。tf_du=true なら置ける。
        if tf_row==true || tf_col==true || tf_dd==true || tf_du==true
            count_main=count_main+1;
        end
    end
end
```

- 探索できるか確認する関数

この関数ではマス目を一つ一つ見ていき、置ける場所か確認する関数です。実際に探索する関数は別に定義していて、その関数を呼び出しています。
i_plus, j_plus には 1, 0 -1 が入り、この2つの変数を組み合わせて探索する方向を決めます。たとえば、i_plus = 0, j_plus = 1 だと、横方向の探索になり、i_plus = 1, j_plus = -1 だと、左下から右上方向の探索になります。
1 つ目の判定条件は、<b> 何も置かれていないマス目 </b> かつ <b> 隣のマスに異なる色が置かれていない</b> です。例えば、白が置ける場所を探している場合、現在注目している場所に何も置かれていなくて、隣のマスに黒が置かれていたとき、探索を開始します。探索した結果なかった場合に次の条件分岐で反対方向を探索するようにしています。

```: check_search 関数
% どちら側に探索できるか判定し、探索する関数
function tf=check_search(A,i,j,i_plus,j_plus,judge)
tf=false;
if A(i,j)==100 && A(i+i_plus,j+j_plus)==abs(judge-1)
    tf=serach(A,i,j,i_plus,j_plus,judge);
elseif  A(i,j)==100 && A(i-i_plus,j-j_plus)==abs(judge-1) && tf==false
            tf=serach(A,i,j,-i_plus,-j_plus,judge);
end
end
```

- 探索する関数

オセロの行列を回すため 1 から 10 まで while 文をまわします。
while 文の中の最初の条件分岐では、終了条件を判定しています。<b> 隣のマスが外枠 </b>、<b> 隣のマスに何も置かれていない </b>、<b> すでに置けると判定された </b> の 3 つです。次の条件は、<b> 隣のマスが探索している色であるか </b> です。探索している色があれば座標を計算して cent に格納しておきます。

```: search 関数
% 探索する関数。i_plus と j_plus に 0, 1, -1 を入れることで探索する方向を決める。
function tf=serach(A,i,j,i_plus,j_plus,judge)
tf=false;
count_search=0;
while j>1 || j<10 
    count_search=count_search+1;
    if A(i+i_plus,j+j_plus)==2 || A(i+i_plus,j+j_plus)==100 || tf==true
        break
    elseif A(i+i_plus,j+j_plus)==judge
        tf=true;
        [~, Locb]=ismember([j_ans(1)+j_ans(2)-1 i_ans(1)+i_ans(2)-1],cc,'rows');
        cent(count_main,:)=[centBD(Locb,1)-R*j_ans(2) centBD(Locb,2)-R*i_ans(2)];
    end
    置ける場所を探索後、元の座標に戻す際、置ける場所の隣にある石の中心座標を基準に
    % 次置ける場所の中心座標を求めるため、どちらの方向に石があるのかを把握するための処理。
    if count_search==1
        i_ans=[i i_plus];
        j_ans=[j j_plus];
    end
    i=i+i_plus;
    j=j+j_plus;
end
end
```

### 描画するための工夫

探索した結果、重複して判定している箇所があるため、それらを削除します。
MATLAB の length や numel などは特に指定しない限り長さや要素数すべてを返します。たとえば 6 行 2 列の場合、12 が返ってきます。そのため、今回のコードではだいたい割る 2 をしています。
中心座標 ±5 の範囲内のものがあれば 0 にするようにしています。
1 つ目から順にみていくので、内側の for 文は i+1 から始めるようにしました。
コメントアウトにも書いてありますが、idx の部分で要素が 0 の行を削除します。円を描画する際に、中心座標と半径の行列は要素数が同じでないとエラーになってしまうため、要素数をそろえます。今回は抽出したオセロで最も小さい半径を描画する円の半径に採用しました。

```: MATLAB
% 縦横斜めで、置ける場所が被ってしまった場合、すべて出力すると重なってしまい見にくい上に
% 置ける場所を数える際に正確な値を求められないため、重複をなくす。
len=length(find(cent))/2;
for i=1:len-1
    for j=i+1:len
        if cent(j,1)>=cent(i,1)-5 && cent(j,1)<=cent(i,1)+5 && cent(j,2)>=cent(i,2)-5 && cent(j,2)<=cent(i,2)+5
            cent(j,:)=0;
        end
    end
end
% 要素が [0 0] の行を削除する。
idx = cent(:,1)==0 & cent(:,2)==0;
centnew=cent(~idx,:);

% 置ける場所の中心座標と同じ長さでないと出力できないので、同じ長さの列ベクトルを作成する。
radnew=zeros(numel(centnew)/2,1)+min(radBD);
```

### 出力方法

白と黒どちらの判定をしているのかで title を変え、sprintf で探索した結果を描画していきます。最後の viscircles で中心座標 centnew、半径 randnew、色が color の円を描画しています。

```: MATLAB
% 白(0) ならタイトルを 'White' にし、黒(1) ならタイトルを 'Black' にする。
if judge==0
    title('White','FontSize',25);
elseif judge==1
    title('Black','FontSize',25);
end
S=sprintf('white = %d枚\nblack = %d枚\nplace = %d\n',length(centB),length(centD),numel(centnew)/2); 
xlabel(S,'FontSize',15)

V=viscircles(centnew, radnew,'Color',color);
```
# 出力結果

今回用意した画像ではすべてうまく判定して描画できました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/15f1e210-ecf1-d824-c736-766797544073.png)


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/ae6ace38-1cc9-bc69-e449-87140092db27.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/b4e32537-149c-663a-ab64-985bfc137fa0.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/dd2e133e-9f57-f899-fa0c-995b7eee35ab.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2631291/4bcdb702-a4ee-b6ca-04b3-97caf482a591.png)


# 最後に
一応オセロで次に置くことのできる場所を判定して描画することができました！今回は最終課題ということでレポートも書かなければいけなく、そこまでコードに時間をかけることができなかったためかなり汚いコードとなっています(言い訳)。変数名やアルゴリズムをもっとわかりやすくできたなと、あとあと後悔しています。あと、説明するために久々にコード読んでみましたが、これほんとに必要か？とかここ違くね？ってとこが結構あったのでちょっと書きなおす必要がありそうです。やっぱりあとのことを色々と考えてプログラムした方がいいですね。
次はこれを発展させて、真上からの画像だけでなく、斜めから撮影した実際のオセロの写真でも認識して判定できるようにしたいと思ってますが、おそらくやることはないでしょう（笑）。

# コード
https://github.com/Ryusei5361/matlab_osero_judge/blob/main/osero_judge_next.m