grafi.jp

!77-77-77-77-77-77-77-77 !76-76-76-76-76-76-76-76 !75-75-75-75-75-75-75-75 !74-74-74-74-74-74-74-74 !73-73-73-73-73-73-73-73 !72-72-72-72-72-72-72-72 !71-71-71-71-71-71-71-71 !70-70-70-70-70-70-70-70
!67-67-67-67-67-67-67-67 !66-66-66-66-66-66-66-66 !65-65-65-65-65-65-65-65 !64-64-64-64-64-64-64-64 !63-63-63-63-63-63-63-63 !62-62-62-62-62-62-62-62 !61-61-61-61-61-61-61-61 !60-60-60-60-60-60-60-60
!57-57-57-57-57-57-57-57 !56-56-56-56-56-56-56-56 !55-55-55-55-55-55-55-55 !54-54-54-54-54-54-54-54 !53-53-53-53-53-53-53-53 !52-52-52-52-52-52-52-52 !51-51-51-51-51-51-51-51 !50-50-50-50-50-50-50-50
!47-47-47-47-47-47-47-47 !46-46-46-46-46-46-46-46 !45-45-45-45-45-45-45-45 !44-44-44-44-44-44-44-44 !43-43-43-43-43-43-43-43 !42-42-42-42-42-42-42-42 !41-41-41-41-41-41-41-41 !40-40-40-40-40-40-40-40
!37-37-37-37-37-37-37-37 !36-36-36-36-36-36-36-36 !35-35-35-35-35-35-35-35 !34-34-34-34-34-34-34-34 !33-33-33-33-33-33-33-33 !32-32-32-32-32-32-32-32 !31-31-31-31-31-31-31-31 !30-30-30-30-30-30-30-30
!27-27-27-27-27-27-27-27 !26-26-26-26-26-26-26-26 !25-25-25-25-25-25-25-25 !24-24-24-24-24-24-24-24 !23-23-23-23-23-23-23-23 !22-22-22-22-22-22-22-22 !21-21-21-21-21-21-21-21 !20-20-20-20-20-20-20-20
!17-17-17-17-17-17-17-17 !16-16-16-16-16-16-16-16 !15-15-15-15-15-15-15-15 !14-14-14-14-14-14-14-14 !13-13-13-13-13-13-13-13 !12-12-12-12-12-12-12-12 !11-11-11-11-11-11-11-11 !10-10-10-10-10-10-10-10
!07-07-07-07-07-07-07-07 !06-06-06-06-06-06-06-06 !05-05-05-05-05-05-05-05 !04-04-04-04-04-04-04-04 !03-03-03-03-03-03-03-03 !02-02-02-02-02-02-02-02 !01-01-01-01-01-01-01-01 !00-00-00-00-00-00-00-00

この記事は Haskell Advenct Calender の17日目の記事です。遅れてしまって申し訳ありません。svg画像が表示できるブラウザで閲覧してください。

学科の課題で夏休みにHaskellで リバーシAIの実装 を行ったのですが、その際に考えた盤面処理のアルゴリズムを画像として可視化したいなと思っていたので、Haskellで図形描画をするライブラリである Diagrams を使って行いました。

ビット演算を駆使してビットを並び替えるようなアルゴリズムは好きなのですが、そうしたアルゴリズムは概して暗号じみています(ビット反転 などが例)。その手のアルゴリズムを上手く画像で表現する、めずらしい試みかと思います。

ビットボードとは

リバーシのAIを実装する際に用いる、盤面を保持するためのデータ構造の一つです。ビットボードという名前は、石が置かれているかどうかが1ビットで表現されて、ビット演算によって操作するということを意味します。64bitマシンの場合、盤面の各位置に黒の石が置かれているかどうかを表すビットベクトルは,64bit整数、即ちCPUのレジスタ一つだけの空間消費で表現できます。白の石についても同様です。つまり、盤面全体がレジスタ二つに収まるということで、高速な処理が期待できます。

ビットボードの処理方法

リバーシの実装において絶対に必要になってくるのは、

  • 石を打てる位置を列挙する処理
  • ある場所に石を打った後に、石を裏返して新しい盤面を作る処理

です。ナイーブにやってもさほど重くはないですが、探索速度に効いてくるので無限に高速化したい部分です。

このうち、石を打てる位置の列挙に関しては、盤面の全体を同時に処理する効率のよい実装が比較的シンプルに可能です。解説が http://d.hatena.ne.jp/ainame/20100426/1272236395 にありますが、上下左右斜めの各方向について、盤面をシフトしながら石を置ける位置の候補を表すビットベクトルを取り出して、全ての候補をORしてやるイメージで、ビットベクトルとして石を打てる位置がまとめて得られます。なお、まとめて得た位置を順に取り出すには,単純にループしても良いですが、y=x&(-x)によってxの一番低い位置で立っているビットが取り出せるという有名なビット演算のテクニックを使うとより高速です。

次に、盤面を更新する処理を考えます。まず、この処理は明らかに上下左右斜めの8方向について独立に行うことができます。上向きと下向きといった180度違いの方向を別々に処理するのはもったいないので、何とか上手いことして同時に処理するようにすれば、4方向についての処理に帰着できます。

この処理を行うために、まず着目している方向の列上での石の並びを、黒と白の両方について、8bitのビットベクトルとして取得します。そして、何らかの方法によって、列上で裏返る石がどれかを示す8bitベクトルを取得します。次に、元々の64bitの盤面上の適切な位置に、8bitベクトル上のビットを戻します。ここまでできれば各方向について裏返る石の場所が分かるので、元の盤面にXORしてやれば新しい盤面が得られます。

