iT邦幫忙

1

興趣研究- 跳棋nim game(1)

(本系列為自己有興趣的主題研究,非教學文)
廣義的nim Game定義如下:

  1. 由兩名玩家參與
  2. 兩名玩家輪流對現在的遊戲盤面進行移動(move),可選擇的移動為有限多種
  3. 合法的移動集合只與盤面本身有關,與哪個選手移動無關,與以前的移動無關,亦不會有擲硬幣等隨機因素
  4. 如果輪到某位選手,但他沒有移動可以走了,則該名選手輸。
  5. 假設遊戲經過有限多步之後,必然會到達沒有移動步的盤面

(參考nim遊戲詳解一文)
所以日常常見的遊戲,譬如象棋,就不是nim game,因為紅方只能動紅棋,黑方只能動黑棋。
以下針對自定義nim game進行研究:

1xn棋盤單向跳棋nim game

  • 遊戲初始盤面: 一個1xn大小的棋盤,最左邊放著一個石頭:

https://ithelp.ithome.com.tw/upload/images/20191110/201171146wnylwJX2A.png

  • 合法移動集定義: 玩家可選擇一個石頭,從以下操作中選擇一種:
    (a)繁殖: 在該石頭的左邊或右邊複製一個石頭
    (b)跳躍: 把該石頭拿起來,放到右邊兩格的位置上
  • 結束盤面(合法移動集為空集合的盤面): 當整個1xn棋盤填滿即宣告結束
  • 研究目標: 分析對每個n來說,先手是必勝或必敗,並計算其nim value

說明為什麼這個遊戲保證會結束:
因為石頭只會增加,不會減少,又因為「跳躍」棋步只有單向,「跳躍」棋步必然有限,故一定會以「繁殖」填滿棋盤。

基礎知識: nim value

nim value可以透過遞迴計算得到。

  1. 對於結束盤面的nim value定義為0
  2. 對於非結束盤面S,假設S經過移動後所有可能抵達的盤面為T1,..., Tn,
    並且T1,..., Tn的nim value分別為v1, ..., vn,
    則S的nim value為第一個不出現於{v1, ..., vn}中的非負整數。

基礎知識: 先手必勝/敗的勝負判斷

只要nim value=0,先手必敗; 反之若nim value>0,先手必勝。

Nim value 分析

這邊嘗試對幾個特殊盤面做nim value的分析:
一、右邊全是石頭,左邊k個空格:
https://ithelp.ithome.com.tw/upload/images/20191110/20117114SLMtHrfJgZ.png

這種盤面很容易分析,因為「跳躍」棋步完全是走不了的,只有「繁殖」,
nim value= k%2 (%是取餘運算)

二、全部有n-1個石頭,僅有一個空格:
https://ithelp.ithome.com.tw/upload/images/20191110/20117114CUl08SQA7F.png
由簡單的狀況往後推,
(a)空格在從左邊數來第1個或第2個:
此時只有唯一一步「繁殖」可走,故nim value=1
(b)空格在第3個:
可以去的盤面={空格在第一個(nv=1), 全滿盤面(n=0)},故nv=2
(c)空格在第4個:
可以去的盤面={空格在第二個(nv=1), 全滿盤面(n=0)},故nv=2
(d)空格在第5個:
可以去的盤面={空格在第三個(nv=2), 全滿盤面(n=0)},故nv=1
(e)空格在第6個:
可以去的盤面={空格在第四個(nv=2), 全滿盤面(n=0)},故nv=1
(f)空格在第7個:
可以去的盤面={空格在第五個(nv=1), 全滿盤面(n=0)},故nv=2

至此已經可以看出規律,
若棋盤大小為1xn,空格位置在第k個,
則 nv = 1 if k%4=1或2 else 2.


2 則留言

0
阿展展展
iT邦好手 1 級 ‧ 2019-11-10 21:05:18

看這個... 好像在看狂賭之淵 /images/emoticon/emoticon06.gif

哈哈,小馬沒看過「狂賭之淵」,倒看過鬥智漫畫「詐欺遊戲」。可以理解為這是對遊戲規則設計有趣(燒腦?)的稱讚嗎?/images/emoticon/emoticon13.gif

/images/emoticon/emoticon12.gif

0
rainbowrain
iT邦新手 5 級 ‧ 2019-11-12 14:15:20

看不懂最後的解釋 .. 按照規則的話,不管空格在哪一格,先手的'移動'只要是繁殖,對手就輸了
既然如此為什麼 nv 的數字會有變化?
例子中 n=7 且 k=7 的盤面,如果以最多手移動的話就是
5 移動到 7, 3 移動到 5, 1 移動到 3, 2 繁殖 1
為什麼 nv 是 2 O_O

這是nv(nim value)的遞迴定義,當前盤面的nv= 所有可去的盤面的nv的集合中,最小沒有出現的非負整數值。(例子中 n應該是大於 k的,圖示只是想表達「全部有n-1個石頭,僅有一個空格」的狀況)

k=7 的盤面的nv是2是因為 k=7 的盤面可以到達的盤面有兩個:
一、 k=5 的盤面(nv=1)
二、 棋盤全滿的盤面(nv=0)
在集合{0,1}中,最小沒有出現的非負整數值=2,所以nv=2。

我要留言

立即登入留言