ただのメモ

他の人に見せても良い方のメモ

5目並べ、4目並べ、戦略拝借

こちらの文献をまとめる。

  • 連珠のルール
    • Free Renju Rule
      • プレイヤーは仮の黒、仮の白としてプレイする。仮の黒、の人は、真ん中に石を置く。
      • 仮の白、の人は、黒石に隣接した位置に石を置く。
      • 仮の黒、の人は、真ん中の5×5格子、の空き場所に石を置く。
      • 仮の白、の人は、白と黒を入れ替えることが出来る
      • 白の人が、4つ目を置く
      • 黒の人は、2つの(非対称の)置ける場所を指定する。
      • 白の人は、そのうち1つを指定し、黒石を置かせる。
      • 6つめ以降は制限無し。
    • Overline
      • 6つ以上の石が連続して並ぶこと。
    • Five
      • 丁度5つの石が連続して並ぶこと。
    • Straight Four
      • 丁度4つの石が連続して並ぶこと。
    • Four
      • 4つの石があって、次に5になれるもの。
      • 連続とは限らない。
        • 3、無し、1
        • 2、無し、2
    • Three
      • 次の一手で、Fourになる。
      • 3つの石
        • 3つ連続
        • 1、無し、2
    • Double Four
      • Fourを2つ以上同時に作ること
    • Double Three
      • Threeを2つ以上同時に作ること。
    • Four Three
      • FourとThreeを同時に作ること。
    • VCF
      • Victory by Consecutive Fours
      • Fourを連続で作って勝つこと
    • VCT
      • Victory by Consecutive Threat
      • Four またはThreeを連続で作って勝こと
    • Fukumi
      • VCFで勝つ恐れのある動き
      • 防御しなければ、負ける
    • Yobi
      • VCFで勝つ恐れのある動き
      • 強制力はない。
        • 防御しなくても耐え得る
  • ここから後は、とても計算量が要る(し、この文献には詳しいコードが書いていない)ので、5目並べの最適戦略を求めるのは、止める。
    • 実際に最適戦略をとって、相手も最適防御を見せたら、47手で終わったよ、という図が文献中にある。
  • このまま、記事を終わるのも、もったいないので、n目並べについて考える。
  • 1目並べは先手必勝。(当たり前)
  • 2目並べも先手必勝。(当たり前)
  • 3目並べも先手必勝。(繋げるだけ)
    • 一般に、n目並べは、n-1個の連続する玉で、両端が空きのものを作れたら、次は片方しか止められないから、自動的に勝利確定
    • 3目並べは、(端っこが有限でないとすると、)1個置いた時点で、どうあがいても、2個連続かつ両端空の状態に持っていかれる。
  • 4目並べは、どうか。
    • さっきの最初の縛りをありで、考えてみると、必勝
      • さっきの縛りとは、
        • 2手目は隣接した箇所に置く
        • 3手目は5×5の格子の中の空き場所に置く。
        • 15×15の板(5目と同じ環境)
      • 縛り無しでも良い。しかし、二手目が無数にあり得るから、探索したことにならない。それでも勝てないから良いが
    • お絵描きする。

最初の配置が縦か横に隣に置かれた場合

f:id:medical-science:20220115015302p:plain

3手目はこうする。

1)次に、相手が緑や紫の位置に置いてきたら、黄色の位置に置いて、2つの1個飛ばしの状況にする。

こうなれば、どっちかは4目並びまで行ける。

f:id:medical-science:20220115015839p:plain

 

2)問題は、(-1,-1)の位置に青色石を置かれた場合である。この場合は、(1,-1)の位置に置く。

f:id:medical-science:20220115020733p:plainその後、緑、紫の位置に置かれなければ、そこに置けば、Straight Threeとなるので、勝ち確定。

ここで、黄色の位置に置かれたらどうなるか、という疑問が湧く。その場合、置かれていない方の黄色の位置に置けば、防御できる。さらに、黄色に置かれることと、紫、緑の筋は関係しないので、議論しなく良い。

最後に、緑か紫が抑えられた場合の話をする。仮に両方抑えられたとしても、以下のようにすれば勝てる。

f:id:medical-science:20220115021314p:plain

(1,1)に置く。これは王手なので、相手は、(3,3)に置かざるを得ない。

そして、緑に置く。すると、Straight Threeが出来上がる。よって勝利。

4手目が(-1,-1)だった時の話は完結。

 

3)4手目がそれ以外の時は、そのまま、Straight Threeを作るだけ。簡単。

 

以上より、2手目が、縦横に隣接する場合は勝てることが分かった。

 

ここからは、斜めに隣接する場合が残る。以下のような配置で攻めることになる。

f:id:medical-science:20220115021746p:plain

これまた、場合分けが必要になるが、結局は勝てる。これの確認は読者に任せることにしよう。(ヒント(?):オレンジのところに青が置いた場合、少し複雑な場合分けが登場する)

上の図のコードは以下。

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
xb = [0,2]
yb = [0,0]
xw = [-1]
yw = [-1]

plt.scatter(xb,yb,color = "red",marker = "o",s = 700)
plt.scatter(xw,yw,color = "blue",marker = "o",s = 700)
plt.xlim(-4,4)
plt.ylim(-4,4)
plt.scatter(-1,0,color = "orange",marker = "o",s = 700)
plt.grid()
plt.show()

 

  • おまけだが、この5目(4目)並べのようなゲームは、一般に(m,n,k) gameと言われる。こちら。
  • (m,n,k)gameについて、より大きなkや、より小さなm,nで先手必勝なら、もとのゲームも先手必勝。という結果が知られている。
    • これは、5目並べが先手必勝なら、4目並べも先手必勝ということを意味する。
  • 戦略拝借論証(m,n,k gameに日本語のWikiよりこちらがわかりやすい) 
    • 後手必勝戦略の存在を仮定し、背理法を用いて証明。
    • 先手が任意の手Xを指す。
    • 先手が後手の振りをして後手必勝戦略をとる。(Xに置いたことを忘れたら、後手)
      • 置こうとしたところに石が無ければ、必勝戦略を取り続ける
      • 再び、Xに置こうとしたとき、すでにXには置いていたので、再び任意の手Yを指し、Yを忘れる。
      • すると、また後手のつもりになって、再び後手必勝戦略をとる
    • 本来の後手が必勝のはずが、先手が必勝になってしまう。
    • これにより、矛盾。よって、後手必勝戦略は無い。

それでは、

Bye-Bye!