iT邦幫忙

6

數學矛盾證法-「盜取策略」我不知道怎麼走但知道遊戲先手必勝的證明技巧

今天分享一個很有意思的證明技巧- 「盜取策略」,
在某些遊戲中,我們可以用這個方法證明若雙方採取最佳策略,
那麼先手一定必勝,
但是神奇的是,我們不知道先手該如何走才會贏。

基礎思想就是假設後手必勝,
後手便存在一個棋步,
讓我不論怎麼走都會輸(假設我是先手),
那麼我就偷對手的這個策略我就贏了,
要怎麼做到這件神奇的「偷策略」呢?
這邊舉個例子:

咬巧克力生死對決

這邊有個小遊戲叫作咬巧克力,雙人對戰,
巧克力是長方形的,有m*n小塊,
譬如說下圖有4*6小塊:

https://ithelp.ithome.com.tw/upload/images/20200703/20117114PgMDbJaYRp.png

最左上角的巧克力是有毒的,
雙方都要避免吃到,
對決方式如下:

  • 兩人輪流行動,每次行動必須選擇一小塊巧克力,將該巧克力右方及下方的巧克力吃掉
  • 輪到某玩家時,若僅剩左上角一塊紫色巧克力,他將被迫吃掉那塊巧克力而輸掉

「盜取策略」證明先手必勝

那麼怎麼證明咬巧克力先手必勝呢?
首先定義什麼叫作必勝必敗盤面。

  • 僅剩左上角一塊紫色巧克力為必敗盤面。
    必勝必敗盤面採用遞迴定義的方式
  • 如果現在走的人可以找到一步變成必敗盤面,那現在的盤面為必勝
  • 如果現在走的人不論怎麼走都形成必勝盤面,那現在的盤面為必敗

證明

假設先手必勝是錯的,那麼就表示後手必勝(因為沒有和局),
先手可以先咬最右下角的巧克力,看對手怎麼勝

https://ithelp.ithome.com.tw/upload/images/20200703/2011711405JVmzJXaB.png

由於後手必勝,表示存在一個行動形成下一個人必敗的盤面,
舉例來說,假設後手咬「第二列第四行」巧克力必勝好了,
那麼下面這個盤面就是必敗盤面了:

https://ithelp.ithome.com.tw/upload/images/20200703/20117114E0diR8oPiE.png

可是如果先手知道後手咬「第二列第四行」的巧克力必勝的話,
那一開始先手就咬這塊巧克力就贏了啊,
不論後手的必勝策略是咬哪一塊巧克力,
先手都可以偷他的策略

因此後手便不可能必勝了

進一步解析思路

如果你是第一次讀這個證明的讀者,
大概會很困惑看不太懂,
小馬猜最常見的疑惑可能是「怎麼知道後手有必勝策略」,
或「怎麼知道對手必勝的策略是哪一步」(你大概想說先手要偷後手的策略總要知道他的具體策略吧)

第一個問題: 後手有必勝策略是我們假設的,透過假設後手有必勝策略得到矛盾,「盜取策略」其實就是數學上常說的「矛盾證明法」或「反證法」
第二個問題: 不需要知道對手必勝的策略具體是哪一步,既然假設對手必勝,那這一步就一定存在,所以先手可以「偷」這一步來用

「盜取策略」證明技巧是用來證明先手一定存在一個行動會贏
並不會告訴我們先手該如何走會贏
所以這個咬巧克力遊戲還是可以拿去跟朋友玩的

「盜取策略」應用- 證明Hex, 井字遊戲,五子棋先手不敗

類似的證明技巧,可以證明經典遊戲六貫棋(Hex, 或稱Nash),井字遊戲,五子棋先手絕不會輸(可參考六貫棋的連結,裡面有證明)

這邊講的「五子棋」假設先手沒有任何禁手的限制(專業五子棋有先手不能走雙活三的規定),
為什麼是「先手不敗」呢?
因為「盜取策略」證明的是「後手必勝」是錯的,
「後手必勝」的反面是「先手不敗」而非「先手必勝」(有可能有和局)

由於六貫棋(Hex)沒有和棋,
所以就保證「先手必勝」

不過,不是任何遊戲都可以用「盜取策略」證明先手必勝的。


2 則留言

2
小碼農米爾 Mir
iT邦研究生 1 級 ‧ 2020-07-03 21:24:44

這是一個教大家怎麼咬巧克力才不會被毒死的故事

心原一馬 iT邦研究生 5 級 ‧ 2020-07-03 22:51:59 檢舉

/images/emoticon/emoticon39.gif

1
anglitery
iT邦新手 5 級 ‧ 2020-07-04 16:41:45

認真看了兩輪,我覺得我看了自己覺得很矛盾,
以下不懂,
如果現在走的人可以找到一步變成必敗盤面,那現在的盤面為必勝。
如果現在走的人不論怎麼走都形成必勝盤面,那現在的盤面為必敗。
必敗 然後 盤面誰必勝。
看兩輪我覺得這個巧克力好毒。

心原一馬 iT邦研究生 5 級 ‧ 2020-07-04 19:44:35 檢舉

嗨嗨,謝謝分享,
若改成這樣會比較白話嗎?

假設現在換我走

  1. 如果不論我採取任何行動,若對手採取最佳策略我就會輸,為必敗盤面
  2. 只要我採取最佳策略就會贏,為必勝盤面

我要留言

立即登入留言