﹝來源﹞
美麗境界，讓John Nash 成為數學系都通曉的數學家，前陣子同學在
閱覽美麗境界一書時，在書中看見"Nash棋"，幾個好奇心甚強的同學
變畫起棋盤，研究一番。
﹝遊戲規則﹞
如下圖為一 14x14的圓格子棋盤[書中原本是正六邊形]，主要是每個圓格子都有
六個圓和他相鄰。兩人各持一顏色棋子，輪流下子，只要先將兩邊相連者，即為
獲勝，(黑色棋要連上下兩邊，白色棋要連左右兩邊)，下棋時任意位置皆可放。
黑
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
白 ○○○○○○○○○○○○○○ 白
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
○○○○○○○○○○○○○○
黑
﹝討論﹞
可先試著比較小的棋盤(如右為一 6x6的Nash)先試玩，在 ○○○○○○
小棋盤時，會覺得先手占有相當的優勢，事實上在6x6 中 ○○○○○○
，先手第一子下中間後機乎是穩超勝算，但若棋盤較大些 ○○○○○○
時，就不是那麼簡單的。 ○○○○○○
○○○○○○
數學系的人直覺會問兩個問題，是否有平手局出現，即當
整個棋盤下完時，黑白皆不連成對邊的線，答案是否，不
論兩人怎麼下皆可分出勝負。先手或後手是否有必勝策略
，答案是有，但在大棋盤中似乎很難說明 (至少我現在還
未想出清礎的解釋方法) 。
﹝問題﹞
下兩圖為4x4 5x5 的兩局棋[摘自數學遊戲一書]，左邊那盤輪綠子下，右邊那盤
輪紅子下，要下那個位置才能必勝。
綠 綠
○○○○ ○○○○○
紅 ●○○● 紅 ○○○○○
○●○○ 紅 ○○○●● 紅
○○●● ○●●○○
○●○○○
綠
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: clifflu (快樂是由內向外的啊) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Sun Apr 28 11:33:36 2002
※ 引述《cfwhite (又一個人陷入愛情)》之銘言：
※ 引述《arist (這實在是太複雜了)》之銘言：
﹝問題﹞
下兩圖為4x4 5x5 的兩局棋[摘自數學遊戲一書]，左邊那盤輪綠子下，右邊那盤
輪紅子下，要下那個位置才能必勝。
綠 綠
○○○○ ○○○○○
紅 ●○●● 紅 ○●○○○
○●●○ 紅 ○○○●● 紅
○○●● ○●●○○
○●○○○
綠
左邊這題我覺得是黃色那個位置 ^^;;
右邊那個應該沒錯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.212.3
※ 編輯: clifflu 來自: 140.112.212.3 (04/28 11:34)
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Sun Apr 28 12:19:19 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: ﹝來源﹞
: 數學系的人直覺會問兩個問題，是否有平手局出現，即當
: 整個棋盤下完時，黑白皆不連成對邊的線，答案是否，不
: 論兩人怎麼下皆可分出勝負。先手或後手是否有必勝策略
: ，答案是有，但在大棋盤中似乎很難說明 (至少我現在還
: 未想出清礎的解釋方法) 。
不妨假設左上角為黑棋，並且想像黑棋是水，
你從左上倒黑水下去，要什麼情形才會發生水到不了底部的情形。
必然是有阻礙，這個阻礙是連成一線的，把黑棋從上面到下面分開了。
（如果不連線，必然有洞。）
這個阻礙連線假如是從左到右，自然沒問題，但如果是從左到上呢？
反正盤面是有限的，換黑棋來圍白棋了。
總之，棋盤擺滿後，不可能沒有勝負的。
而且顯然先手必勝。
假如後手存有必勝策略，先手先幻想盤面上面已經有一顆對方的子，
然後用後手的策略下（當然記得要轉個九十度）。
這種棋跟圍棋不一樣，多下一子，完全不可能吃虧。
: ﹝問題﹞
: 下兩圖為4x4 5x5 的兩局棋[摘自數學遊戲一書]，左邊那盤輪綠子下，右邊那盤
: 輪紅子下，要下那個位置才能必勝。
: 綠 綠
: ○○○○ ○○○○○
: 紅 ●○○● 紅 ○○○○○
: ○●○○ 紅 ○○○●● 紅
: ○○●● ○●●○○
: ○●○○○
: 綠
--
※ 編輯: weijr 來自: 64.175.110.217 (04/28 12:35)
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Mon Apr 29 00:52:42 2002
※ 引述《weijr (173/124)》之銘言：
: 而且顯然先手必勝。
: 假如後手存有必勝策略，先手先幻想盤面上面已經有一顆對方的子，
: 然後用後手的策略下（當然記得要轉個九十度）。
: 這種棋跟圍棋不一樣，多下一子，完全不可能吃虧。
實際上的必勝策略很簡單，先手在左上角放一子，
往下有兩條路，後手只能防一路，餘此類推。
可以推廣至三度空間或更高度。
: : ﹝問題﹞
: : 下兩圖為4x4 5x5 的兩局棋[摘自數學遊戲一書]，左邊那盤輪綠子下，右邊那盤
: : 輪紅子下，要下那個位置才能必勝。
: : 綠 綠
: : ○○○○ ○○○○○
: : 紅 ●○○● 紅 ○○○○○
: : ○●○○ 紅 ○○○●● 紅
: : ○○●● ○●●○○
: : ○●○○○
: : 綠
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.48.130
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Mon Apr 29 05:53:33 2002
※ 引述《LRM (小烏龜)》之銘言：
: ※ 引述《weijr (173/124)》之銘言：
: : 實際上的必勝策略很簡單，先手在左上角放一子，
: : 往下有兩條路，後手只能防一路，餘此類推。
: : 可以推廣至三度空間或更高度。
: 可是如果後手下第三行第二個呢？
: 1 0 0 ...
: 0 0 0 0 ...
: 0 2 0 0 ...
謝謝，沒有想清楚。
3應該放在2右邊。
如果4擋在1,3中間，5則放在4的右邊，當成交換一手。
如果4放在右下方n-2 x n-2 的區域，則我們使用n-2 x n-2 的必勝方式
應對。
如果4是放在其它位置比較麻煩，如果放在左手邊則5 將1 3 連起
如果是放在上半部，就要看情形了。放在上面第二行，可能要放一子在右邊接應。
放在第一行則放在下一行接應。
但由於有交換一手的情形，所以 n-2 x n-2的必勝策略不見得能和左上
的黑子相連，所以黑子要想辦法穿越上面兩行。基本上是試著往左跑
，和自己的子力碰頭。
還是有點複雜，還是要實際操作一下才知道。
但同樣的，2還有許多位置可以選擇，所以我原來沒有想清楚。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: weijr 來自: 131.215.108.166 (04/29 06:24)
> -------------------------------------------------------------------------- <
作者: arist (這實在是太複雜了) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Mon Apr 29 08:42:13 2002
※ 引述《weijr (173/124)》之銘言：
: ※ 引述《LRM (小烏龜)》之銘言：
: : 可是如果後手下第三行第二個呢？
: : 1 0 0 ...
: : 0 0 0 0 ...
: : 0 2 0 0 ...
: 謝謝，沒有想清楚。
: 3應該放在2右邊。
: 如果4擋在1,3中間，5則放在4的右邊，當成交換一手。
: 如果4放在右下方n-2 x n-2 的區域，則我們使用n-2 x n-2 的必勝方式
: 應對。
: 如果4是放在其它位置比較麻煩，如果放在左手邊則5 將1 3 連起
: 如果是放在上半部，就要看情形了。放在上面第二行，可能要放一子在右邊接應。
: 放在第一行則放在下一行接應。
: 但由於有交換一手的情形，所以 n-2 x n-2的必勝策略不見得能和左上
: 的黑子相連，所以黑子要想辦法穿越上面兩行。基本上是試著往左跑
: ，和自己的子力碰頭。
: 還是有點複雜，還是要實際操作一下才知道。
: 但同樣的，2還有許多位置可以選擇，所以我原來沒有想清楚。
嗯 這種問題再小棋盤中 常很容易覺得有必勝下法
大棋牌裡的變化 要說清礎 似乎很難 但實際在下時 先手的確感覺有優勢
像下面10X10的棋盤，先手為綠子，現換先手下，
初看以為先手下中間的方向最多要檔住很難，
但若後手不管先手直接封殺先手的鄰邊就很難防，
基本上我感覺這就會變成先後手交互填下方的棋盤，
但先手因中間已先有一顆還是會先連結起來。
另外weijr說明先手必勝的那部我覺得頗妙的。
綠
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
紅 ○○○○○○○○○○
○○○○●○○○○○
○○○○○○○○○○ 紅
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○●○○○
綠
若要像五子棋那樣加入先手的限制 不知是否能改變平衡
如先手一定要在nxn的棋盤中下完4n顆棋之前獲勝。
當然這種限制在如上的棋盤中似乎可覺得在此限制下後手會必勝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Mon Apr 29 11:40:03 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: 若要像五子棋那樣加入先手的限制 不知是否能改變平衡
: 如先手一定要在nxn的棋盤中下完4n顆棋之前獲勝。
: 當然這種限制在如上的棋盤中似乎可覺得在此限制下後手會必勝。
沒有平手的情形下，有限遊戲一定有一方必勝。
要讓後手有利，不妨改成 nx(n-1)
另外，常用的方式，先手第一步放一子，皆下來，輪流每步放兩子
也可以改成甜甜圈，先連成指定方向的圈圈者獲勝。（圈圈有兩種）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.48.174
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Thu May 2 06:45:32 2002
※ 引述《weijr (173/124)》之銘言：
: ※ 引述《arist (這實在是太複雜了)》之銘言：
: : 若要像五子棋那樣加入先手的限制 不知是否能改變平衡
: : 如先手一定要在nxn的棋盤中下完4n顆棋之前獲勝。
: : 當然這種限制在如上的棋盤中似乎可覺得在此限制下後手會必勝。
: 沒有平手的情形下，有限遊戲一定有一方必勝。
: 要讓後手有利，不妨改成 nx(n-1)
: 另外，常用的方式，先手第一步放一子，皆下來，輪流每步放兩子
: 也可以改成甜甜圈，先連成指定方向的圈圈者獲勝。（圈圈有兩種）
看 rec.games.go，連幾個連結找到的網址
http://www-2.cs.cmu.edu/~hde/hex/hexfaq/
1942年發明，john nash 1949年證明先手勝，
目前已知必勝法到7x7。
某些地方的規則，
後手可以在先手下一子之後，請求換邊。（所以後手必勝）
也有用美國地圖當棋盤的。
用戰國地圖來合縱連橫一番似乎也不錯。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: weijr 來自: 131.215.108.166 (05/02 06:49)
> -------------------------------------------------------------------------- <
作者: arist (這實在是太複雜了) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Fri May 3 07:35:34 2002
※ 引述《weijr (173/124)》之銘言：
: ※ 引述《hiei81 (夕。陽，華燈初上)》之銘言：
: : Why? 假定棋盤是奇數成以奇數, 第一手下在正中央, 換邊有差嗎?:p
: 當然有差，他變成先手了。
換邊的意思 你說的和hiei81說的好像不太一樣
hiei81說的 是原本先手若是要連 上下邊
但下完第一子後 後手可要求先手要連左右邊
先手還是先手後手還是後手
你的意思 是指 換誰當先後手?
有些像五子棋的國規一開始那樣?
但若先手第一子下的很怪 如下的很貼近後手的邊
那樣還有辦法保證先手必勝嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: arist (這實在是太複雜了) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Fri May 3 07:40:52 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: ※ 引述《weijr (173/124)》之銘言：
: : 當然有差，他變成先手了。
: 換邊的意思 你說的和hiei81說的好像不太一樣
: hiei81說的 是原本先手若是要連 上下邊
: 但下完第一子後 後手可要求先手要連左右邊
: 先手還是先手後手還是後手
: 你的意思 是指 換誰當先後手?
: 有些像五子棋的國規一開始那樣?
: 但若先手第一子下的很怪 如下的很貼近後手的邊
: 那樣還有辦法保證先手必勝嗎
如
紅
○○○○○○
○○○○○○
綠 ○○○○○○ 綠
○○○○○○
●○○○○○
○○○○○○
紅
要準備去上課了 沒仔細去想
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Fri May 3 07:46:03 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: ※ 引述《weijr (173/124)》之銘言：
: : 當然有差，他變成先手了。
: 換邊的意思 你說的和hiei81說的好像不太一樣
: hiei81說的 是原本先手若是要連 上下邊
: 但下完第一子後 後手可要求先手要連左右邊
: 先手還是先手後手還是後手
: 你的意思 是指 換誰當先後手?
: 有些像五子棋的國規一開始那樣?
: 但若先手第一子下的很怪 如下的很貼近後手的邊
: 那樣還有辦法保證先手必勝嗎
後手既然可以選擇換，自然也可以選擇不換了，
否則就不叫做選擇了。
總之，先手下的好，後手會要求換，
先手下不好，後手自然不換，怎麼算都是後手有利。
只是複雜程度又增加了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.108.166
> -------------------------------------------------------------------------- <
作者: hiei81 (夕。陽，華燈初上) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Fri May 3 17:40:57 2002
※ 引述《weijr (173/124)》之銘言：
: ※ 引述《arist (這實在是太複雜了)》之銘言：
: : 換邊的意思 你說的和hiei81說的好像不太一樣
: : hiei81說的 是原本先手若是要連 上下邊
: : 但下完第一子後 後手可要求先手要連左右邊
: : 先手還是先手後手還是後手
: : 你的意思 是指 換誰當先後手?
: : 有些像五子棋的國規一開始那樣?
: : 但若先手第一子下的很怪 如下的很貼近後手的邊
: : 那樣還有辦法保證先手必勝嗎
: 後手既然可以選擇換，自然也可以選擇不換了，
: 否則就不叫做選擇了。
: 總之，先手下的好，後手會要求換，
: 先手下不好，後手自然不換，怎麼算都是後手有利。
: 只是複雜程度又增加了。
這樣不行, 無論先手下在哪裡, 由於遊戲有限,
一定可以算出後手必勝或先手必勝,
如果先手必勝, 後手便要求當先手, 反之便要求當後手並採用必勝策略,
因此後手必勝.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.18.71
> -------------------------------------------------------------------------- <
作者: arist (這實在是太複雜了) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Sat May 4 12:38:15 2002
※ 引述《hiei81 (夕。陽，華燈初上)》之銘言：
: ※ 引述《weijr (173/124)》之銘言：
: : 後手既然可以選擇換，自然也可以選擇不換了，
: : 否則就不叫做選擇了。
: : 總之，先手下的好，後手會要求換，
: : 先手下不好，後手自然不換，怎麼算都是後手有利。
: : 只是複雜程度又增加了。
: 這樣不行, 無論先手下在哪裡, 由於遊戲有限,
: 一定可以算出後手必勝或先手必勝,
: 如果先手必勝, 後手便要求當先手, 反之便要求當後手並採用必勝策略,
: 因此後手必勝.
對阿 就像 weijr說的 複雜度就增加了
增加到超乎一般人 直覺判斷能力 這棋就有他的價值
五子棋 也是有限(雖然也有可能合局)
不過還是存在必勝 只是已超乎 目前 的計算能力吧
Nash棋 一開始14x14 這樣大的棋盤也就有他的價值
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.50.184
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【雙人遊戲】Nash棋
時間: Tue May 7 08:15:12 2002
※ 引述《hiei81 (夕。陽，華燈初上)》之銘言：
: ※ 引述《weijr (173/124)》之銘言：
: : 不貼目，先手不敗。
: 有證明?:) (東坡棋是不合的)
圍棋可以放棄著手。
連續兩方都放棄，棋局就結束了。
理論上是每一手都可以放棄，但第一手可不可以放棄，就有點法律問題了。
因為棋局的開始由黑方下一子開始，所以第一手是否可以放棄有爭議。
我原來的論述是以第一手可以放棄當前提的。
: : 不一定有必勝策略，因為有和棋。（如三劫循環，或點數相同。）
: 若使用全同禁著, 黑貼幾目半之類的規則:)
: (簡單地說就是下下去會造成與以前相同的盤面就不可以下)
其實圍棋在理論上，可能比象棋還要簡單，因為東坡棋可能可以降低
理論的難度。
比方在某些不是 simply conneted 的棋盤上面，可能只要東坡棋就行了。
一維的圍棋可能可以給出解。
依照慣例，可能更高維的比較簡單，只有二三維比較難。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.108.166
※ 編輯: weijr 來自: 131.215.108.166 (05/07 08:29)