Werden wir Helden für einen Tag

Algorithmic Cluedo

Posted on Jan 5, 2012 by Chung-hong Chan

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