我想可能不止資工人,應該很多人小時候都玩過這個遊戲吧xD 這個小遊戲起源於 20世紀中期的英國,然後遊戲的部分通常會需要兩名玩家 ( 可以是人,也可以是電腦。) 其中一名玩家負責出題,另一名玩家負責猜題。標準的玩法呢,出題者需要想好一個沒有重復數字的 4位數 e.g. 1234、7689、3654、7890、2395、8719、0982 ... 而它想好的這組數字不能讓猜題者知道,負責猜的人接下來就可以開始猜了,然後每猜一次,出題者就要根據猜題者猜的數字給出 幾A 幾B 的回應,其中 A 前面的數字代表正確猜中數字的個數,而 B 前的數字代表數字正確但位置不對的個數,下面舉個例子來說明: 假設出題者設想的題目為 - 1234 接著猜題者猜 - 4567;出題者則會回應 - 0A1B 接著猜題者猜 - 3489;出題者則會回應 - 0A2B 接著猜題者猜 - 2340;出題者則會回應 - 0A3B 接著猜題者猜 - 0234;出題者則會回應 - 3A0B 接著猜題者猜 - 1234;出題者則會回應 - 4A0B 在猜題者猜中答案之後遊戲就結束了。 當然這遊戲後來也有演變出一些變形的玩法,像是題目個數不是標準的四碼或者允許有重複數字之類的,但就不針對那部分進行討論啦,不然也是一個沒完沒了xD 從標準玩法出發,一般來說,如果你有採用比較嚴謹的猜題策略,任何數字最多7次就可猜出。 而對念資工系的肥宅們來說,通常我們都蠻邊緣的、沒什麼朋友Q_Q,只好自己寫個程式來跟電腦玩遊戲了!所以這時侯,我們會希望由電腦來當 code maker,出一組四碼且不重複的密碼來給我們 ( code breaker ) 猜。 其實要電腦來當 Code Maker 這部分還蠻簡單的,使用 C/C++ 實現的代碼如下:
Bulls and Cows implemented in C ++
程式在執行、遊玩的過程大概長得像這個樣子:
寫程式來實現 Code Marker 的部分還蠻簡單的,一般來說資工系大一的程式課,都會有這樣一題經典的練習題,那如果今天,要你寫一個 Code Breaker 的話,那就有趣多了! 像前面提到的,「如果你有採用比較嚴謹的猜題策略,任何數字最多7次就可猜出!」 至於什麼是 "嚴謹的猜題策略",說穿了就是演算法! 那麼有哪些演算法可以被我們用來實作 Code Breaker 這就是一個有趣的問題xD 既然是有趣的問題,自然也有人拿這個題目來寫,發過 paper 啦~ 像是你可以把它化作樹或者圖形的方式來解,另外你也可以發現,每次你填完一個答案後,系統都會根據這個答案的好壞返饋一個數值給你,所以我們當然也可以用一些啟發式 ( heuristic ) 的演算法來解這個問題,像是大名鼎鼎的基因演算法 ( Genetic Algorithm , GA ),或者我們也可以把現在一些人工智慧的演算法套進來玩。 不過這部分的東西就已經算是比較進階的啦,所以 Jason 今天應該不打算寫這一部份的東西,如果自己有興趣的話可以去 Google 一下,相關的資源應該還蠻容易找的。 Ok, 那麼今天這篇就寫到這邊吧~ Bye :")
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|