囲碁棋譜におけるSuffix Arrayを用いた着手記号列のインデックス手法
An Efficient Indexing Method for Go Game Records based on Suffix Array
加藤雄大

アブストラクト

囲碁や将棋,チェスなどのボードゲームでは定石が存在し,定石を用いればある 程度着手の選択肢が狭まる.このように囲碁を学ぶ上で定石,布石,手筋などの手 順を覚えることは不可欠となる.手順を覚える手段は定石書を読む,プロの実戦の 棋譜を見る,棋譜データベースで調べるという手段がある.定石書やプロの棋譜を 用いる手段ではパターンを覚えることは可能だが,囲碁学習者が知りたい手順を直 ちに知ることはできない.また,「囲碁の棋譜でーたべーす 」のような棋譜データ ベースは手順によって棋譜を検索することができるが,問題点として初手からの手 順しか検索できない点が挙げられる.囲碁学習者にとって棋譜の途中の手順であっ ても検索できることが望ましい. 本論文では,囲碁棋譜において入力手順を含む棋譜を検索するためのインデック ス作成手法について説明する.棋譜を検索するには 2 つの方法があり,1 つ目は局面 による棋譜検索,2 つ目は手順による棋譜検索がある.局面による棋譜検索は盤の指 定した範囲を含む棋譜を検索する方法である.局面による検索では Zobrist Hashing と呼ばれる盤上の石の状態をハッシュ値に変換する手法が用いられる.手順による 棋譜検索は指定した手順を含む棋譜を検索する方法である.ここで,手順とは着手 を直列化したものとする.本研究では,手順による棋譜検索を用いる. 本研究では,手順による棋譜検索システムを作成した.システムのインデックス 作成方法は,回転,鏡像,移動,色反転を考慮した符号化方法を用いて棋譜を着手 記号列と呼ばれる文字列に符号化する.この符号化を複数の棋譜に対して行い,得 られた複数の着手記号列から Suffix Array を作成する.Suffix Array を用いることで 文字列を高速に検索でき,Suffix Array 内の類似した文字列は偏って存在するため 1 頻度計算が容易になるという利点がある.入力手順を含む棋譜の検索時には,不連 続な手順を考慮した検索方法を用いて検索の再現率を上げる.システムの検索方法 は,ユーザの入力手順をインデックス作成時と同様の符号化法を用いて着手記号列 に符号化し,Suffix Array を用いて検索する.手順による棋譜検索では,検索された 複数の棋譜から次の着手を読み取ることができる.プロの実戦の棋譜から作成され たデータベースを用いて検索すれば有力な着手を得ることができる.もちろん,定 石,布石の手順も知ることが可能となる.