Werden wir Helden für einen Tag

Home | About | Archive

Algorithmic Cluedo

Posted on Jan 5, 2012 by Chung-hong Chan

在網上看到如此 comment 。他說已經破解了 Cluedo 這個 game ,不再覺得好玩。
在二零一一年十二月三十一日之前我沒有玩過 Cluedo ,在當天我玩了人生的第一局和第二局,在第二局我已經知道上文 comment 所說的東西了,但我仍覺得很有樂趣。
電腦學家研究 Cluedo 的 AI ,可用於掃地雷問題。 Cluedo 就算發展出很強的 AI ,也並不像 Checker 那樣,宣佈遊戲已被 solve ,情況就像西洋棋。
此遊戲有不少 trick 的。遊戲目的是要估中三張卡 Ax1, Bx2, Cx3
理性的 assumption 是,玩家 suspect 的 Ax, Bx 和 Cx ,他手上沒有此三張牌,故此他以此收窄 search space 。但是,如果玩家估 A 和 B 都是手上有的牌 (Ah, Bh),而 C 是手頭上無的牌 (Cdh), search space 收得更窄,是只限死在 C 。如果有人展示此 C 卡。代表 Cx3 != Cdh 。而當無人能展示 suspect 的 C 卡,就代表 Cx3 == Cdh 。無論怎計,這樣的估法是能獲取更多的資料。大前提是,你沒有從此暴露你有 Ah, Bh
另一個 trick 是 suspect 三張牌手頭上都有 (Ah, Bh, Ch) ,屆時人人都不能展示,整個 system 就 short circuit 了。從此提供錯誤資訊,令人以為 Ah, Bh, Ch 其中最少一個是 Ax1, Bx2, Cx3
問題就是在於,人人要估三張手頭上都無的卡來收窄 search space 的假設未必成立的。估計何時成立何時不成立,就是此遊戲的絕妙之處。
如果只係玩 deduction ,此遊戲只需要有 shorthand 記下所有 transaction ,再用超人方法分析就可以了。但問題是,要 suspect 某人在某地行兇,是要棋子走到在某地才可進行。故此, Limiting factor 正是行棋方法,這也涉及擲骰運氣,甚至隨時被其他玩家 suspect 時拉走,請問這一部份又如何 "break" ?


Powered by Jekyll and profdr theme