Komakuro

English/日本語

将棋の数学的定義:駒の動きと局面の遷移

定義「有限列の表記」集合S上の有限列s1, s2, ... , snを[s1, s2, ... , sn]と表記します。
s=[s1, s2, ... , sn]とするとき、s(i)=siと定義します。
また、nをこの有限列の長さといいます。
ちなみに、数学的に厳密に言うと、S上の有限列とは、「ℕの部分集合{1, 2, ... , n}からSへの写像」です。
このシリーズではそこまで深く考えなくでもいいですが。
定義「動き」Kind×Side×Turnの元に対してℤ×ℤ上の有限列の集合 をわりあてる写像Moveを次のように定義します。
Move(歩, 不成, 先手)={ [(0,-1)] }
Move(歩, 不成, 後手)={ [(0,1)] }
Move(香, 不成, 先手)={ [(0,-1),(0,-2),...,(0,-8)] }
Move(香, 不成, 後手)={ [(0,1),(0,2),...,(0,8)] }
Move(桂, 不成, 先手)={ [(-1,-2)], [(1,-2)] }
Move(桂, 不成, 後手)={ [(-1,2)], [(1,2)] }
Move(銀, 不成, 先手)={ [(1,-1)], [(0,-1)], [(-1,-1)], [(-1,1)], [(1,1)] }
Move(銀, 不成, 後手)={ [(-1,1)], [(0,1)], [(1,1)], [(1,-1)], [(-1,-1)] }
Move(金, 不成, 先手)=Move(歩, 成, 先手)=Move(香, 成, 先手)=Move(桂, 成, 先手)=Move(銀, 成, 先手)={ [(1,0)], [(1,-1)], [(0,-1)], [(-1,-1)], [(-1,0)], [(0,1)] }
Move(金, 不成, 後手)=Move(歩, 成, 後手)=Move(香, 成, 後手)=Move(桂, 成, 後手)=Move(銀, 成, 後手)={ [(-1,0)], [(-1,1)], [(0,1)], [(1,1)], [(1,0)], [(0,-1)] }
Move(角, 不成, 先手)=Move(角, 不成, 後手)={ [(-1,-1),(-2,-2),...,(-8,-8)], [(-1,1),(-2,2),...,(-8,8)], [(1,1),(2,2),...,(8,8)], [(1,-1),(2,-2),...,(8,-8)] }
Move(角, 成, 先手)=Move(角, 成, 後手)=Move(角, 不成, 先手)∪{[(-1,0)], [(1,0)], [(0,-1)], [(0,1)]}
Move(飛, 不成, 先手)=Move(飛, 不成, 後手)={ [(-1,0),(-2,0),...,(-8,0)], [(1,0),(2,0),...,(8,0)], [(0,-1),(0,-2),...,(0,-8)], [(0,1),(0,2),...,(0,8)] }
Move(飛, 成, 先手)=Move(飛, 成, 後手)=Move(飛, 不成, 先手)∪{[(-1,-1)], [(-1,1)], [(1,1)], [(1,-1)]}
Move(玉, 不成, 先手)=Move(玉, 不成, 後手)={ [(-1,-1)], [(-1,0)], [(-1,1)], [(0,1)], [(1,1)], [(1,0)], [(1,-1)], [(0,-1)] }
Move(金, 成, 先手)=Move(金, 成, 後手)=Move(玉, 成, 先手)=Move(玉, 成, 後手)=∅
定義「駒の利き」state=(post,t)∈Stateとp∈Pieceと(c'',r'')∈Column×Rowが次の条件をみたすとき、stateにおいて、pは(c'',r'')に利いているといいます。
条件: c∈Column、r∈Row、s∈Side、o∈Turnがあってpost(p)=((c,r,s),o)であり、m∈Move(kind(p),s,o)とn∈ℕがあって、以下の条件をみたす。
(1)途中に駒がない
任意の1≦i<nなる自然数iに対して、(c,r)+m(i)=(c',r')とおくと、任意のp'∈Piece, s'∈Side, o'∈Turnに対してpost(p')≠((c',r',s'),o')
(2)
(c,r)+m(n)=(c'',r'')
定理「駒の利きの単一性」state=(post,t)∈Stateとp∈Pieceと(c'',r'')∈Column×Rowとします。
stateにおいて、pが(c'',r'')に利いていることと、次の条件は同値です。
条件: c∈Column、r∈Row、s∈Side、o∈Turnがあってpost(p)=((c,r,s),o)であり、唯一つのm∈Move(kind(p),s,o)と唯一つのn∈ℕがあって、以下の条件をみたす。
(1)途中に駒がない
任意の1≦i<nなる自然数iに対して、(c,r)+m(i)=(c',r')とおくと、任意のp'∈Piece, s'∈Side, o'∈Turnに対してpost(p')≠((c',r',s'),o')
(2)
(c,r)+m(n)=(c'',r'')
証明Moveの定義を見れば、任意のk∈Kind,s∈Side,o∈Turnに対し、m,m'∈Move(k,s,o)、n,n'∈ℕに対してm≠m'またはn≠n'ならばm(n)≠m'(n')であることがすぐにわかります。
したがってこのとき、(c,r)+m(n)=(c'',r'')と(c,r)+m'(n')=(c'',r'')は同時に成立しません。
定義「β1遷移」state,state'∈Stateに対し、次の条件がなりたつとき、stateからstate'にβ1遷移可能であるといい、stateβ1state'とかきます。
条件: state=(post,t),state'=(post',t')とおくと、(1)かつ「(2)または(3)」が成立します。
(1)t≠t'
(2)あるp∈Piece、c,c'∈Column、r,r'∈Row、s∈Sideがあって、post(p)=((c,r,s),t)であり、m∈Move(kind(p),s,o)とn∈ℕがあって、以下の条件をみたす。
(2-1)stateにおいてpは(c',r')に利いている
(2-2)任意のp'∈Pieceに対して、あるs'∈Side, o'∈Turnがあってpost(p')=((c',r',s'),o')ならば、o'=t'であり、post'(p')=(stand,t)
このようなs',o'があるようなp'があるとき、このβ1遷移は(((c,r)の)駒pで)((c',r')の)駒(p')をとる手である、といいます。
(2-3)それ以外の駒は不動
任意のp'∈Pieceに対して、p'≠pかつ、「あるs'∈Side, o'∈Turnがあってpost(p')=((c',r',s'),o')」とならないなら、post'(p')=post(p')
(2-4)動かした駒の動かした後の状態
あるs'∈Sideがあってpost'(p)=((c',r',s'),t)。
s=成 なら s'=成。
s=不成 かつ「『t=先手かつr≧4かつr'≧4』または『t=後手かつr≦6かつr'≦6』」なら、s'=不成
このとき、このβ1遷移は、駒(p)を((c,r)から)((c',r')に)動かす手である、といいます。
(3)持ち駒を打つ場合
あるp∈Piece、c∈Column、r∈Rowがあって、以下がなりたつ
(3-1)pは手番側の持ち駒
post(p)=(stand,t)
(3-2)打ちたいところに駒がない
任意のp'∈Piece、s∈Side、o∈Turnに対して、post(p')≠((c,r,s),o)
(3-3)持ち駒を打った後のその駒の状態
post'(p)=((c,r,不成),t)
(3-4)打った駒以外は不動
任意のp'∈Pieceに対して、p'=pならpost'(p')=post(p')
このとき、このβ1遷移は、駒(p)を((c,r)に)打つ手である、といいます。
stateβ1state'とは要するに、局面stateから局面state'に1手でうつれる、ということです。
定義「β遷移」State上の二項関係β1の反射的推移的閉包をβとかきます。
state,state'∈Stateがstateβstate'であるとき、sからs'にβ遷移可能であるといいます。
stateβstate'とは要するに、局面sから局面s'に0手以上でたどり着ける、ということです。