PTT遊戲區 / Little-Games (小遊戲)

Re: [分享] 棋奕-納許棋

看板Little-Games (小遊戲)作者 (菜心)時間16年前 (2010/07/05 20:45), 編輯推噓17(17推 0噓 40→)
留言57則, 18人參與, 最新討論串2/3 (看更多)
※ 引述《SeekU (梓軒)》之銘言： : *遊戲本名：Hex : *遊戲譯名：納許棋 : *遊戲網址：http://www.lutanho.net/play/hex.html : *遊戲官網：http://www.mrlsmath.com/website-resource/the-game-of-hex/ : *遊戲操作：玩家彼此各下一步棋，先將自己兩邊的顏色串聯起來的獲勝。 : (由於這個遊戲有一個理論是先手有必勝走法，所以有一個swap rule，後手可以決定要不 : 要取代先手的顏色，右邊可以把這個功能關掉) : *個人心得：會知道這個遊戲是因為今天聊到電影美麗境界，得知原來男主角有發明一種 : 棋類遊戲，一開始是google到了http://www.mathland.idv.tw/fun/nashgame.htm 這網頁 : ，下載來玩被電腦電了一陣子後突然要我驗證之類的就不能玩了...於是才又去找到線上版 : 的。網路上查到一些針對該遊戲的理論跟實驗，看了半天還是不知道怎麼先手必勝XD" : 感覺這個遊戲應該會op才對，但我沒搜尋到0..0" Hex 是 ICGA (國際機器博弈協會) 的比賽項目之一 所以必勝法應該是還沒找出來，否則就可以不用比了XD 不過理論上先手是會有必勝法的 這點可以用 Nash 提出的偷策略(strategy-stealing)定理來證明 偷策略定理也可以應用在五子棋上面 我試著簡單說明一下他的理論 先手A 後手B 假設 後手有必勝策略 則 A 一開始隨機下一顆子，等 B 下了子以後 A 可以當作剛才隨機下的子不存在，接著套用後手必勝策略來下 接下來有兩種情況 1. 必勝策略說，接下來要下的點，上面沒有子，則 A 就可以直接下下去 2. 必勝策略說，接下來要下的點，上面有 A 剛才自己隨機下的子 則 A 再隨機下一顆子 如此一來後手的必勝策略，就可以由先手順利運作 代表先手有必勝策略，與假設矛盾 故反証法證明後手沒有必勝策略 -> 先手有必勝策略 雖然理論上先手存在必勝法 不過這個必勝法該怎麼下，人類目前還不知道就是了XD -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.251.208.71
→
07/05 20:50, , 1F
這個證明有點隨便...b去a下子的地方下就不能當不存在
07/05 20:50, 1F
→
07/05 21:04, , 2F
針對不同的棋盤大小有些必勝法已經找到了
07/05 21:04, 2F
→
07/05 21:06, , 3F
的確 不過樓上提的只對B有壞處 不影響A的必勝策略
07/05 21:06, 3F
→
07/05 21:07, , 4F
阿 一樓才對
07/05 21:07, 4F
→
07/05 21:10, , 5F
A可以忽略掉第一顆子來執行後手必勝策略 這句話邏輯
07/05 21:10, 5F
→
07/05 21:10, , 6F
已經出問題了
07/05 21:10, 6F
推
07/05 21:33, , 7F
這應該也是為什麼偷策略不能應用在圍棋上
07/05 21:33, 7F
→
07/05 21:34, , 8F
以五子棋來說 多的那一顆棋子會讓玩家"輸"的情況幾乎
07/05 21:34, 8F
→
07/05 21:34, , 9F
沒有 最糟也只是"贏不了"(五子變六子之類)
07/05 21:34, 9F
→
07/05 21:35, , 10F
但是圍棋多的那一顆子 有可能剛好是自己的眼而塞死自
07/05 21:35, 10F
→
07/05 21:35, , 11F
己 再說 圍棋有讓子 輸贏不是那麼一定
07/05 21:35, 11F
→
07/05 21:36, , 12F
所以雖然五樓說的對 但是大部份的情況 A是可以忽略第
07/05 21:36, 12F
→
07/05 21:36, , 13F
一子的
07/05 21:36, 13F
→
07/05 21:42, , 14F
五子連六不是禁手嗎...還是我記錯...
07/05 21:42, 14F
推
07/05 21:49, , 15F
這個說明 WIKI講的比較清楚一點
07/05 21:49, 15F
推
07/05 22:03, , 16F
五子棋 好像因為棋盤限制有先手必勝法 所以才會出現
07/05 22:03, 16F
→
07/05 22:03, , 17F
禁手的規則
07/05 22:03, 17F
推
07/05 22:13, , 18F
五子棋有先手必勝 所以才會有先手不能雙三雙四的規定
07/05 22:13, 18F
推
07/06 04:50, , 19F
有點看不懂 為什麼後手沒有必勝策略=先手有必勝策略?
07/06 04:50, 19F
→
07/06 04:51, , 20F
為什麼不會有必勝策略不存在的狀況阿???
07/06 04:51, 20F
推
07/06 04:55, , 21F
像是最簡單的OOXX 就算先手隨機下一手
07/06 04:55, 21F
→
07/06 04:56, , 22F
後手也不可能有必勝策略...
07/06 04:56, 22F
→
07/06 04:56, , 23F
可是後手沒有必勝策略 也不代表 先手有必勝策略
07/06 04:56, 23F
→
07/06 04:57, , 24F
基本上在絕對不失誤的情況下 絕對是打和的...
07/06 04:57, 24F
→
07/06 04:57, , 25F
所以那個邏輯是不是怪怪的阿?
07/06 04:57, 25F
推
07/06 05:19, , 26F
因為五子棋的和局很難達成 所以假設必有一方贏
07/06 05:19, 26F
→
07/06 07:56, , 27F
HEX 沒有和局!!
07/06 07:56, 27F
推
07/06 10:19, , 28F
同意邏輯怪異
07/06 10:19, 28F
→
07/06 10:25, , 29F
因為即使後手沒有必勝邏輯，仍存在獲勝的可能
07/06 10:25, 29F
推
07/06 10:36, , 30F
因為沒有和局 所以一方必勝 一方必敗
07/06 10:36, 30F
推
07/06 10:42, , 31F
問題在於-沒有必勝邏輯不代表必敗
07/06 10:42, 31F
→
07/06 10:44, , 32F
即使沒有和局也是如此
07/06 10:44, 32F
推
07/06 11:13, , 33F
亂証!
07/06 11:13, 33F
推
07/06 11:29, , 34F
看不懂的人，有興趣可以去看原文?不然納許會哭喔XD
07/06 11:29, 34F
推
07/06 11:36, , 35F
後手沒有必勝策略代表先手有辦法可以阻止後手獲勝直
07/06 11:36, 35F
→
07/06 11:36, , 36F
到遊戲結束，但這個遊戲沒有和局，直到遊戲結束後手
07/06 11:36, 36F
→
07/06 11:36, , 37F
沒有獲勝就代表先手獲勝
07/06 11:36, 37F
→
07/06 11:37, , 38F
所以後手沒有必勝策略=先手有必勝策略
07/06 11:37, 38F
推
07/06 11:52, , 39F
為何會說"後手沒有必勝策略代表先手有辦法可以阻止後
07/06 11:52, 39F
→
07/06 11:52, , 40F
手獲勝直到遊戲結束"?
07/06 11:52, 40F
→
07/06 11:54, , 41F
有人有Nash證明的原文嗎?
07/06 11:54, 41F
推
07/06 12:38, , 42F
恩...零合 雙方對等 有限狀態 的遊戲必有一方必勝
07/06 12:38, 42F
推
07/06 12:50, , 43F
必勝策略代表「無論對方怎麼下，都可以獲勝」，沒有
07/06 12:50, 43F
→
07/06 12:50, , 44F
必勝策略就代表「無論你怎麼下，對方都存在至少一種
07/06 12:50, 44F
→
07/06 12:53, , 45F
方法可以阻止你獲勝」，如果沒有必勝策略對手還無法
07/06 12:53, 45F
→
07/06 12:53, , 46F
阻止你獲勝的話，那就不是沒有必勝策略了
07/06 12:53, 46F
推
07/06 13:26, , 47F
我覺得taka大提到的"有限狀態"是重點，將sky大的"沒
07/06 13:26, 47F
→
07/06 13:28, , 48F
有必勝策略就代表"後方加上"有限狀態下"，就比較合理
07/06 13:28, 48F
→
07/06 13:30, , 49F
了，各位認為呢?
07/06 13:30, 49F
→
07/06 16:25, , 50F
可能是我記錯了 偷策略應該沒辦法用在五子棋
07/06 16:25, 50F
→
07/06 16:26, , 51F
不過 Hex 是的確可以用偷策略來證明先手必勝的
07/06 16:26, 51F
→
07/06 17:59, , 52F
這種"非構造性"必勝策略的證明通常都假設"有限步"
07/06 17:59, 52F
→
07/06 18:00, , 53F
拿象棋,西洋棋為例, 因為沒有保證有限步必可分出勝負
07/06 18:00, 53F
→
07/06 18:01, , 54F
所以這種"証明"不能套用在 象棋, 西洋棋, 圍棋 上
07/06 18:01, 54F
→
11/04 13:25, , 55F
這個證明我覺得沒問題,雖然b會受到a先下的子的影響
11/04 13:25, 55F
→
11/04 13:26, , 56F
以至於要下在其他地方,但是不論改下在哪裡a都能反應
11/04 13:26, 56F
→
11/04 13:26, , 57F
(因為已假設a有必勝策略)
11/04 13:26, 57F
‣ 更多 ACGfans 的文章
文章代碼(AID): #1CCTG268 (Little-Games)
討論串 (同標題文章)
本文引述了以下文章的的內容：
15
21
[分享] 棋奕-納許棋
SeekU
16年前, 07/05
完整討論串 (本文為第 2 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
15
21
[分享] 棋奕-納許棋
SeekU
16年前, 07/05
在新視窗開啟完整討論串 (共3篇)
Little-Games 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ACGfans 的文章
文章代碼(AID): #1CCTG268 (Little-Games)