🐈

オセロのひっくり返すべき石判定システムとしての正規表現

2021/05/02に公開

正規表現

regex

オセロ

tech

前置き

人類には、時として雑にオセロを実装する必要を迫られる瞬間というものがあります。「なんかこう……オセロ、つくってくんナイ？あ、リバーシでもイイよ」 みたいな、そういうことを突然言われる瞬間があるのです。
オセロエンジンを適当に実装するのもいいですが、必要の迫られ方が雑である以上、実装の仕方も雑であった方が自然（𝑵𝒂𝒕𝒖𝒓𝒂𝒍）というものです。実装の仕方も雑であった方が自然（𝑵𝒂𝒕𝒖𝒓𝒂𝒍）というものです。今、私は同じ文章を二回繰り返しました。それこそが自然（𝑵𝒂𝒕𝒖𝒓𝒂𝒍）というものであり、この事実自体を補強する材料なわけです。

さて、一先ずオセロの雑な実装という課題が浮き上がります。GUIを組むとか平面直角座標系を実装するとかはまあどうしようもないところですが、それはそれとして明らかに短縮できる面倒というものがオセロの実装には存在します。すなわち、ひっくり返すべき石の判定です。
ことあるごとにオセロを実装する必要に迫られ、そしてことあるごとに「えーとこのマスに置いた場合8方向に探索を走らせてこれはひっくり返して……」みたいなコードを書く必要に迫られる―――これは非常に悲しいことです。こういう代り映えのしない作業なんてものは、コピペ一発で片付けられるべきでしょう。

そういうわけで、実際にコピペ1発で終わる正規表現で実装することにします。

仕様

オセロ盤は8*8とする
基本的に黒の手番であるものとして考え、「指定する座標に黒石を置いた場合に、ひっくり返るべき白石」にマッチする正規表現を作るものとする
正規表現にはJavaScriptの記法を使用するものとする
入力される文字列はオセロ盤一列一列を文字列として表現したうえで改行（\n）で結合したものとする
- 文字列およびそれに対応するマスの状態：
  - B：黒石が置かれているマス
  - W：白石が置かれているマス
  - N：石が置かれていないマス
  - P：これから黒石を置く場所として指定されたマス
- 入力例：
```
NNNNNNNN
NNBPWBNN
NNBWWWNN
NNBWWBNN
NNWWBWNN
NNNBNNNN
NNNNNNNN
```

実装

横

めちゃくちゃ簡単です。要するに

Pが左右のどちらかに遠在する
その反対側にはBが遠在する
PおよびBと己の間にはWしか無い（\nやNが無い）
己はWである

という条件に合致する文字列を探すわけですから、

(?<=BW*)W(?=W*P)|(?<=PW*)W(?=W*B)

といった風に記述すればいいです。

縦

やや難しいです。条件としては

Pが真上または真下に遠在する
その反対側にはBが真上または真下に遠在する
PおよびBと己の間（直線的な意味で）にはWしか無い（\nやNが無い）
己はWである

というものです。一見すると横と大して変わらないのですが、この場合「真上または真下に遠在する」の定義をもう少し厳密化する必要があります。
正規表現は基本的に一次元的なものなので「真上」とか「真下」みたいなy軸の要素が出てくると話が一気にややこしくなります。
図で考えてみましょう。

このMSペイントで3分くらいで書いた図において、白駒は黒駒の1マス真下にあるということができます。これを一次元的に定義するならば、

こういった風に、白駒は黒駒の右に8マス（改行含め9マス）進んだ先にあるコマということができるでしょう。
正規表現でこれを定義すると、

(?<=B[^]{8})W

といった風になり、更に「1マス」ではなく単に「真下にある」のみの定義ならば

(?<=B(([^]{8}.)*[^]{8}))W

となるでしょう。
あとは1.の条件のためにBをPに、3.の条件のために.をWに置換し、さらに2.の条件のために「白駒の下に黒駒がある」判定を付け加えると

(?<=P(([^]{8}W)*[^]{8}))W(?=(([^]{8}W)*[^]{8})B)

となります。
あとはこれの逆、つまるところ「上に黒駒があって下に置かれた」バージョンを付け加えて、

(?<=P(([^]{8}W)*[^]{8}))W(?=(([^]{8}W)*[^]{8})B)|(?<=B(([^]{8}W)*[^]{8}))W(?=(([^]{8}W)*[^]{8})P)

が最終的な縦の判定です。

斜め

めんどくさそうなので左上/右下と左下/右上で分けます

左上/右下

基本的に縦の使いまわしです。斜めというのは要するに縦が1列ごとに1マスずれるバージョンですから、8を9にしてやれば事足ります。

(?<=P(([^]{9}W)*[^]{9}))W(?=(([^]{9}W)*[^]{9})B)|(?<=B(([^]{9}W)*[^]{9}))W(?=(([^]{9}W)*[^]{9})P)

左下/右上

問題はこっちかと思ったんですが別にそれほどでもなかったので普通に使いまわしで行けました。

(?<=P(([^]{7}W)*[^]{7}))W(?=(([^]{7}W)*[^]{7})B)|(?<=B(([^]{7}W)*[^]{7}))W(?=(([^]{7}W)*[^]{7})P)

あの、これ分ける必要ありましたかね？

最終的な正規表現

こうなりました。

(?<=BW*)W(?=W*P)|(?<=PW*)W(?=W*B)|(?<=P(([^]{8}W)*[^]{8}))W(?=(([^]{8}W)*[^]{8})B)|(?<=B(([^]{8}W)*[^]{8}))W(?=(([^]{8}W)*[^]{8})P)|(?<=P(([^]{9}W)*[^]{9}))W(?=(([^]{9}W)*[^]{9})B)|(?<=B(([^]{9}W)*[^]{9}))W(?=(([^]{9}W)*[^]{9})P)|(?<=P(([^]{7}W)*[^]{7}))W(?=(([^]{7}W)*[^]{7})B)|(?<=B(([^]{7}W)*[^]{7}))W(?=(([^]{7}W)*[^]{7})P)

これを適当にググったら出てきた正規表現チェッカーに突っ込んで、

NNNNBNNN
NBNNWNNN
NNWNWNBN
NNNWWWNN
NBWWPWWB
NNNWWNNN
NNWNBNNN
NBNNNNNN

みたいな文字列で走らせますと……

イイ感じですね！！

まとめ

みんなも、コピペを使ってらくらくオセロ！！

前置き

仕様

実装

横

縦

斜め

左上/右下

左下/右上

最終的な正規表現

まとめ

Discussion