最近一個朋友在用計算機模擬人來玩文曲星上的
“猜數字”游戲，也邀我一起討論。我以前沒有玩過，不過發現這個還是蠻有趣的，于是也想寫一個能猜數據的小程序。
通過幾日思考，終于實現了一個稍微有點聰明的。以下是C++代碼（
下載源代碼）。
首先函數頭的定義部分，其中一個重要的數據結構是各個排列之間的關系矩陣。
我們使用 char 來表示兩個排列的關系，char值的計算方法為“A*10+B”；譬如假設 排列i 與 排列j 的關系為“1A2B”，則 table[i][j] = (char)12。
1 #include <iostream>
2
3 #define N 4 // 排列長度
4 #define M (10*9*8*7) // 總的可能排列數
5 #define MATCH (N*10) // 猜測正確時的judge()返回值
6
7 #define swap(a,b) {int t=a; a=b; b=t;}
8
9 int arrange[M][N]; // 所有可能排列的列表，一行一個排列
10 char table[M][M]; // 各排列之間的關系矩陣
11
12 int arr_count; // 用于生成所有排列時使用的全局變量
判斷兩個排列之間關系的函數：
1 // 判斷兩個排列之間的關系
2 // 譬如如果結果為“1A2B”，則返回值為 (char)12
3 char judge(int v1[], int v2[])
4 {
5 int a = 0;
6 int b = 0;
7 for (int i=0; i<N; i++) {
8 if( v1[i] == v2[i])
9 a += 1;
10 for (int j=0; j<N; j++) {
11 if (v1[i] == v2[j])
12 b += 1;
13 }
14 }
15 b -= a;
16 return (char)(a * 10 + b);
17 }
18
初始化排列列表：
1 // 使用遞歸方法計算排列
2 void arr(int a[], int start)
3 {
4 if (start == N) {
5 for (int i=0; i<N; i++)
6 arrange[arr_count][i] = a[i];
7 arr_count++;
8 return;
9 }
10 for (int i=start; i<=9; i++) {
11 swap(a[start], a[i]);
12 arr(a, start+1);
13 swap(a[start], a[i]);
14 }
15 }
16
17 // 初始化所有可能排列情況的列表
18 void init_arrange()
19 {
20 int a[10];
21 arr_count = 0;
22 for (int i=0; i<=9; i++)
23 a[i] = i;
24 arr(a, 0);
25 }
初始化關系矩陣：
1 // 初始化各個排列間的關系矩陣
2 void init_table()
3 {
4 for (int i=0; i<M; i++) {
5 for (int j=0; j<=i; j++) {
6 table[i][j] = table[j][i] = judge(arrange[i], arrange[j]);
7 }
8 }
9 }
為了方便，這里有一些打印信息的函數：
1 // 按照“[0 1 2 3]”的形式打印排列
2 void print_arrange(int arr_index)
3 {
4 std::cout << "[";
5 for (int i=0; i<N; i++) {
6 if (i != 0)
7 std::cout << " ";
8 std::cout << arrange[arr_index][i];
9 }
10 std::cout << "]";
11 }
12
13 // 按照類似“0A0B”的形式打印裁判的結果
14 void print_result(char result)
15 {
16 std::cout << ((int)result/10) << "A" << ((int)result%10) << "B" <<std::endl;
17 }
18
19 // 打印一次猜測與結果的信息
20 void print_guess_info(int arr_index, char result) {
21 print_arrange(arr_index);
22 std::cout << " --> ";
23 print_result(result);
24 std::cout << std::endl;
25 }
便于擴展，使用抽象類。以下是裁判與玩家雙方的接口：
1 // 玩家的抽象類
2 class Player
3 {
4 public:
5 // 開始游戲前的初始化
6 virtual void init() = 0;
7 // 獲取下一次猜測的排列
8 virtual int getNextGuess() = 0;
9 // 告訴玩家上一次猜測的結果
10 virtual void setGuessResult(int arr_index, char result) = 0;
11 };
12
13 // 裁判的抽象類
14 class Judgment
15 {
16 public:
17 // 開始游戲前的初始化
18 virtual void init() = 0;
19 // 對猜測進行判斷，返回結果
20 virtual char doJudge(int arr_index) = 0;
21 };
現在讓玩家玩一次游戲，直到猜成功：
1 // 玩一次游戲，返回猜測次數
2 int play(Player * p, Judgment * j) {
3 int time = 0;
4 p->init();
5 j->init();
6 while (1) {
7 int guess = p->getNextGuess();
8 char result = j->doJudge(guess);
9 // print_guess_info(guess, result);
10 time++;
11 if (result == (char)MATCH)
12 break;
13 p->setGuessResult(guess, result);
14 }
15 return time;
16 }
尋找一個誠實的裁判：
1 class HonestJudgment
2 : public Judgment
3 {
4 int _my_arr[N];
5 public:
6 HonestJudgment() { }
7 ~HonestJudgment() { }
8 public:
9 void init() { }
10 // 設置裁判的正確結果
11 void setArrange(int arr[]) {
12 for (int i=0; i<N; i++)
13 _my_arr[i] = arr[i];
14 }
15 // 這是一個誠實的裁判，所以會誠實地裁決
16 char doJudge(int arr_index) {
17 return judge(_my_arr, arrange[arr_index]);
18 }
19 };
有了裁判，還要找一個玩家。我們先找一個頭腦簡單點的玩家：
1 class NaivePlayer
2 : public Player
3 {
4 bool _cand[M];
5 int _cand_count;
6 public:
7 NaivePlayer() { }
8 ~NaivePlayer() { }
9 public:
10 void init() {
11 for (int i=0; i<M; i++)
12 _cand[i] = true;
13 _cand_count = M;
14 }
15 int getNextGuess() {
16 // 第一次猜測總是使用第一個排列
17 if (_cand_count == M)
18 return 0;
19 // 返回遇到的第一個可行排列
20 for (int i=0; i<M; i++) {
21 if (_cand[i]) {
22 return i;
23 }
24 }
25 }
26 void setGuessResult(int arr_index, char result) {
27 // 依據返回結果進一步排除已有的可行排列
28 for (int j=0; j<M; j++) {
29 if (_cand[j] && table[arr_index][j] != result)
30 _cand[j] = false;
31 _cand_count--;
32 }
33 }
34 };
用Factory工廠制造裁判和玩家（哈哈，批量生產）：
1 Player * player_factory()
2 {
3 return new NaivePlayer();
4 }
5
6 Judgment * judgment_factory()
7 {
8 return new HonestJudgment();
9 }
現在讓大家玩起來吧：
1 int main()
2 {
3 int time_stat[M]; // 次數統計表
4 Judgment *jp;
5 Player *pp;
6 // 獲取實例
7 jp = judgment_factory();
8 pp = player_factory();
9 // 初始化次數統計表
10 for (int i=0; i<M; i++)
11 time_stat[i] = 0;
12 // 初始化排列列表和關系矩陣
13 init_arrange();
14 init_table();
15 // 每一種排列情況都玩一次
16 for (int i=0; i<M; i++) {
17 ((HonestJudgment*)jp)->setArrange(arrange[i]);
18 int t = play(pp, jp);
19 print_arrange(i);
20 std::cout << " : " << t << std::endl;
21 time_stat[t]++;
22 }
23 // 統計結果
24 int total = 0;
25 std::cout << "-------------" << std::endl;
26 for (int i=0; i<M; i++) {
27 if (time_stat[i]) {
28 std::cout << i << "\t" << time_stat[i] << std::endl;
29 total += time_stat[i]*i;
30 }
31 }
32 std::cout << "Average: " << total << "/" << M << " = " << (float)total/M << std::endl;
33 std::cout << "-------------" << std::endl;
34 delete jp;
35 delete pp;
36 return 0;
37 }
得到的統計數據：
NaivePlayer Algorithm:
-------------
1 1
2 13
3 108
4 596
5 1664
6 1770
7 755
8 128
9 5
Average: 28029/5040 = 5.56131
-------------
雖然頭腦簡單，但是還都能猜出來，只是次數多了點。
好了，現在整個框架搭起來了?，F在的任務是尋找更聰明的玩家，讓猜測次數降下來。
還真找到了一個貪婪的玩家（算法原理見代碼注釋），且叫他 Clever1Player 吧：
1 class Clever1Player
2 : public Player
3 {
4 bool _cand[M]; // 排列是否可行的標志矩陣
5 int _cand_count; // 當前可行排列的個數
6 public:
7 Clever1Player() { }
8 ~Clever1Player() { }
9 public:
10 void init() {
11 for (int i=0; i<M; i++)
12 _cand[i] = true;
13 _cand_count = M;
14 }
15 int getNextGuess() {
16 // 第一次猜測總是使用第一個排列
17 if (_cand_count == M)
18 return 0;
19 // 當只有一個可行排列時，直接返回
20 if (_cand_count == 1) {
21 for (int i=0; i<M; i++)
22 if (_cand[i])
23 return i;
24 }
25 ///////////////////
26 // 悲觀假設：
27 // 假設無論猜什么排列，電腦總是能聰明地返回結果，
28 // 使得依據返回結果能進一步排除掉的可行排列數目最少（即剩余的可行排列數目最多）
29 // 貪婪算法：
30 // 從可行排列中選擇下一次猜測的排列；
31 // 在悲觀假設總是成立的條件下，使得每次排除掉的可行排列數目最多（即剩余的可行排列數目最少），即求最好的最壞情況；
32 ///////////////////
33 int res_count[MATCH+1];
34 int min_max = M+1;
35 int min_max_index;
36 for (int i=0; i<M; i++) {
37 // 對于每一個可行排列 Ri
38 if (_cand[i]) {
39 // 下一次猜測排列 Ri 的時候，裁判將會返回一個結果；
40 // 根據悲觀假設，裁判返回的結果總是使得依據返回結果能進一步排除掉的可行排列數目最少（即剩余的可行排列數目最多）
41 // cur_max 記錄該最壞情況下剩余的可行排列的數目
42 int cur_max = 0;
43 for (int j=0; j<=MATCH; j++)
44 res_count[j] = 0;
45 for (int j=0; j<M; j++) {
46 if (_cand[j])
47 res_count[ (int)table[i][j] ]++;
48 }
49 for (int j=0; j<=MATCH; j++)
50 if (res_count[j] > cur_max)
51 cur_max = res_count[j];
52 // 如果 cur_max 小于全局 min_max，則更新 min_max，并記錄下當前排列的序號
53 // 這樣能找到最好最壞情況
54 if (cur_max < min_max) {
55 min_max = cur_max;
56 min_max_index = i;
57 }
58 }
59 }
60 // 返回最好最壞情況下的排列序號
61 return min_max_index;
62 }
63 void setGuessResult(int arr_index, char result) {
64 // 依據返回結果進一步排除已有的可行排列
65 for (int j=0; j<M; j++) {
66 if (_cand[j] && table[arr_index][j] != result) {
67 _cand[j] = false;
68 _cand_count--;
69 }
70 }
71 }
72 };
73
74 // 讓工廠開始生產我
75 Player * player_factory()
76 {
77 return new Clever1Player();
78 }
好了，Clever1Player 也來玩了，看看他的成績：
Clever1Player Algorithm:
-------------
1 1
2 13
3 108
4 620
5 2002
6 1937
7 356
8 3
Average: 26979/5040 = 5.35298
-------------
成績還不錯，不過最差情況下要猜8次嘛。
有人說最多7次就可以猜出來，我們再找找。
沒想到 Clever1Player 的兄弟 Clever2Player 也會玩，而且玩的也不錯（算法原理見代碼注釋）：
1 class Clever2Player
2 : public Player
3 {
4 bool _cand[M];
5 int _cand_count;
6 public:
7 Clever2Player() { }
8 ~Clever2Player() { }
9 public:
10 void init() {
11 for (int i=0; i<M; i++)
12 _cand[i] = true;
13 _cand_count = M;
14 }
15 int getNextGuess() {
16 // 第一次猜測總是使用第一個排列
17 if (_cand_count == M)
18 return 0;
19 // 當只有一個可行排列時，直接返回
20 if (_cand_count == 1) {
21 for (int i=0; i<M; i++)
22 if (_cand[i])
23 return i;
24 }
25 ///////////////////
26 // 與Clever1Player的區別：
27 // 下一次猜測的排列不局限于可行排列
28 ///////////////////
29 int res_count[MATCH+1];
30 int min_max = M+1;
31 int min_max_index;
32 for (int i=0; i<M; i++) {
33 // 對于所有排列 Ri
34 int cur_max = 0;
35 for (int j=0; j<=MATCH; j++)
36 res_count[j] = 0;
37 for (int j=0; j<M; j++) {
38 if (_cand[j])
39 res_count[ (int)table[i][j] ]++;
40 }
41 for (int j=0; j<=MATCH; j++)
42 if (res_count[j] > cur_max)
43 cur_max = res_count[j];
44 if (cur_max < min_max) {
45 min_max = cur_max;
46 min_max_index = i;
47 }
48 }
49 return min_max_index;
50 }
51 void setGuessResult(int arr_index, char result) {
52 for (int j=0; j<M; j++) {
53 if (_cand[j] && table[arr_index][j] != result) {
54 _cand[j] = false;
55 _cand_count--;
56 }
57 }
58 }
59 };
60
61 // 讓工廠開始生產我
62 Player * player_factory()
63 {
64 return new Clever2Player();
65 }
Clever2Player 的成績：
Clever2Player Algorithm:
-------------
1 1
2 2
3 22
4 176
5 1301
6 2885
7 653
Average: 29161/5040 = 5.78591
-------------
不錯，果然在7次之內都能猜出來。只是為什么平均成績還不如 Clever1Player 呢？
這個問題，我得找時間問問他。
當前Clever1Player時間復雜度為 (M*M*Time) ，其中Time為猜測次數?？紤]次數總小于10，所以時間復雜度為 (M^2)。
我曾經做過優化，即使用一個數組保存可行排列序號，這樣在 Clever1Player 的 36 和 45 行就只需要掃描數組，而不需要每次都掃描 M 次了。當然總的時間復雜度依然是 (M^2)。
Clever2Player 與 Clever1Player 的唯一區別在于 “去掉了Clever1Player 的第 38 行”，使得“下一次猜測的排列不局限于可行排列”。
基于的考慮是：
-------------
假設正確結果是 0124
第一次猜 0123 -> 3A0B
Clever1Player 接下來不能猜 4567 ，因為 4567 不在可行集中（已經排除）。
但是Clever2Player 則有可能會猜 4567 得到 0A1B，直觀上說，猜測范圍就縮小到 01234567 中了，搜索空間減小很多。實際上我們人腦使用邏輯推理的時候通常就是這么考慮的，而且我們肯定是不會使用這種搜索算法的。
至于邏輯推理法與搜索法之間有什么聯系，我也不清楚。
-------------
另外，該算法的關注點在于猜測次數，即在于效果而不是效率。所以為了使算法看起來清晰，我沒有過多優化。
NaivePlayer 算法執行時間最快，大約1分鐘跑完所有5040種情況，Clever1Player大約5分鐘，Clever2Player大約10分鐘。
另外我也曾考慮過“動態規劃”算法，遞推公式： t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是當前可行集，t(F) 為該可行集 F 條件下猜出結果的次數，f 為 F 中的一個可行排列。
但是我沒有編程實現，因為擔心復雜度太高運行不完。
而貪心算法得到的應當不是最優解，但是近似最優解，而且從次數和執行效率上來說都是可以接受的。
下一步做什么呢？
我們可以找一個狡猾的裁判，他讓玩家 Clever1Player 和 Clever1Player 的“悲觀假設”變成現實。
一邊是聰明的玩家，一邊是狡猾的裁判，哈哈，有好戲看了。
究竟鹿死誰手，請聽下回分解。
最后感謝
東坡_居士，讓我有機會接觸這么好玩的游戲。