Re: 關於五子棋的現況--回應ddavid

[ddavid (謊言接線生)]

※ 引述《dogswang (= =)》之銘言：
: ddavid大在前面的回文中提及了五子棋的現況
: 幾經修正，甚至詳細再查過之後，還是給了錯誤的答案。
: 這篇希望能讓板眾不要被誤導，對五子棋有錯誤的觀念。
: 首先，五子棋在初手天元，一人一手的情況下，
: 不論有無禁手，都是先手必勝。是必勝，不是不敗。
    我的查證有誤，向大家說抱歉，因為我把推廣結果混在一起了XD。正確的結論是
這樣：

    任何一個無其它限制的m,n,k-game都是先手不敗的。

    所謂m,n,k-game指的是在一個m*n大小的盤面上，勝利條件為將k子連成直、橫或
斜線的遊戲。井字棋是3,3,3-game，而五子棋若用一般圍棋棋盤，則是19,19,5-game
。而當然，這兩種棋類都進一步可達到先手必勝。
: 在此規則之下，世界冠軍持白對上我，我也是永遠必勝。
: 這個結論不需要靠窮舉所有變化，只需要窮舉白方所有防守即可得到。
: 我相信這個tree是存在的，或者說，
: 我有把握在幾天內生出這個tree，因為變化實在不多。
: 以上說的是傳統的五子棋。
: 接下來談談現行五子棋的規則。
: 加入了禁手與開局規則後，和局的確變多，
: 五子棋從先手必勝的遊戲變為可實戰的棋類，和局變多是必然的結果。
: 而不是什麼「必勝的Path都被拿掉了，
: 所以雙方只要不失誤走出被限制後的最佳著手就會往和局走。」
: 無法窮舉，就無法拿掉所有必勝的path，上述論點自然不成立。
    嗯，我後來的推文有修正一些錯誤。的確在加了禁手規則後，沒有窮舉的情況下
能做到的只是將已知的必勝Path先拔除，並且削弱優勢方。不過那個結論仍然有部分
是對的，因為當任一方必勝的Path被減少後，剩下的Path通往和局的比例就的確可能
相對變高。雙方棋手的技藝與經驗越好，就更會避免走向自己必敗的Path，而走向必
勝Path的可能性也減少的情況下，自然和局比例會提高也是合理的。窮舉完後則是能
夠把這點做到100%，得到某種限制規則讓完美著手100%和局。
: 五子棋，從來就不是被窮舉的棋類。
: 另外，我想問的是，d大提到黑白棋也是被窮舉的棋類？
: 請問有哪裡可以看到這樣的結論嗎？我很想知道結論到底是什麼~~
    這裡一定要向版友們道歉。我只是憑印象寫出來的，然而詳查後確實是不完全對
的。目前只有統計資料是後手略為有利，單以人類觀點來理解的原因是容易限制先手
的選擇、白棋是實質先手、以及可下子格的數量等等。確實沒有窮舉結果。被窮舉的
是6x6的黑白棋，證明後手必勝，而標準8x8還沒有。雖然其運算量估計只有10^58，
比起西洋棋的10^123跟象棋的10^150遠小，但還是沒窮舉完成。

--
    「你會死。」不由分說，他被狠狠罵了一頓。

    午休時，我拉著他到安靜的地方。「你怎麼對著人這樣說話呢？」

    「他本來就會死，難道他不會死？」他抱怨。
                                                      －－預言師

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.24.203.83
推 shonbn:推
→ ddavid:我忽然意識到已經扯遠了，這完全沒提到圍棋了XD
→ ddavid:之後不會再增加此串文章數了，若版主覺得不妥請直接砍除XD
推 Honam:喜歡這個討論串其實
推 fatbird:據說圍棋的變化量約是10^700? (這數字對嗎?)
→ ddavid:圍棋的話，已知的估計值似乎是10^400
→ ddavid:這個值應是「上限」，不過我不知道如果使用不同的棋規會影
→ ddavid:響這個值到什麼程度......
→ jason12308:多一點不同的話題也行
推 fatbird:700是印象中之前看到的 剛看到維基上寫600
推 mirageled:我身為五子棋愛好者,看到有人把五子棋寫錯,會感覺不太好
推 rj5871224:推~~基本上加入交換後，就不可能有必勝的情況出現
→ ddavid:@mirageled 嗯，前面推文有寫錯的不少東西真的很抱歉XD
→ ddavid:@rj5871224 有兩種可能性就是了。一種是其實還有某些很複雜
→ ddavid:一手都不能應錯的必勝法存在，只是因為一點都不能應錯所以
→ ddavid:沒被發現，或者說就算有人走到了也只被當做是一般的勝利。
→ ddavid:另一種可能性是真的所有必勝都因而排除了（因為交換制沒人
→ ddavid:會想開個優劣有差距的局被對手選擇交換），在這種情況下就
→ ddavid:變成比失誤這樣，有一方沒走在最佳應手可能就輸了，都走對
→ ddavid:就和局XD
→ ddavid:當然這裡所說的「失誤」是指綜觀整顆對局樹來看的，事實上
→ ddavid:兩個人在下的時候也許並不覺得哪一方有失誤，只是某顆子可
→ ddavid:能好幾十手後忽然發揮了效用之類。圍棋也常有這種情況發生
→ ddavid:，就人類研究的觀點可能說布局做得好、計算夠深或有時就是
→ ddavid:一點運氣，不過從完整對局樹的角度來說就只有必然了，這也
→ ddavid:是這種還未能真正窮舉棋類有趣的價值所在:D