最近一個朋友在用計算機(jī)模擬人來玩文曲星上的
“猜數(shù)字”游戲，也邀我一起討論。我以前沒有玩過，不過發(fā)現(xiàn)這個還是蠻有趣的，于是也想寫一個能猜數(shù)據(jù)的小程序。
通過幾日思考，終于實現(xiàn)了一個稍微有點聰明的。以下是C++代碼（
下載源代碼）。
首先函數(shù)頭的定義部分，其中一個重要的數(shù)據(jù)結(jié)構(gòu)是各個排列之間的關(guān)系矩陣。
我們使用 char 來表示兩個排列的關(guān)系，char值的計算方法為“A*10+B”；譬如假設(shè) 排列i 與 排列j 的關(guān)系為“1A2B”，則 table[i][j] = (char)12。
1 #include <iostream>
2
3 #define N 4 // 排列長度
4 #define M (10*9*8*7) // 總的可能排列數(shù)
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]; // 各排列之間的關(guān)系矩陣
11
12 int arr_count; // 用于生成所有排列時使用的全局變量
判斷兩個排列之間關(guān)系的函數(shù)：
1 // 判斷兩個排列之間的關(guān)系
2 // 譬如如果結(jié)果為“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 }
初始化關(guān)系矩陣：
1 // 初始化各個排列間的關(guān)系矩陣
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 }
為了方便，這里有一些打印信息的函數(shù)：
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”的形式打印裁判的結(jié)果
14 void print_result(char result)
15 {
16 std::cout << ((int)result/10) << "A" << ((int)result%10) << "B" <<std::endl;
17 }
18
19 // 打印一次猜測與結(jié)果的信息
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 }
便于擴(kuò)展，使用抽象類。以下是裁判與玩家雙方的接口：
1 // 玩家的抽象類
2 class Player
3 {
4 public:
5 // 開始游戲前的初始化
6 virtual void init() = 0;
7 // 獲取下一次猜測的排列
8 virtual int getNextGuess() = 0;
9 // 告訴玩家上一次猜測的結(jié)果
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 // 對猜測進(jìn)行判斷，返回結(jié)果
20 virtual char doJudge(int arr_index) = 0;
21 };
現(xiàn)在讓玩家玩一次游戲，直到猜成功：
1 // 玩一次游戲，返回猜測次數(shù)
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 // 設(shè)置裁判的正確結(jié)果
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 // 依據(jù)返回結(jié)果進(jìn)一步排除已有的可行排列
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工廠制造裁判和玩家（哈哈，批量生產(chǎn)）：
1 Player * player_factory()
2 {
3 return new NaivePlayer();
4 }
5
6 Judgment * judgment_factory()
7 {
8 return new HonestJudgment();
9 }
現(xiàn)在讓大家玩起來吧：
1 int main()
2 {
3 int time_stat[M]; // 次數(shù)統(tǒng)計表
4 Judgment *jp;
5 Player *pp;
6 // 獲取實例
7 jp = judgment_factory();
8 pp = player_factory();
9 // 初始化次數(shù)統(tǒng)計表
10 for (int i=0; i<M; i++)
11 time_stat[i] = 0;
12 // 初始化排列列表和關(guān)系矩陣
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 // 統(tǒng)計結(jié)果
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 }
得到的統(tǒng)計數(shù)據(jù)：
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
-------------
雖然頭腦簡單，但是還都能猜出來，只是次數(shù)多了點。
好了，現(xiàn)在整個框架搭起來了。現(xiàn)在的任務(wù)是尋找更聰明的玩家，讓猜測次數(shù)降下來。
還真找到了一個貪婪的玩家（算法原理見代碼注釋），且叫他 Clever1Player 吧：
1 class Clever1Player
2 : public Player
3 {
4 bool _cand[M]; // 排列是否可行的標(biāo)志矩陣
5 int _cand_count; // 當(dāng)前可行排列的個數(shù)
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 // 當(dāng)只有一個可行排列時，直接返回
20 if (_cand_count == 1) {
21 for (int i=0; i<M; i++)
22 if (_cand[i])
23 return i;
24 }
25 ///////////////////
26 // 悲觀假設(shè)：
27 // 假設(shè)無論猜什么排列，電腦總是能聰明地返回結(jié)果，
28 // 使得依據(jù)返回結(jié)果能進(jìn)一步排除掉的可行排列數(shù)目最少（即剩余的可行排列數(shù)目最多）
29 // 貪婪算法：
30 // 從可行排列中選擇下一次猜測的排列；
31 // 在悲觀假設(shè)總是成立的條件下，使得每次排除掉的可行排列數(shù)目最多（即剩余的可行排列數(shù)目最少），即求最好的最壞情況；
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 的時候，裁判將會返回一個結(jié)果；
40 // 根據(jù)悲觀假設(shè)，裁判返回的結(jié)果總是使得依據(jù)返回結(jié)果能進(jìn)一步排除掉的可行排列數(shù)目最少（即剩余的可行排列數(shù)目最多）
41 // cur_max 記錄該最壞情況下剩余的可行排列的數(shù)目
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，并記錄下當(dāng)前排列的序號
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 // 依據(jù)返回結(jié)果進(jìn)一步排除已有的可行排列
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 // 讓工廠開始生產(chǎn)我
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 // 當(dāng)只有一個可行排列時，直接返回
20 if (_cand_count == 1) {
21 for (int i=0; i<M; i++)
22 if (_cand[i])
23 return i;
24 }
25 ///////////////////
26 // 與Clever1Player的區(qū)別：
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 // 讓工廠開始生產(chǎn)我
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次之內(nèi)都能猜出來。只是為什么平均成績還不如 Clever1Player 呢？
這個問題，我得找時間問問他。
當(dāng)前Clever1Player時間復(fù)雜度為 (M*M*Time) ，其中Time為猜測次數(shù)。考慮次數(shù)總小于10，所以時間復(fù)雜度為 (M^2)。
我曾經(jīng)做過優(yōu)化，即使用一個數(shù)組保存可行排列序號，這樣在 Clever1Player 的 36 和 45 行就只需要掃描數(shù)組，而不需要每次都掃描 M 次了。當(dāng)然總的時間復(fù)雜度依然是 (M^2)。
Clever2Player 與 Clever1Player 的唯一區(qū)別在于 “去掉了Clever1Player 的第 38 行”，使得“下一次猜測的排列不局限于可行排列”。
基于的考慮是：
-------------
假設(shè)正確結(jié)果是 0124
第一次猜 0123 -> 3A0B
Clever1Player 接下來不能猜 4567 ，因為 4567 不在可行集中（已經(jīng)排除）。
但是Clever2Player 則有可能會猜 4567 得到 0A1B，直觀上說，猜測范圍就縮小到 01234567 中了，搜索空間減小很多。實際上我們?nèi)四X使用邏輯推理的時候通常就是這么考慮的，而且我們肯定是不會使用這種搜索算法的。
至于邏輯推理法與搜索法之間有什么聯(lián)系，我也不清楚。
-------------
另外，該算法的關(guān)注點在于猜測次數(shù)，即在于效果而不是效率。所以為了使算法看起來清晰，我沒有過多優(yōu)化。
NaivePlayer 算法執(zhí)行時間最快，大約1分鐘跑完所有5040種情況，Clever1Player大約5分鐘，Clever2Player大約10分鐘。
另外我也曾考慮過“動態(tài)規(guī)劃”算法，遞推公式： t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是當(dāng)前可行集，t(F) 為該可行集 F 條件下猜出結(jié)果的次數(shù)，f 為 F 中的一個可行排列。
但是我沒有編程實現(xiàn)，因為擔(dān)心復(fù)雜度太高運(yùn)行不完。
而貪心算法得到的應(yīng)當(dāng)不是最優(yōu)解，但是近似最優(yōu)解，而且從次數(shù)和執(zhí)行效率上來說都是可以接受的。
下一步做什么呢？
我們可以找一個狡猾的裁判，他讓玩家 Clever1Player 和 Clever1Player 的“悲觀假設(shè)”變成現(xiàn)實。
一邊是聰明的玩家，一邊是狡猾的裁判，哈哈，有好戲看了。
究竟鹿死誰手，請聽下回分解。
最后感謝
東坡_居士，讓我有機(jī)會接觸這么好玩的游戲。