列上で裏返る石を取得する方法ですが、普通にループで処理することも可能ですし、またルックアップテーブルを使った凝った実装( Edaxというリバーシプログラムでの実装 のコメントや https://github.com/grafi-tt/tatsuki/tree/2f85835c5aab83c3c60999a37a51fa4794c84285#一つの列をひっくり返した結果の取得 を参照)が存在します。斜めの方向の場合は、盤面の両端をまたぐケースの処理が必要になったりもしますが。

残るは、8bitベクトルを得る処理と、8bitベクトルを元の盤面上の位置に戻す処理です。ビット演算や特定のパターンによる乗算を駆使することで可能ですが、ソースコードは暗号じみたものになります。そこで、この部分を可視化することを試みました。

8bitベクトルの抽出・復元処理の可視化

記事の冒頭の画像を確認してください。まず、画像はリバーシの盤面に対応しており、つまりビットボード実装では各マス目が64bit整数の各ビットに対応しています。ここで、LSB(右端のビット)を一番右下のマスに対応させ、MSB(左端のビット)を一番左上のマスに対応させます。ビットが左にずれるごとに左のマスにずれていき、8bit左にずれた地点で、一つ上のマスに移動するような対応とします。

ビット演算を繰り返すにしたがって、行った演算に従って64bit整数中のそれぞれのビットが移動します。冒頭の画像や以下に示す画像では、それぞれのビットに元の盤面での位置ごとに違う色を割り当ててやって、各演算ごとに動かしています。こうすることで、ビットの移動が視覚的に追跡できてアルゴリズムの理解が容易になります。

さて、盤面上で左右方向に並んだ駒を8bitベクトルとして得ることを考えます。この際、着目する左右方向の列として8通りの列を選ぶことができます。画像中のそれぞれの三角形の色相は、「元々の盤面でどの列に所属しているビットであるか」を示します。一方三角形の濃度は、列の中で何番目にあたるかを示します。

0から7までの自然数nを固定して、n番目の列に着目するとします。n={0,1,2,3,4,5,6,7}について、それぞれ{赤,橙,金,草,緑,水,紺,紫}色に対応させています。色の選択は、CIELAB表色系において明度や色相に相当するパラメータをずらしていくことで行いました。sRGBのディスプレイで表示すると色が変になったり区別がつきにくくなったりしたので、比較的マシになるパラメータを探して決定しました(MacBook Airで作業していたものの、他のディスプレイでは違うかもしれません。また、色覚異常がある場合の見え方などは考慮していません。ご容赦ください。)。

n番目の列を8bitビットベクトルとして取り出すためには、nビットだけシフトするといった、nの値に依存する処理が当然必要となります。n=0のときの処理を追跡するのが東北東の方角にある三角形です。そこから反時計回りに、n=1、n=2…のときの処理を追跡させて、東南東の方角においてn=7のときの処理を追跡させます。元々の盤面においてn番目の列以外に所属するビットが三角形の中に入るとすれば、そのビットは8bitベクトルの中には現れない余計なビットということになります。つまり、決まった方角の三角形は決まった色が入るべきであって、そうでなければ余計ということになります。余計である場所には、分かりやすくするためにグレーの線をいれています。

8bitベクトルを得て、そこから裏返る石の8bitベクトルを得て、元の盤面上に復元するという処理ですが、裏返る石を得る部分はビットの移動には関係ないので、省略して続けて書いてしまっています。

上下方向

元々の盤面。nをy座標(xy座標は、右下端が0で左上端が7。以下同様)とする。

!77-77-77-77-77-77-77-77 !76-76-76-76-76-76-76-76 !75-75-75-75-75-75-75-75 !74-74-74-74-74-74-74-74 !73-73-73-73-73-73-73-73 !72-72-72-72-72-72-72-72 !71-71-71-71-71-71-71-71 !70-70-70-70-70-70-70-70
!67-67-67-67-67-67-67-67 !66-66-66-66-66-66-66-66 !65-65-65-65-65-65-65-65 !64-64-64-64-64-64-64-64 !63-63-63-63-63-63-63-63 !62-62-62-62-62-62-62-62 !61-61-61-61-61-61-61-61 !60-60-60-60-60-60-60-60
!57-57-57-57-57-57-57-57 !56-56-56-56-56-56-56-56 !55-55-55-55-55-55-55-55 !54-54-54-54-54-54-54-54 !53-53-53-53-53-53-53-53 !52-52-52-52-52-52-52-52 !51-51-51-51-51-51-51-51 !50-50-50-50-50-50-50-50
!47-47-47-47-47-47-47-47 !46-46-46-46-46-46-46-46 !45-45-45-45-45-45-45-45 !44-44-44-44-44-44-44-44 !43-43-43-43-43-43-43-43 !42-42-42-42-42-42-42-42 !41-41-41-41-41-41-41-41 !40-40-40-40-40-40-40-40
!37-37-37-37-37-37-37-37 !36-36-36-36-36-36-36-36 !35-35-35-35-35-35-35-35 !34-34-34-34-34-34-34-34 !33-33-33-33-33-33-33-33 !32-32-32-32-32-32-32-32 !31-31-31-31-31-31-31-31 !30-30-30-30-30-30-30-30
!27-27-27-27-27-27-27-27 !26-26-26-26-26-26-26-26 !25-25-25-25-25-25-25-25 !24-24-24-24-24-24-24-24 !23-23-23-23-23-23-23-23 !22-22-22-22-22-22-22-22 !21-21-21-21-21-21-21-21 !20-20-20-20-20-20-20-20
!17-17-17-17-17-17-17-17 !16-16-16-16-16-16-16-16 !15-15-15-15-15-15-15-15 !14-14-14-14-14-14-14-14 !13-13-13-13-13-13-13-13 !12-12-12-12-12-12-12-12 !11-11-11-11-11-11-11-11 !10-10-10-10-10-10-10-10
!07-07-07-07-07-07-07-07 !06-06-06-06-06-06-06-06 !05-05-05-05-05-05-05-05 !04-04-04-04-04-04-04-04 !03-03-03-03-03-03-03-03 !02-02-02-02-02-02-02-02 !01-01-01-01-01-01-01-01 !00-00-00-00-00-00-00-00

n×8ビット右シフト

!__-__-__-__-__-__-__-77 !__-__-__-__-__-__-__-76 !__-__-__-__-__-__-__-75 !__-__-__-__-__-__-__-74 !__-__-__-__-__-__-__-73 !__-__-__-__-__-__-__-72 !__-__-__-__-__-__-__-71 !__-__-__-__-__-__-__-70
!__-__-__-__-__-__-77-67 !__-__-__-__-__-__-76-66 !__-__-__-__-__-__-75-65 !__-__-__-__-__-__-74-64 !__-__-__-__-__-__-73-63 !__-__-__-__-__-__-72-62 !__-__-__-__-__-__-71-61 !__-__-__-__-__-__-70-60
!__-__-__-__-__-77-67-57 !__-__-__-__-__-76-66-56 !__-__-__-__-__-75-65-55 !__-__-__-__-__-74-64-54 !__-__-__-__-__-73-63-53 !__-__-__-__-__-72-62-52 !__-__-__-__-__-71-61-51 !__-__-__-__-__-70-60-50
!__-__-__-__-77-67-57-47 !__-__-__-__-76-66-56-46 !__-__-__-__-75-65-55-45 !__-__-__-__-74-64-54-44 !__-__-__-__-73-63-53-43 !__-__-__-__-72-62-52-42 !__-__-__-__-71-61-51-41 !__-__-__-__-70-60-50-40
!__-__-__-77-67-57-47-37 !__-__-__-76-66-56-46-36 !__-__-__-75-65-55-45-35 !__-__-__-74-64-54-44-34 !__-__-__-73-63-53-43-33 !__-__-__-72-62-52-42-32 !__-__-__-71-61-51-41-31 !__-__-__-70-60-50-40-30
!__-__-77-67-57-47-37-27 !__-__-76-66-56-46-36-26 !__-__-75-65-55-45-35-25 !__-__-74-64-54-44-34-24 !__-__-73-63-53-43-33-23 !__-__-72-62-52-42-32-22 !__-__-71-61-51-41-31-21 !__-__-70-60-50-40-30-20
!__-77-67-57-47-37-27-17 !__-76-66-56-46-36-26-16 !__-75-65-55-45-35-25-15 !__-74-64-54-44-34-24-14 !__-73-63-53-43-33-23-13 !__-72-62-52-42-32-22-12 !__-71-61-51-41-31-21-11 !__-70-60-50-40-30-20-10
!77-67-57-47-37-27-17-07 !76-66-56-46-36-26-16-06 !75-65-55-45-35-25-15-05 !74-64-54-44-34-24-14-04 !73-63-53-43-33-23-13-03 !72-62-52-42-32-22-12-02 !71-61-51-41-31-21-11-01 !70-60-50-40-30-20-10-00
<<<
!67-57-47-37-27-17-07-__ !66-56-46-36-26-16-06-__ !65-55-45-35-25-15-05-__ !64-54-44-34-24-14-04-__ !63-53-43-33-23-13-03-__ !62-52-42-32-22-12-02-__ !61-51-41-31-21-11-01-__ !60-50-40-30-20-10-00-__
!57-47-37-27-17-07-__-__ !56-46-36-26-16-06-__-__ !55-45-35-25-15-05-__-__ !54-44-34-24-14-04-__-__ !53-43-33-23-13-03-__-__ !52-42-32-22-12-02-__-__ !51-41-31-21-11-01-__-__ !50-40-30-20-10-00-__-__
!47-37-27-17-07-__-__-__ !46-36-26-16-06-__-__-__ !45-35-25-15-05-__-__-__ !44-34-24-14-04-__-__-__ !43-33-23-13-03-__-__-__ !42-32-22-12-02-__-__-__ !41-31-21-11-01-__-__-__ !40-30-20-10-00-__-__-__
!37-27-17-07-__-__-__-__ !36-26-16-06-__-__-__-__ !35-25-15-05-__-__-__-__ !34-24-14-04-__-__-__-__ !33-23-13-03-__-__-__-__ !32-22-12-02-__-__-__-__ !31-21-11-01-__-__-__-__ !30-20-10-00-__-__-__-__
!27-17-07-__-__-__-__-__ !26-16-06-__-__-__-__-__ !25-15-05-__-__-__-__-__ !24-14-04-__-__-__-__-__ !23-13-03-__-__-__-__-__ !22-12-02-__-__-__-__-__ !21-11-01-__-__-__-__-__ !20-10-00-__-__-__-__-__
!17-07-__-__-__-__-__-__ !16-06-__-__-__-__-__-__ !15-05-__-__-__-__-__-__ !14-04-__-__-__-__-__-__ !13-03-__-__-__-__-__-__ !12-02-__-__-__-__-__-__ !11-01-__-__-__-__-__-__ !10-00-__-__-__-__-__-__
!07-__-__-__-__-__-__-__ !06-__-__-__-__-__-__-__ !05-__-__-__-__-__-__-__ !04-__-__-__-__-__-__-__ !03-__-__-__-__-__-__-__ !02-__-__-__-__-__-__-__ !01-__-__-__-__-__-__-__ !00-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-_\_

ビットマスク

________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ _______\_
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000

8bitのベクトルが得られました。

n×8ビット左シフト

7_______ 6_______ 5_______ 4_______ 3_______ 2_______ 1_______ 0_______
_7______ _6______ _5______ _4______ _3______ _2______ _1______ _0______
__7_____ __6_____ __5_____ __4_____ __3_____ __2_____ __1_____ __0_____
___7____ ___6____ ___5____ ___4____ ___3____ ___2____ ___1____ ___0____
____7___ ____6___ ____5___ ____4___ ____3___ ____2___ ____1___ ____0___
_____7__ _____6__ _____5__ _____4__ _____3__ _____2__ _____1__ _____0__
______7_ ______6_ ______5_ ______4_ ______3_ ______2_ ______1_ ______0_
_______7 _______6 _______5 _______4 _______3 _______2 _______1 _____\_\_0

元の盤面上の位置に復元されました。

上下方向

元々の盤面。nはx座標。

!70-70-70-70-70-70-70-70 !60-60-60-60-60-60-60-60 !50-50-50-50-50-50-50-50 !40-40-40-40-40-40-40-40 !30-30-30-30-30-30-30-30 !20-20-20-20-20-20-20-20 !10-10-10-10-10-10-10-10 !00-00-00-00-00-00-00-00
!71-71-71-71-71-71-71-71 !61-61-61-61-61-61-61-61 !51-51-51-51-51-51-51-51 !41-41-41-41-41-41-41-41 !31-31-31-31-31-31-31-31 !21-21-21-21-21-21-21-21 !11-11-11-11-11-11-11-11 !01-01-01-01-01-01-01-01
!72-72-72-72-72-72-72-72 !62-62-62-62-62-62-62-62 !52-52-52-52-52-52-52-52 !42-42-42-42-42-42-42-42 !32-32-32-32-32-32-32-32 !22-22-22-22-22-22-22-22 !12-12-12-12-12-12-12-12 !02-02-02-02-02-02-02-02
!73-73-73-73-73-73-73-73 !63-63-63-63-63-63-63-63 !53-53-53-53-53-53-53-53 !43-43-43-43-43-43-43-43 !33-33-33-33-33-33-33-33 !23-23-23-23-23-23-23-23 !13-13-13-13-13-13-13-13 !03-03-03-03-03-03-03-03
!74-74-74-74-74-74-74-74 !64-64-64-64-64-64-64-64 !54-54-54-54-54-54-54-54 !44-44-44-44-44-44-44-44 !34-34-34-34-34-34-34-34 !24-24-24-24-24-24-24-24 !14-14-14-14-14-14-14-14 !04-04-04-04-04-04-04-04
!75-75-75-75-75-75-75-75 !65-65-65-65-65-65-65-65 !55-55-55-55-55-55-55-55 !45-45-45-45-45-45-45-45 !35-35-35-35-35-35-35-35 !25-25-25-25-25-25-25-25 !15-15-15-15-15-15-15-15 !05-05-05-05-05-05-05-05
!76-76-76-76-76-76-76-76 !66-66-66-66-66-66-66-66 !56-56-56-56-56-56-56-56 !46-46-46-46-46-46-46-46 !36-36-36-36-36-36-36-36 !26-26-26-26-26-26-26-26 !16-16-16-16-16-16-16-16 !06-06-06-06-06-06-06-06
!77-77-77-77-77-77-77-77 !67-67-67-67-67-67-67-67 !57-57-57-57-57-57-57-57 !47-47-47-47-47-47-47-47 !37-37-37-37-37-37-37-37 !27-27-27-27-27-27-27-27 !17-17-17-17-17-17-17-17 !07-07-07-07-07-07-07-07

nビット右シフト

!__-__-__-__-__-__-__-70 !__-__-__-__-__-__-70-60 !__-__-__-__-__-70-60-50 !__-__-__-__-70-60-50-40 !__-__-__-70-60-50-40-30 !__-__-70-60-50-40-30-20 !__-70-60-50-40-30-20-10 !70-60-50-40-30-20-10-00
!60-50-40-30-20-10-00-71 !50-40-30-20-10-00-71-61 !40-30-20-10-00-71-61-51 !30-20-10-00-71-61-51-41 !20-10-00-71-61-51-41-31 !10-00-71-61-51-41-31-21 !00-71-61-51-41-31-21-11 !71-61-51-41-31-21-11-01
!61-51-41-31-21-11-01-72 !51-41-31-21-11-01-72-62 !41-31-21-11-01-72-62-52 !31-21-11-01-72-62-52-42 !21-11-01-72-62-52-42-32 !11-01-72-62-52-42-32-22 !01-72-62-52-42-32-22-12 !72-62-52-42-32-22-12-02
!62-52-42-32-22-12-02-73 !52-42-32-22-12-02-73-63 !42-32-22-12-02-73-63-53 !32-22-12-02-73-63-53-43 !22-12-02-73-63-53-43-33 !12-02-73-63-53-43-33-23 !02-73-63-53-43-33-23-13 !73-63-53-43-33-23-13-03
!63-53-43-33-23-13-03-74 !53-43-33-23-13-03-74-64 !43-33-23-13-03-74-64-54 !33-23-13-03-74-64-54-44 !23-13-03-74-64-54-44-34 !13-03-74-64-54-44-34-24 !03-74-64-54-44-34-24-14 !74-64-54-44-34-24-14-04
!64-54-44-34-24-14-04-75 !54-44-34-24-14-04-75-65 !44-34-24-14-04-75-65-55 !34-24-14-04-75-65-55-45 !24-14-04-75-65-55-45-35 !14-04-75-65-55-45-35-25 !04-75-65-55-45-35-25-15 !75-65-55-45-35-25-15-05
!65-55-45-35-25-15-05-76 !55-45-35-25-15-05-76-66 !45-35-25-15-05-76-66-56 !35-25-15-05-76-66-56-46 !25-15-05-76-66-56-46-36 !15-05-76-66-56-46-36-26 !05-76-66-56-46-36-26-16 !76-66-56-46-36-26-16-06
!66-56-46-36-26-16-06-77 !56-46-36-26-16-06-77-67 !46-36-26-16-06-77-67-57 !36-26-16-06-77-67-57-47 !26-16-06-77-67-57-47-37 !16-06-77-67-57-47-37-27 !06-77-67-57-47-37-27-17 !77-67-57-47-37-27-17-07
<<<
!67-57-47-37-27-17-07-__ !57-47-37-27-17-07-__-__ !47-37-27-17-07-__-__-__ !37-27-17-07-__-__-__-__ !27-17-07-__-__-__-__-__ !17-07-__-__-__-__-__-__ !07-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__
!__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-__ !__-__-__-__-__-__-__-_\_

ビットマスク

________ ________ ________ ________ ________ ________ ________ 00000000
________ ________ ________ ________ ________ ________ ________ 11111111
________ ________ ________ ________ ________ ________ ________ 22222222
________ ________ ________ ________ ________ ________ ________ 33333333
________ ________ ________ ________ ________ ________ ________ 44444444
________ ________ ________ ________ ________ ________ ________ 55555555
________ ________ ________ ________ ________ ________ ________ 66666666
________ ________ ________ ________ ________ ________ _______\_ 77777777

1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1

を掛ける

________ ________ ________ ________ ________ ________ ________ ________
00000000 ________ ________ ________ ________ ________ ________ ________
11111111 00000000 ________ ________ ________ ________ ________ ________
22222222 11111111 00000000 ________ ________ ________ ________ ________
33333333 22222222 11111111 00000000 ________ ________ ________ ________
44444444 33333333 22222222 11111111 00000000 ________ ________ ________
55555555 44444444 33333333 22222222 11111111 00000000 ________ ________
66666666 55555555 44444444 33333333 22222222 11111111 00000000 ________
>>>
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
________ 77777777 66666666 55555555 44444444 33333333 22222222 11111111
________ ________ 77777777 66666666 55555555 44444444 33333333 22222222
________ ________ ________ 77777777 66666666 55555555 44444444 33333333
________ ________ ________ ________ 77777777 66666666 55555555 44444444
________ ________ ________ ________ ________ 77777777 66666666 55555555
________ ________ ________ ________ ________ ________ 77777777 66666666
________ ________ ________ ________ ________ ________ _______\_ 77777777

56bit右シフト

________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ _______\_
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000

8bitのベクトルが得られました。

1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1

を掛ける

________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ 77777777 66666666 55555555 44444444 33333333 22222222 11111111
>>>
00000000 ________ 77777777 66666666 55555555 44444444 33333333 22222222
11111111 00000000 ________ 77777777 66666666 55555555 44444444 33333333
22222222 11111111 00000000 ________ 77777777 66666666 55555555 44444444
33333333 22222222 11111111 00000000 ________ 77777777 66666666 55555555
44444444 33333333 22222222 11111111 00000000 ________ 77777777 66666666
55555555 44444444 33333333 22222222 11111111 00000000 ________ 77777777
66666666 55555555 44444444 33333333 22222222 11111111 00000000 _______\_
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000

ビットマスク

00000000 ________ ________ ________ ________ ________ ________ ________
11111111 ________ ________ ________ ________ ________ ________ ________
22222222 ________ ________ ________ ________ ________ ________ ________
33333333 ________ ________ ________ ________ ________ ________ ________
44444444 ________ ________ ________ ________ ________ ________ ________
55555555 ________ ________ ________ ________ ________ ________ ________
66666666 ________ ________ ________ ________ ________ ________ ________
77777777 ________ ________ ________ ________ ________ ________ _______\_

7-nビット右シフト

0_______ _0______ __0_____ ___0____ ____0___ _____0__ ______0_ _______0
1_______ _1______ __1_____ ___1____ ____1___ _____1__ ______1_ _______1
2_______ _2______ __2_____ ___2____ ____2___ _____2__ ______2_ _______2
3_______ _3______ __3_____ ___3____ ____3___ _____3__ ______3_ _______3
4_______ _4______ __4_____ ___4____ ____4___ _____4__ ______4_ _______4
5_______ _5______ __5_____ ___5____ ____5___ _____5__ ______5_ _______5
6_______ _6______ __6_____ ___6____ ____6___ _____6__ ______6_ _______6
7_______ _7______ __7_____ ___7____ ____7___ _____7__ ______7_ _____\_\_7

元の盤面上の位置に復元されました。

左上右下方向

元の盤面。nは (y座標 - x座標) (mod 8)。

!07-07-07-07-07-07-07-07 !16-16-16-16-16-16-16-16 !25-25-25-25-25-25-25-25 !34-34-34-34-34-34-34-34 !43-43-43-43-43-43-43-43 !52-52-52-52-52-52-52-52 !61-61-61-61-61-61-61-61 !70-70-70-70-70-70-70-70
!77-77-77-77-77-77-77-77 !06-06-06-06-06-06-06-06 !15-15-15-15-15-15-15-15 !24-24-24-24-24-24-24-24 !33-33-33-33-33-33-33-33 !42-42-42-42-42-42-42-42 !51-51-51-51-51-51-51-51 !60-60-60-60-60-60-60-60
!67-67-67-67-67-67-67-67 !76-76-76-76-76-76-76-76 !05-05-05-05-05-05-05-05 !14-14-14-14-14-14-14-14 !23-23-23-23-23-23-23-23 !32-32-32-32-32-32-32-32 !41-41-41-41-41-41-41-41 !50-50-50-50-50-50-50-50
!57-57-57-57-57-57-57-57 !66-66-66-66-66-66-66-66 !75-75-75-75-75-75-75-75 !04-04-04-04-04-04-04-04 !13-13-13-13-13-13-13-13 !22-22-22-22-22-22-22-22 !31-31-31-31-31-31-31-31 !40-40-40-40-40-40-40-40
!47-47-47-47-47-47-47-47 !56-56-56-56-56-56-56-56 !65-65-65-65-65-65-65-65 !74-74-74-74-74-74-74-74 !03-03-03-03-03-03-03-03 !12-12-12-12-12-12-12-12 !21-21-21-21-21-21-21-21 !30-30-30-30-30-30-30-30
!37-37-37-37-37-37-37-37 !46-46-46-46-46-46-46-46 !55-55-55-55-55-55-55-55 !64-64-64-64-64-64-64-64 !73-73-73-73-73-73-73-73 !02-02-02-02-02-02-02-02 !11-11-11-11-11-11-11-11 !20-20-20-20-20-20-20-20
!27-27-27-27-27-27-27-27 !36-36-36-36-36-36-36-36 !45-45-45-45-45-45-45-45 !54-54-54-54-54-54-54-54 !63-63-63-63-63-63-63-63 !72-72-72-72-72-72-72-72 !01-01-01-01-01-01-01-01 !10-10-10-10-10-10-10-10
!17-17-17-17-17-17-17-17 !26-26-26-26-26-26-26-26 !35-35-35-35-35-35-35-35 !44-44-44-44-44-44-44-44 !53-53-53-53-53-53-53-53 !62-62-62-62-62-62-62-62 !71-71-71-71-71-71-71-71 !00-00-00-00-00-00-00-00

n×8ビット右循環シフト

!77-67-57-47-37-27-17-07 !06-76-66-56-46-36-26-16 !15-05-75-65-55-45-35-25 !24-14-04-74-64-54-44-34 !33-23-13-03-73-63-53-43 !42-32-22-12-02-72-62-52 !51-41-31-21-11-01-71-61 !60-50-40-30-20-10-00-70
!67-57-47-37-27-17-07-77 !76-66-56-46-36-26-16-06 !05-75-65-55-45-35-25-15 !14-04-74-64-54-44-34-24 !23-13-03-73-63-53-43-33 !32-22-12-02-72-62-52-42 !41-31-21-11-01-71-61-51 !50-40-30-20-10-00-70-60
!57-47-37-27-17-07-77-67 !66-56-46-36-26-16-06-76 !75-65-55-45-35-25-15-05 !04-74-64-54-44-34-24-14 !13-03-73-63-53-43-33-23 !22-12-02-72-62-52-42-32 !31-21-11-01-71-61-51-41 !40-30-20-10-00-70-60-50
!47-37-27-17-07-77-67-57 !56-46-36-26-16-06-76-66 !65-55-45-35-25-15-05-75 !74-64-54-44-34-24-14-04 !03-73-63-53-43-33-23-13 !12-02-72-62-52-42-32-22 !21-11-01-71-61-51-41-31 !30-20-10-00-70-60-50-40
!37-27-17-07-77-67-57-47 !46-36-26-16-06-76-66-56 !55-45-35-25-15-05-75-65 !64-54-44-34-24-14-04-74 !73-63-53-43-33-23-13-03 !02-72-62-52-42-32-22-12 !11-01-71-61-51-41-31-21 !20-10-00-70-60-50-40-30
!27-17-07-77-67-57-47-37 !36-26-16-06-76-66-56-46 !45-35-25-15-05-75-65-55 !54-44-34-24-14-04-74-64 !63-53-43-33-23-13-03-73 !72-62-52-42-32-22-12-02 !01-71-61-51-41-31-21-11 !10-00-70-60-50-40-30-20
!17-07-77-67-57-47-37-27 !26-16-06-76-66-56-46-36 !35-25-15-05-75-65-55-45 !44-34-24-14-04-74-64-54 !53-43-33-23-13-03-73-63 !62-52-42-32-22-12-02-72 !71-61-51-41-31-21-11-01 !00-70-60-50-40-30-20-10
!07-77-67-57-47-37-27-17 !16-06-76-66-56-46-36-26 !25-15-05-75-65-55-45-35 !34-24-14-04-74-64-54-44 !43-33-23-13-03-73-63-53 !52-42-32-22-12-02-72-62 !61-51-41-31-21-11-01-71 !70-60-50-40-30-20-10-00

ビットマスク

77777777 ________ ________ ________ ________ ________ ________ ________
________ 66666666 ________ ________ ________ ________ ________ ________
________ ________ 55555555 ________ ________ ________ ________ ________
________ ________ ________ 44444444 ________ ________ ________ ________
________ ________ ________ ________ 33333333 ________ ________ ________
________ ________ ________ ________ ________ 22222222 ________ ________
________ ________ ________ ________ ________ ________ 11111111 ________
________ ________ ________ ________ ________ ________ _______\_ 00000000

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

を掛ける

________ ________ ________ ________ ________ ________ ________ ________
77777777 ________ ________ ________ ________ ________ ________ ________
77777777 66666666 ________ ________ ________ ________ ________ ________
77777777 66666666 55555555 ________ ________ ________ ________ ________
77777777 66666666 55555555 44444444 ________ ________ ________ ________
77777777 66666666 55555555 44444444 33333333 ________ ________ ________
77777777 66666666 55555555 44444444 33333333 22222222 ________ ________
77777777 66666666 55555555 44444444 33333333 22222222 11111111 ________
>>>
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
________ 66666666 55555555 44444444 33333333 22222222 11111111 00000000
________ ________ 55555555 44444444 33333333 22222222 11111111 00000000
________ ________ ________ 44444444 33333333 22222222 11111111 00000000
________ ________ ________ ________ 33333333 22222222 11111111 00000000
________ ________ ________ ________ ________ 22222222 11111111 00000000
________ ________ ________ ________ ________ ________ 11111111 00000000
________ ________ ________ ________ ________ ________ _______\_ 00000000

56bit右シフト

________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
<<<
________ 66666666 55555555 44444444 33333333 22222222 11111111 00000000
________ ________ 55555555 44444444 33333333 22222222 11111111 00000000
________ ________ ________ 44444444 33333333 22222222 11111111 00000000
________ ________ ________ ________ 33333333 22222222 11111111 00000000
________ ________ ________ ________ ________ 22222222 11111111 00000000
________ ________ ________ ________ ________ ________ 11111111 00000000
________ ________ ________ ________ ________ ________ ________ 00000000
________ ________ ________ ________ ________ ________ ________ _______\_

8bitのベクトルが得られました。

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

を掛ける

77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000

ビットマスク

77777777 ________ ________ ________ ________ ________ ________ ________
________ 66666666 ________ ________ ________ ________ ________ ________
________ ________ 55555555 ________ ________ ________ ________ ________
________ ________ ________ 44444444 ________ ________ ________ ________
________ ________ ________ ________ 33333333 ________ ________ ________
________ ________ ________ ________ ________ 22222222 ________ ________
________ ________ ________ ________ ________ ________ 11111111 ________
________ ________ ________ ________ ________ ________ _______\_ 00000000

n×8ビット左循環シフト

_______7 ______6_ _____5__ ____4___ ___3____ __2_____ _1______ 0_______
7_______ _______6 ______5_ _____4__ ____3___ ___2____ __1_____ _0______
_7______ 6_______ _______5 ______4_ _____3__ ____2___ ___1____ __0_____
__7_____ _6______ 5_______ _______4 ______3_ _____2__ ____1___ ___0____
___7____ __6_____ _5______ 4_______ _______3 ______2_ _____1__ ____0___
____7___ ___6____ __5_____ _4______ 3_______ _______2 ______1_ _____0__
_____7__ ____6___ ___5____ __4_____ _3______ 2_______ _______1 ______0_
______7_ _____6__ ____5___ ___4____ __3_____ _2______ 1_______ _____\_\_0

元の盤面上の位置に復元されました。

左上右下方向

元の盤面。nは (y座標 + x座標 - 7) (mod 8)。

!77-77-77-77-77-77-77-77 !66-66-66-66-66-66-66-66 !55-55-55-55-55-55-55-55 !44-44-44-44-44-44-44-44 !33-33-33-33-33-33-33-33 !22-22-22-22-22-22-22-22 !11-11-11-11-11-11-11-11 !00-00-00-00-00-00-00-00
!67-67-67-67-67-67-67-67 !56-56-56-56-56-56-56-56 !45-45-45-45-45-45-45-45 !34-34-34-34-34-34-34-34 !23-23-23-23-23-23-23-23 !12-12-12-12-12-12-12-12 !01-01-01-01-01-01-01-01 !70-70-70-70-70-70-70-70
!57-57-57-57-57-57-57-57 !46-46-46-46-46-46-46-46 !35-35-35-35-35-35-35-35 !24-24-24-24-24-24-24-24 !13-13-13-13-13-13-13-13 !02-02-02-02-02-02-02-02 !71-71-71-71-71-71-71-71 !60-60-60-60-60-60-60-60
!47-47-47-47-47-47-47-47 !36-36-36-36-36-36-36-36 !25-25-25-25-25-25-25-25 !14-14-14-14-14-14-14-14 !03-03-03-03-03-03-03-03 !72-72-72-72-72-72-72-72 !61-61-61-61-61-61-61-61 !50-50-50-50-50-50-50-50
!37-37-37-37-37-37-37-37 !26-26-26-26-26-26-26-26 !15-15-15-15-15-15-15-15 !04-04-04-04-04-04-04-04 !73-73-73-73-73-73-73-73 !62-62-62-62-62-62-62-62 !51-51-51-51-51-51-51-51 !40-40-40-40-40-40-40-40
!27-27-27-27-27-27-27-27 !16-16-16-16-16-16-16-16 !05-05-05-05-05-05-05-05 !74-74-74-74-74-74-74-74 !63-63-63-63-63-63-63-63 !52-52-52-52-52-52-52-52 !41-41-41-41-41-41-41-41 !30-30-30-30-30-30-30-30
!17-17-17-17-17-17-17-17 !06-06-06-06-06-06-06-06 !75-75-75-75-75-75-75-75 !64-64-64-64-64-64-64-64 !53-53-53-53-53-53-53-53 !42-42-42-42-42-42-42-42 !31-31-31-31-31-31-31-31 !20-20-20-20-20-20-20-20
!07-07-07-07-07-07-07-07 !76-76-76-76-76-76-76-76 !65-65-65-65-65-65-65-65 !54-54-54-54-54-54-54-54 !43-43-43-43-43-43-43-43 !32-32-32-32-32-32-32-32 !21-21-21-21-21-21-21-21 !10-10-10-10-10-10-10-10

n×8ビット右循環シフト

!67-57-47-37-27-17-07-77 !56-46-36-26-16-06-76-66 !45-35-25-15-05-75-65-55 !34-24-14-04-74-64-54-44 !23-13-03-73-63-53-43-33 !12-02-72-62-52-42-32-22 !01-71-61-51-41-31-21-11 !70-60-50-40-30-20-10-00
!57-47-37-27-17-07-77-67 !46-36-26-16-06-76-66-56 !35-25-15-05-75-65-55-45 !24-14-04-74-64-54-44-34 !13-03-73-63-53-43-33-23 !02-72-62-52-42-32-22-12 !71-61-51-41-31-21-11-01 !60-50-40-30-20-10-00-70
!47-37-27-17-07-77-67-57 !36-26-16-06-76-66-56-46 !25-15-05-75-65-55-45-35 !14-04-74-64-54-44-34-24 !03-73-63-53-43-33-23-13 !72-62-52-42-32-22-12-02 !61-51-41-31-21-11-01-71 !50-40-30-20-10-00-70-60
!37-27-17-07-77-67-57-47 !26-16-06-76-66-56-46-36 !15-05-75-65-55-45-35-25 !04-74-64-54-44-34-24-14 !73-63-53-43-33-23-13-03 !62-52-42-32-22-12-02-72 !51-41-31-21-11-01-71-61 !40-30-20-10-00-70-60-50
!27-17-07-77-67-57-47-37 !16-06-76-66-56-46-36-26 !05-75-65-55-45-35-25-15 !74-64-54-44-34-24-14-04 !63-53-43-33-23-13-03-73 !52-42-32-22-12-02-72-62 !41-31-21-11-01-71-61-51 !30-20-10-00-70-60-50-40
!17-07-77-67-57-47-37-27 !06-76-66-56-46-36-26-16 !75-65-55-45-35-25-15-05 !64-54-44-34-24-14-04-74 !53-43-33-23-13-03-73-63 !42-32-22-12-02-72-62-52 !31-21-11-01-71-61-51-41 !20-10-00-70-60-50-40-30
!07-77-67-57-47-37-27-17 !76-66-56-46-36-26-16-06 !65-55-45-35-25-15-05-75 !54-44-34-24-14-04-74-64 !43-33-23-13-03-73-63-53 !32-22-12-02-72-62-52-42 !21-11-01-71-61-51-41-31 !10-00-70-60-50-40-30-20
!77-67-57-47-37-27-17-07 !66-56-46-36-26-16-06-76 !55-45-35-25-15-05-75-65 !44-34-24-14-04-74-64-54 !33-23-13-03-73-63-53-43 !22-12-02-72-62-52-42-32 !11-01-71-61-51-41-31-21 !00-70-60-50-40-30-20-10

ビットマスク

________ ________ ________ ________ ________ ________ ________ 00000000
________ ________ ________ ________ ________ ________ 11111111 ________
________ ________ ________ ________ ________ 22222222 ________ ________
________ ________ ________ ________ 33333333 ________ ________ ________
________ ________ ________ 44444444 ________ ________ ________ ________
________ ________ 55555555 ________ ________ ________ ________ ________
________ 66666666 ________ ________ ________ ________ ________ ________
77777777 ________ ________ ________ ________ ________ ________ _______\_

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

を掛ける

________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ 00000000
________ ________ ________ ________ ________ ________ 11111111 00000000
________ ________ ________ ________ ________ 22222222 11111111 00000000
________ ________ ________ ________ 33333333 22222222 11111111 00000000
________ ________ ________ 44444444 33333333 22222222 11111111 00000000
________ ________ 55555555 44444444 33333333 22222222 11111111 00000000
________ 66666666 55555555 44444444 33333333 22222222 11111111 00000000
>>>
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 ________
77777777 66666666 55555555 44444444 33333333 22222222 ________ ________
77777777 66666666 55555555 44444444 33333333 ________ ________ ________
77777777 66666666 55555555 44444444 ________ ________ ________ ________
77777777 66666666 55555555 ________ ________ ________ ________ ________
77777777 66666666 ________ ________ ________ ________ ________ ________
77777777 ________ ________ ________ ________ ________ ________ _______\_

56bit右シフト

________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ ________
________ ________ ________ ________ ________ ________ ________ _______\_
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000

8bitのベクトルが得られました。

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

を掛ける

77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000
77777777 66666666 55555555 44444444 33333333 22222222 11111111 00000000

ビットマスク

________ ________ ________ ________ ________ ________ ________ 00000000
________ ________ ________ ________ ________ ________ 11111111 ________
________ ________ ________ ________ ________ 22222222 ________ ________
________ ________ ________ ________ 33333333 ________ ________ ________
________ ________ ________ 44444444 ________ ________ ________ ________
________ ________ 55555555 ________ ________ ________ ________ ________
________ 66666666 ________ ________ ________ ________ ________ ________
77777777 ________ ________ ________ ________ ________ ________ _______\_

n×8ビット左循環シフト

7_______ _6______ __5_____ ___4____ ____3___ _____2__ ______1_ _______0
_7______ __6_____ ___5____ ____4___ _____3__ ______2_ _______1 0_______
__7_____ ___6____ ____5___ _____4__ ______3_ _______2 1_______ _0______
___7____ ____6___ _____5__ ______4_ _______3 2_______ _1______ __0_____
____7___ _____6__ ______5_ _______4 3_______ _2______ __1_____ ___0____
_____7__ ______6_ _______5 4_______ _3______ __2_____ ___1____ ____0___
______7_ _______6 5_______ _4______ __3_____ ___2____ ____1___ _____0__
_______7 6_______ _5______ __4_____ ___3____ ____2___ _____1__ ______0\_

元の盤面上の位置に復元されました。

画像生成の実装

ここまでの画像は、一旦テキスト形式として元になるデータを記述しておいて、Parsecでデータを読み取って適当なデータ構造に格納し、それをDiagramsで処理して描画するという形で生成しています。なお、元になるデータはどうせプログラムの実行結果を示すものなのだから、ビットボードの実際の実装を走らせることで自動生成することも考えたのですが、オーバーフローやアンダーフローの情報が消えてしまうので手書きを選びました。なおテキスト形式のデータは画像のalt属性としてこっそり埋め込んでいます。

ライブラリのDiagramsに関してですが、関数型プログラミングらしいcomposableなやりかたで画像を構築できるのは中々小気味良いと感じました。ただ、APIが可能な限り型クラスで抽象化されているので、どういう型クラスで抽象化されているのか慣れるまでが大変です。 公式のチュートリアル を見れば雰囲気は分かった気になるのですが、チュートリアルに現れない望みの図形を描こうとすると結局Haddockのドキュメントや実装のソース自体を読まないとどうにもなりません。ドキュメントに嘘は見当たらないし、ソースコードもバックエンドの操作を扱う部分はいざ知らないが比較的高級なコンビネータ部分は読みやすかったので、悪くないとは思います。

以下がソースコードです。 drawBoardWithFlow 関数以下が、Diagramsによる描画処理となります。

{-# LANGUAGE GeneralizedNewtypeDeriving, FlexibleContexts, TypeFamilies #-}

import Control.Applicative
import Data.Foldable (foldMap)
import Data.Monoid
import System.IO (hPutStrLn, stderr)
import System.Environment (getArgs)

import Data.Array

import Text.Parsec.String
import Text.Parsec hiding ((<|>))
import Data.Char (digitToInt)

import Data.Colour.CIE (cieLAB, Chromaticity, mkChromaticity)
import Diagrams.Backend.Cairo
import Diagrams.TwoD.Size
import Diagrams.TwoD.Text
import Diagrams.Prelude hiding (position, (<>))

-- types
data BoardRange = R0 | R1 | R2 | R3 | R4 | R5 | R6 | R7 deriving (Ix, Enum, Bounded, Ord, Eq, Show)

newtype LaneIx = LaneIx BoardRange deriving (Ix, Enum, Bounded, Ord, Eq, Show)
newtype BoardRowIx = BoardRowIx BoardRange deriving (Ix, Enum, Bounded, Ord, Eq, Show)
newtype BoardColIx = BoardColIx BoardRange deriving (Ix, Enum, Bounded, Ord, Eq, Show)
newtype ColorRowIx = ColorRowIx BoardRange deriving (Ix, Enum, Bounded, Ord, Eq, Show)
newtype ColorColIx = ColorColIx BoardRange deriving (Ix, Enum, Bounded, Ord, Eq, Show)

data Position = Position (Array LaneIx (Maybe (ColorRowIx, ColorColIx)))
data Board = Board (Array BoardRowIx (Array BoardColIx Position))
data BoardWithFlow = BoardWithFlow (Maybe Board) Board (Maybe Board)

-- main
main :: IO ()
main = do
  inputPath <- head <$> getArgs
  res <- parseFromFile boardWithFlow inputPath
  case res of
    Right brdF -> renderCairo (inputPath ++ ".svg") (mkSizeSpec (Just 328) Nothing) $ drawBoardWithFlow brdF
    Left err -> hPutStrLn stderr $ show err

-- parser
arrayRange :: (Bounded a, Ix a) => (a, a)
arrayRange = (minBound, maxBound)

boardWithFlow = BoardWithFlow <$> optionMaybe (try (board <* ovfSep)) <*> board <*> optionMaybe (try (udfSep *> board))

ovfSep = string ">>>" <* newline
udfSep = string "<<<" <* newline

board = Board . listArray arrayRange <$> count 8 line

line = listArray arrayRange <$> count 8 position <* newline

position = Position <$> (numbers <|> strictNumbers) <* skipMany (char ' ')

numbers = listArray arrayRange . zipWith (\i -> ((,) (toEnum i) <$>)) [0 .. 7] . reverse <$> count 8 numberMaybe
strictNumbers = (listArray arrayRange . reverse <$>) $ (:) <$> (char '!' *> strictNumberMaybe) <*> count 7 (char '-' *> strictNumberMaybe)

strictNumberMaybe = dontCare *> dontCare <|> Just <$> ((,) <$> number <*> number)
numberMaybe = dontCare <|> Just <$> number
number :: Enum e => Parser e -- deal with monomorphic restriction
number = toEnum . digitToInt <$> oneOf ['0' .. '7']
dontCare = char '_' *> pure Nothing

-- drawer
maybeHomo :: Monoid b => (a -> b) -> Maybe a -> b
maybeHomo f Nothing = mempty
maybeHomo f (Just a) = f a

drawBoardWithFlow :: (Backend b R2, Renderable (Path R2) b, Renderable Text b) => BoardWithFlow -> Diagram b R2
drawBoardWithFlow (BoardWithFlow mOvf brd mUdf) =
  strutY 0.5
  ===
  maybeHomo (\ovf ->
    alignL (strutX 0.5 ||| (alignB $ drawBoard (1/128) white ovf) ||| strutX 0.3 ||| (moveOriginBy (0 ^& (-0.3)) . font "Futura" . fontSize 0.8 $ baselineText "overflow"))
    ===
    alignL (padY 5 . lw 0 . fc black $ roundedRect 20.5 0.125 0.06125)
  ) mOvf
  ===
  alignL (strutX 0.5 ||| (drawBoard (1/16) white brd) ||| strutX 4)
  ===
  maybeHomo (\udf ->
    alignL (padY 5 . lw 0 . fc black $ roundedRect 20.5 0.125 0.06125)
    ===
    alignL (strutX 0.5 ||| (alignT $ drawBoard (1/128) white udf) ||| strutX 0.3 ||| (moveOriginBy (0 ^& 0.3) . font "Futura" . fontSize 0.8 $ topLeftText "underflow"))
  ) mUdf
  ===
  strutY 0.5

drawBoard :: (Backend b R2, Renderable (Path R2) b) => Double -> Colour Double -> Board -> Diagram b R2
drawBoard bdw bgc (Board board) = centerXY $ g (elems board)
  where
    g = foldr (\line e -> f (elems line) === e) mempty
    f = foldr (\pos e -> drawPosition bdw bgc pos ||| e) mempty

drawPosition :: (Backend b R2, Renderable (Path R2) b) => Double -> Colour Double -> Position -> Diagram b R2
drawPosition bdw bgc (Position ary) = bg bgc $ lw bdw (square 2) <> item
  where
    item = foldMap (\(li, mrc) -> maybe mempty (\(ri, ci) -> drawPiece li ri ci) $ mrc) $ assocs ary

drawPiece :: (Backend b R2, Renderable (Path R2) b) => LaneIx -> ColorRowIx -> ColorColIx -> Diagram b R2
drawPiece li ri ci = guard <> piece
  where
    li' = fromEnum li
    ri' = fromEnum ri
    ps = [1 ^& 0, 1 ^& 1, 0 ^& 1, (-1) ^& 1, (-1) ^& 0, (-1) ^& (-1), 0 ^& (-1), 1 ^& (-1), 1 ^& 0]
    piece = lw (1 / 128) . lc black . fc (pieceColor ri ci) $ strokeLocLoop . mapLoc closeLine $ fromVertices [origin, ps !! li', ps !! (li'+1)]
    guard | fromEnum li' == ri' = mempty
          | otherwise = lw 0 . fc neutral . strokeLocLoop . mapLoc closeLine $ fromVertices [0.375 *. (ps !! li'), 0.375 *. (ps !! (li'+1)), 0.625 *. (ps !! (li'+1)), 0.625 *. (ps !! li')]

-- CIELAB: tuned parameters to make it viewable on sRGB monitor (tested on MacBook Air)
pieceColor :: ColorRowIx -> ColorColIx -> Colour Double
pieceColor ri ci = cieLAB whitePointD65 l (sat * cos deg) (sat * sin deg)
  where
    l = 85 - fromIntegral (fromEnum ci) * 6.5
    deg = pi * [0.03, 0.28, 0.53, 0.72, 1.00, 1.28, 1.63, 1.80] !! fromEnum ri
    sat = 47

neutral :: Colour Double
neutral = cieLAB whitePointD65 (85 - 3.5 * 6.5) 0 0

whitePointD65 = mkChromaticity 0.31271 0.32902

SVGBackendによってネイティブでSVG画像を出力することもできるのですが、フォントを指定しようと思うとCairoBackendによってcairoを通す必要があります(Futuraを使いたかったのです)。OS Xへのcairoのインストールは、まずXQuartzをインストールしてから、ソースコードを普通にmakeすれば大丈夫でした。cairoが入ってしまえば、Diagramsもそのcairoサポートもcabalであっさり入ります。

ParsecとDiagrams以外には特に凝ったライブラリは使わずにゴリゴリと書いています。Diagramsを使ったコーディングがだいたいどんな感じかという雰囲気は出ていると思います。図形はモノイドであって、モノイド同士の二項演算によって重ねていけるのは結構面白いです。

ビットボードの実装

載せるとあまりに記事が長くなりそうなので割愛します。 https://github.com/grafi-tt/tatsuki/blob/2f85835c5aab83c3c60999a37a51fa4794c84285/Reversi/Tatsuki/BitBoard.hs を見てください。暗号的ですが。

ビット演算に記号が無いといくらなんでも実装がきついものの、一般的なビット演算の記号はモナドの記号と被るし循環シフトの記号も考えないといけないので、いっそあやしいUnicodeの記号を使っているところが面白い点です。GHC7.6.xでは循環シフト命令の出力がサポートされていない https://ghc.haskell.org/trac/ghc/ticket/7337 のは残念です。LLVMバックエンドではStrength Reductionで抽出されるらしいですが。

blog comments powered by Disqus