はじめに
この記事は以下の記事のサポート記事です。手順を細かく解説しています。touch-sp.hatenablog.com
解説
前回盤面の表し方を解説しました。【C#】【オセロ】解説記事 part 1 - パソコン関連もろもろ
今回はそれを踏まえてBoardクラスを作っていきます。
Boardクラスの設計
以下のような設計にしました。class Board { private readonly UInt64 init = 1; public UInt64 black; public UInt64 white; public int CurrentColor; public Dictionary<int, UInt64> possiblePos = new Dictionary<int, UInt64>(); public Board(UInt64 black_stone, UInt64 white_stone, int turn) { black = black_stone; white = white_stone; CurrentColor = turn; if (CurrentColor == 1) { update_possiblePos(black, white); } else { update_possiblePos(white, black); } } public Board move(int x) { //これから } public void update_possiblePos(UInt64 turn, UInt64 not_turn) { //これから } }
石の配置をあらわすblackとwhiteという変数（UInt64）と手番を表すCurrentColorという変数(int)を用意しています。
手番を表す変数は符号付の整数です。黒の手番を「1」、白の手番を「-1」と表すことにします。
どうしてblackやwhiteと同様に「0」「1」の2進法で表さないのか？そういう風に疑問に思われる人もいるかもしれません。しかしここは「0」「1」で表すメリットがありません。むしろ「1」「-1」で表した方が-1を掛けるだけでひっくり返るので簡単です。
その他にpossiblePosという辞書型の変数を用意しています。
これは次に石を置く場所を表す整数（int）をキー、それによってひっくり返る石を表す整数（UInt64）をバリューに持つ辞書型変数です。ここではよくわからないと思いますが詳細は後述します。
メソッドとしてはmoveとupdate_possiblePosを用意してます。
moveは石を置いた後の状態を返すメソッドです。今あるBoardオブジェクトの変数を更新する方法もありますが、今回は新しいBoardオブジェクトを返すことにします。PCで解析する時にはトライ＆エラーを繰り返すことになるのですが今あるBoardオブジェクトの変数を更新してしまうと元に戻す作業が必要になるからです。一手石を置くごとにどんどん新しいBoardオブジェクトが作られるようにしています。この部分は目的によって変わってくると思います。
update_possiblePosは新たにBoardオブジェクトが作成された時に辞書型変数possiblePosを作成するためのものです。先ほど書いたようにBoardオブジェクトの変数を更新することはないので呼ばれるのはBoardオブジェクトが新たに作成された時だけです。updateとせずにcreateと名前を付けた方が良かったかもしれません。途中でClassの設計（moveの挙動）を変更したためにこのネーミングが残ってしまいました。
update_possiblePosには手番側の石と手番側でない石を引数として与えます。手番によって変わってくるためです。黒石、白石、手番の3つを引数にとるように設計しても良いと思います。
今回はupdate_possiblePosを呼び出すときに条件分けをしています。
if (CurrentColor == 1) { update_possiblePos(black, white); } else { update_possiblePos(white, black); }
update_possiblePosメソッド
いよいよ石を反転させるコードを書く時がやってきました。オセロのプログラムを書く時に一番難しいところです。この部分に関してはいろんな人がいろんな書き方をしています。どの方法がベストなのかはよくわかりません。とりあえず動けばすべて正解です。
私の方法を紹介します。
まずは基本設計です。このようにしました。
public void update_possiblePos(UInt64 turn, UInt64 not_turn) { UInt64 mask; UInt64 tmp; UInt64 rev; possiblePos.Clear(); for (int i = 0; i < 64; i++) { rev = 0; //8方向の判定 if (rev != 0) possiblePos.Add(i, rev); } }
maskとtmpに関してはここでは無視して下さい。0～63までのすべてのマスについて調べて置ける場所のみpossiblePosに格納します。その際にrevという変数と一緒に辞書型として格納しています。
revは反転する石があるところが「1」、その他が「0」で表された整数（UInt64）です。もう少し読み進めて頂ければ詳細がわかると思います。
iのループ（0～63）の中ではまずi番目に石が置けるかどうかのチェックが必要です。反転する石があるがどうかは後回しにしてそこに石がすでにあるかどうかのチェックをまず行います。これは2行で書けます。
UInt64 check_position = init << i; if (((turn | not_turn) & (check_position)) != 0) continue;
i番目だけ「1」、その他は「0」のcheck_positionを作ります。
手番側の石と手番側でない石を論理OR演算子「|」で計算するとすでに石がある場所が「1」、ない場所が「0」の整数ができます。
それとcheck_positionを論理AND演算子「&」で計算すると石がなければ「0」（64桁すべて0の整数）が返ってきます。石があれば0以外が返ってきます。
ループの部分だけ抽出するとこのようになります。
for (int i = 0; i < 64; i++) { UInt64 mask; UInt64 tmp; rev = 0; UInt64 check_position = init << i; if (((turn | not_turn) & (check_position)) != 0) continue; //8方向の判定 if (rev != 0) possiblePos.Add(i, rev); }
置きたい場所に石がないことがわかれば8方向の判定に入ります。
ここでは右方向の判定のみ解説します。このようにしました。
わかりやすいように手番を黒と仮定して説明します。
//右方向チェック tmp = 0; mask = check_position << 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; while((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; } if ((mask & turn) != 0) rev |= tmp; }
right_left_watcherというまだ定義していない変数が出てきましたがそちらに関しては後述します。
まずはmaskについて説明します。
maskは今現在注目しているマスが「1」、その他が「0」の整数です。まず最初に隣のマスをチェックする必要があるので最初はcheck_positionから「1」の場所をひとつずらしたものになります。盤面では右方向に調べていくのですが64桁の整数を考えるときには「1」は左にずらす必要がありますので注意して下さい。
なぜmaskという変数を用意する必要があるか疑問に思うかもしれません。それはcheck_positionを変更してしまうと他の方向の判定の時に困るからです。check_positionは8方向の判定を行う基準点ですので変更しない方がよいと思います。
right_left_watcherについて説明します。
right_left_watcherは図にすると以下のような整数です。
maskが右端に到達したことを知るために用意しています。オセロプログラムにおいては「番兵」などと表現されることがあります。
このようにしてあらかじめ作っておきました。
UInt64 init = 1; UInt64 right_left_watcher = 0; for (int i = 0; i < 8; i++) { right_left_watcher |= init << i * 8; right_left_watcher |= init << i * 8 + 7; } right_left_watcher = ~right_left_watcher; Console.WriteLine(right_left_watcher.ToString("X16"));
7E7E7E7E7E7E7E7E
これをこのままつかうにはClassの定義の最初に以下を1行を追加する必要があります。
private readonly UInt64 right_left_watcher = Convert.ToUInt64("7E7E7E7E7E7E7E7E", 16);
ここで以下の論理AND演算（&）を考えて下さい。
mask & right_left_watcher
0が返ってくるようならmaskが右端に到達していることを表します。
最初のcheck_positionがすでに右端だった場合はどうでしょう？右に1マスずれると一段下の左端になります。左側にも「0」をならべてあるのでやはりこの演算は0を返します。check_positionが63番目だった場合もC#ではそこから1マスずれると0番目に戻るので問題ありません。
次に以下の論理AND演算（&）を考えて下さい。
mask & not_turn
0以外が返ってくるようならmaskの部分に白石が存在することを表します。
つまり最初のifの部分
if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0)
は右端でなく、かつ白石があることを表しています。
そうとわかれば次々と同様の条件を満たす限りmaskの「1」を一つずつずらしていきます。その際に通った場所に目印を付けていきます。それがtmpになります。
tmpは最初64桁すべて「0」の整数です。今現在注目しているマス白石があればどんどん「1」に変更していきます。
tmp |= mask;
この時点では黒石に挟まれているかどうかを気にする必要はありません。
最後に右端あるいは白石が置かれていないマスに到達した時点でそこに黒石が置かれているかをチェックします。
if ((mask & turn) != 0)
0以外が返ってくるようならmaskの部分に黒石が存在することを表しますのでrevとtmpの論理OR演算を行います。0が返ってきた場合にはtmpはなにもされまいまま破棄されます。
rev |= tmp
ここでのtmpは右方向の判定を行った結果です。最終的にrevは8方向の判定を行いそれぞれのtmpを合算したものになります。
tmpが破棄されるのは無駄のように感じるかもしれませんが反転する石が存在するかをチェックすると同時に反転する石を記録しているためこの方法は効率が良いはずです。石が置けるがどうかを判定する時と、石を置いた時に反転させる動作の時に別々にループ処理を書いているコードも実際にはあります。
もう一度右方向チェックのコードを見てみましょう。
tmp = 0; mask = check_position << 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; while((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; } if ((mask & turn) != 0) rev |= tmp; }
よく見ると最初のifとwhileの条件分岐とその後の演算は全く同じです。コードを省略できるのではと気付いた方は鋭いです。ではなぜこのようにしたか？
すべてをwhileで条件分岐した場合には一番最初にfalseが返ってきた時にも最終行が評価されます。
if ((mask & turn) != 0) rev |= tmp;
最終行のifの条件がtrueになった場合でもtmpは「0」なのでrevに影響はしませんが無駄な評価と演算が行われたことになります。それを避けるために最初だけ別にしています。黒が手番だとして黒石の左隣に黒石を置こうとした場合にこのようなことが生じます。
上下の番兵と全周の番兵に関しても作り方をのせておきます。
UInt64 init = 1; UInt64 right_left_watcher = 0; for (int i = 0; i < 8; i++) { right_left_watcher |= init << i * 8; right_left_watcher |= init << i * 8 + 7; } right_left_watcher = ~right_left_watcher; Console.WriteLine(right_left_watcher.ToString("X16")); UInt64 upper_lower_watcher = 0; for (int i = 0; i < 8; i++) { upper_lower_watcher |= init << i; upper_lower_watcher |= init << i + 56; } upper_lower_watcher = ~upper_lower_watcher; Console.WriteLine(upper_lower_watcher.ToString("X16")); UInt64 around_watcher = right_left_watcher & upper_lower_watcher; Console.WriteLine(around_watcher.ToString("X16"));
7E7E7E7E7E7E7E7E 00FFFFFFFFFFFF00 007E7E7E7E7E7E00
最終的なupdate_possiblePosこのようになります。
public void update_possiblePos(UInt64 turn, UInt64 not_turn) { UInt64 mask; UInt64 tmp; UInt64 rev; possiblePos.Clear(); for (int i = 0; i < 64; i++) { //着手箇所は空白でなければダメ //空きマスが「0」で表されているUInt64と着手箇所との比較 //空白でなければcontinue UInt64 check_position = init << i; if (((turn | not_turn) & (check_position)) != 0) continue; rev = 0; //右方向チェック tmp = 0; mask = check_position << 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; while((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; } if ((mask & turn) != 0) rev |= tmp; } //左方向チェック tmp = 0; mask = check_position >> 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 1; while ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 1; } if ((mask & turn) != 0) rev |= tmp; } //上方向チェック tmp = 0; mask = check_position >> 8; if ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 8; while ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 8; } if ((mask & turn) != 0) rev |= tmp; } //下方向チェック tmp = 0; mask = check_position << 8; if ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 8; while ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 8; } if ((mask & turn) != 0) rev |= tmp; } //右上方向チェック tmp = 0; mask = check_position >> 7; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 7; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 7; } if ((mask & turn) != 0) rev |= tmp; } //右下方向チェック tmp = 0; mask = check_position << 9; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 9; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 9; } if ((mask & turn) != 0) rev |= tmp; } //左上方向チェック tmp = 0; mask = check_position >> 9; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 9; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 9; } if ((mask & turn) != 0) rev |= tmp; } //左下方向チェック tmp = 0; mask = check_position << 7; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 7; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 7; } if ((mask & turn) != 0) rev |= tmp; } if (rev != 0) possiblePos.Add(i, rev); } }
moveメソッド
possiblePosにrevを格納しているのでmoveメソッドは非常に簡単に書けます。public Board move(int x) { UInt64 rev = possiblePos[x]; UInt64 new_black; UInt64 new_white; if (CurrentColor == 1) { new_black = black ^ ((init << x) | rev); new_white = white ^ rev; } else { new_black = black ^ rev; new_white = white ^ (init << x | rev); } return new Board(new_black, new_white, CurrentColor * -1); }
なぜこの演算で石が回転させられるかはビット演算を復習しながらよく考えてみて下さい。
黒が手番と仮定すると黒石がないところに黒石が置かれる（あるいは白から黒に反転する）ので黒石の「0」とrevの「１」で「1」にすればよいことになります。論理OR演算子（|）を使っても論理XOR演算子（^）を使っても結果は同じになります。
白石に関しては白石の「1」とrevの「1」で「0」にする必要がありますので論理XOR演算子（^）を使います。
revはあくまで反転する石の場所を表しているだけでこれから石を配置するマスは「0」になっているのでそこは気を付けてください。それを解決しているのがこの部分になります。
init << x | rev
繰り返しになりますがmoveメソッドは新しいBoardオブジェクトを返すように設計しています。今扱っているBoardオブジェクトの内部変数には全く変更を加えていません。
人によるinputを受け付けるのであれば引数xが妥当かどうかの判定が必要になります。
もし書くならメソッドの冒頭にこのように書けばよいと思います。
if (possiblePos.ContainsKey(x))
今回はPCによる解析を行いますのでpossiblePosのキーを順に引数として与えることになります。この場合には当然チェックは不要です。
Boardクラス全体のコード
最終的なコードはこのようになりました。class Board { private readonly UInt64 init = 1; private readonly UInt64 right_left_watcher = Convert.ToUInt64("7E7E7E7E7E7E7E7E", 16); private readonly UInt64 upper_lower_watcher = Convert.ToUInt64("00FFFFFFFFFFFF00", 16); private readonly UInt64 around_watcher = Convert.ToUInt64("007E7E7E7E7E7E00", 16); public UInt64 black; public UInt64 white; public int CurrentColor; public Dictionary<int, UInt64> possiblePos = new Dictionary<int, UInt64>(); public Board(UInt64 black_stone, UInt64 white_stone, int turn) { black = black_stone; white = white_stone; CurrentColor = turn; if (CurrentColor == 1) { update_possiblePos(black, white); } else { update_possiblePos(white, black); } } public Board move(int x) { UInt64 rev = possiblePos[x]; UInt64 new_black; UInt64 new_white; if (CurrentColor == 1) { new_black = black ^ ((init << x) | rev); new_white = white ^ rev; } else { new_black = black ^ rev; new_white = white ^ (init << x | rev); } return new Board(new_black, new_white, CurrentColor * -1); } public void display() { foreach (int i in Enumerable.Range(0, 8)) { foreach (int j in Enumerable.Range(0, 8)) { if ((black & init << (8 * i + j)) != 0) { Console.Write(" O "); } else { Console.Write(((white & init << (8 * i + j)) != 0) ? " x " : " . "); } } Console.WriteLine(); Console.WriteLine(); } } public void update_possiblePos(UInt64 turn, UInt64 not_turn) { UInt64 mask; UInt64 tmp; UInt64 rev; possiblePos.Clear(); for (int i = 0; i < 64; i++) { //着手箇所は空白でなければダメ //空きマスが「0」で表されているUInt64と着手箇所との比較 //空白でなければcontinue UInt64 check_position = init << i; if (((turn | not_turn) & (check_position)) != 0) continue; rev = 0; //右方向チェック tmp = 0; mask = check_position << 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; while((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 1; } if ((mask & turn) != 0) rev |= tmp; } //左方向チェック tmp = 0; mask = check_position >> 1; if ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 1; while ((mask & right_left_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 1; } if ((mask & turn) != 0) rev |= tmp; } //上方向チェック tmp = 0; mask = check_position >> 8; if ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 8; while ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 8; } if ((mask & turn) != 0) rev |= tmp; } //下方向チェック tmp = 0; mask = check_position << 8; if ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 8; while ((mask & upper_lower_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 8; } if ((mask & turn) != 0) rev |= tmp; } //右上方向チェック tmp = 0; mask = check_position >> 7; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 7; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 7; } if ((mask & turn) != 0) rev |= tmp; } //右下方向チェック tmp = 0; mask = check_position << 9; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 9; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 9; } if ((mask & turn) != 0) rev |= tmp; } //左上方向チェック tmp = 0; mask = check_position >> 9; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 9; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask >> 9; } if ((mask & turn) != 0) rev |= tmp; } //左下方向チェック tmp = 0; mask = check_position << 7; if ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 7; while ((mask & around_watcher) != 0 && (mask & not_turn) != 0) { tmp |= mask; mask = mask << 7; } if ((mask & turn) != 0) rev |= tmp; } if (rev != 0) possiblePos.Add(i, rev); } } }
