会社blogの方にこんな記事やらこんな記事を書いて、思考ルーチンやら解法アルゴリズムが好物であることがばれたので、西尾さんに「次、これなんてどう？」と勧められたのが「ブロックス・デュオ」。
GPCC で「ブロックス・デュオ」のプログラム対戦の問題も出ているそうで。ふむふむ。
ざっくり考えてみた範囲では、前半は定石ベース、中盤は評価関数、終盤は全数探索による寄せというところかなあ。
前半は可能な手が異様に多く、この手のボードゲームとしてはちょっと珍しい？*1
逆に、終盤は手がほとんど無くなり、脳内全数探索ができてしまうくらい収束が早い。
そして、双方が２１ピースしか持たないので、高々４２手で探索が完了する。
で、今日ちょうど西尾さんとお出かけの際につらつらしゃべってみて、「やっぱ一度全数探索に挑戦してみたいのう」という方向で意見が一致（ブロックス経験値ゼロだから、定石とか全然わからんし）。
西尾さんは当然 Python なので、じゃあ俺は Ruby で書いてみよう（え？ Erlang？ むにゃむにゃもごもご）。
最初の２手と３手目以降はピースの置き方が全然違うので、まずは２手目までを幅優先探索するコードを書いてみた。こんな感じ。
pieces = <<PIECES */ **/ ***/1 ** *./2 ****/1 *** *../2 *** .*./3 **. .**/4 ** **/5 *****/1 **** *.../2 **** .*../3 *** **./4 *** *.*/5 ***. ..**/6 **. .** .*./7 **. .** ..*/8 **. .*. .**/9 .*. *** .*./10 *** *.. *../11 *** .*. .*./12 PIECES def coordinate(st) piece = [] y=0 st.each do |line| (0..line.length-1).each do |x| piece << [x, y] if line[x]==42 end y+=1 end piece end def hsymmetry(piece) h = piece.map{|coor| coor[0]}.max piece.map{|coor| [h-coor[0], coor[1]]} end def rotate(piece) v = piece.map{|coor| coor[1]}.max piece.map{|coor| [v-coor[1], coor[0]]} end def mirror(piece) piece.map{|coor| [coor[1], coor[0]]} end def create_piece_list(pieces) id = 0 pieces.split(/\/\d*\n/).inject({}) do |m, piece| coor = coordinate(piece) variation = [t=coor, u=hsymmetry(coor)] variation << t = rotate(t) variation << t = rotate(t) variation << rotate(t) variation << u = rotate(u) variation << u = rotate(u) variation << rotate(u) m[id] = variation.map{|t|t.sort}.uniq id+=1 m end end def first_turn(start_posi, pieces, mirror_flag) list = [] pieces.each do |id, variation| symmetry = [] variation.each do |piece| self_mirror_flag = false if mirror_flag next if symmetry.include?(piece) mir = mirror(piece).sort self_mirror_flag = (mir == piece) symmetry << mir end piece.each do |offset| posi = piece.map{|coor| [coor[0]+start_posi[0]-offset[0], coor[1]+start_posi[1]-offset[1]]} list << [id, posi, self_mirror_flag] end end end list end def create_first_list(pieces) rest_pieces = create_piece_list(pieces) list = first_turn([4, 4], rest_pieces, true) #puts list.length list.each do |item| id1, posi1, self_mirror_flag = item first_turn([9, 9], rest_pieces, self_mirror_flag).each do |id2, posi2, dummy| puts "#{[id1,posi1,id2,posi2].inspect}" end end end create_first_list(pieces)
ピースを座標化して回転対称とってズバズバ置いてみたという単純なプログラム。
ここから１手目が 225 通り、２手目が 86346 通りであることがわかった（盤面対角線対称は除いている）。
「１手目がおそらく４００くらい、鏡像を同一視して半分の２００。２手目はほとんど対称とならないので４００のまま。かけ算して８万くらいかなあ」と思っていたので、まさにドンぴしゃ！ って喜んでる場合じゃない。どひゃー。
もしも仮に３手目以降がおのおの６０秒で全数探索できたとしても（まあまずありえないが）、１日は 86400 秒なので、６０日(笑)。
いきなり全数探索は厳しめなようである……*2
