iT邦幫忙

2

興趣研究- 跳棋nim game(2)盤面的記號表示

(本系列為自己有興趣的主題研究,非教學文)
興趣研究- 跳棋nim game(1)中,小馬創造了自己的遊戲,
並針對特殊盤面的nim value進行分析。
然而一直畫石頭來表達現在的盤面也是挺麻煩的,
有沒有什麼方法可以方法的以記號來記錄一組盤面呢?
譬如以下的盤面:

https://ithelp.ithome.com.tw/upload/images/20191117/20117114trdUZ6E7GI.png

目前有想到幾種表示方法:

  1. 記錄盤面大小及石頭的位置
  2. 記錄盤面大小及空格的位置
  3. 相鄰的石頭或空格合併成一個數字,例如本盤面就是「3個空格、2個石頭、2個空格、4個石頭」

目前並不知道哪種表示方法較好,
但直覺上小馬認為若記錄盤面大小及石頭的位置總是冗長,
一般來說用「3個空格、2個石頭、2個空格、4個石頭」的講法感覺較省記錄需要的數字。
注意尾端不論有幾個石頭,因為最後幾個石頭都是無法移動的,故
尾端有「n個石頭」與尾端有「1個石頭」其實效果是一樣的。
所以本盤面相當於「3個空格、2個石頭、2個空格、1個石頭」的盤面,
簡單用元組(tuple)記為(3,2,2;1),
或者,為了方便,亦允許記為(0,3,2,2;1)。
我們只在意尾端是否有石頭,不在意數量,
故設定尾碼必定是0或是1代表尾端是否有石頭。
特別地,若盤面為全部都是石頭無空格,則記為單獨一碼(1)。

Note: 除了首、尾碼允許是0,中間必定都是正整數

牛刀小試: 以下盤面記號表示法?

https://ithelp.ithome.com.tw/upload/images/20191117/20117114qHXzrcvHvr.png

ans: (1,1,1,1,1,1,1;0)

Nim value 分析

對於興趣研究- 跳棋nim game(1)中的nim value分析,
我們可以用新的記號來寫。(設nv表示nim value)
一、右邊全是石頭,左邊k個空格:
https://ithelp.ithome.com.tw/upload/images/20191117/20117114Jt6pRgAc0y.png

記號表示: nv(k;1) = k%2 (%是取餘運算)

二、全部有n-1個石頭,僅有一個空格:
https://ithelp.ithome.com.tw/upload/images/20191117/20117114pk2twIXarL.png

記號表示: nv(k,1;1) = 1 if k%4< 2 else 2

接下來的目標: 找到nv general 的遞迴式或繼續找些特殊盤面研究。


尚未有邦友留言

立即登入留言