qinzuoyan

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 16 Comments :: 0 Trackbacks

常用链接

留言簿(3)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

最近一个朋友在用计算机模拟人来玩文曲星上的“猜数字”游戏,也邀我一起讨论。我以前没有玩过,不过发现这个还是蛮有趣的,于是也想写一个能猜数据的小程序。

通过几日思考,终于实现了一个稍微有点聪明的。以下是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/<< 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
    
-------------
虽然头脑简单,但是还都能猜出来,只是次数多了点。

好了,现在整个框架搭起来了。现在的任务是寻找更聪明的玩家,让猜测次数降下来。

还真找到了一个贪婪的玩家(算法原理见代码注释),且叫他 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 的“悲观假设”变成现实。
一边是聪明的玩家,一边是狡猾的裁判,哈哈,有好戏看了。
究竟鹿死谁手,请听下回分解。

最后感谢东坡_居士,让我有机会接触这么好玩的游戏。

posted on 2009-08-14 14:11 左言 阅读(3097) 评论(15)  编辑 收藏 引用

Feedback

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 14:41 东坡_居士
Clever1Player 思路基本了解了,Clever2Player 不明白
程序没看,感觉看不懂c++面向对象了。。。

还有一个问题,这个程序复杂度多少啊?或者说跑出这个结果要多久?  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:04 左言
@东坡_居士

当前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分钟跑完所有,Clever1Player大约5分钟,Clever2Player大约10分钟。


  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:17 东坡_居士
恩,确实可以用可行解之外的做试探,我之前也想到这点,总感觉不可思议,犹豫之下为了少算几次就没用了~

找最好最坏那一步再描述一下?是否有递归啊?是否对算过的集合做记录?  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:18 左言
@东坡_居士


回复东坡_居士:你的算法“如果这个“提问”得到的“答案”种类越多,每个答案下面的可能数字就越少”,实际上可以通过对Clever1Palyer的进行修改实现:
34 int all_max = 0;
35 int all_max_index;
36 for (int i=0; i<M; i++) {
37 // 对于每一个可行排列 Ri
38 if (_cand[i]) { // 这一行也可以去掉
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] > 0)
51 cur_max ++;
52 // 如果 cur_max 小于全局 all_max,则更新 all_max,并记录下当前排列的序号
53 // 这样能找到种类数最多的情况
54 if (cur_max > all_max) {
55 all_max = cur_max;
56 all_max_index = i;
57 }
58 }
59 }

所以我的假设是最坏假设,你的假设是等概率假设。呵呵,你把裁判想得比较善良。
  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:22 左言
@东坡_居士
最好最坏就是说:每一行求最大(最坏),然后对所有行的最大值中取最小(最好)。所以计算过程还是 O(M^2) 的。  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:32 东坡_居士
@左言
恩,我理解错了~

我之前想的新的思路是这样:

因为问题的根源都在于我们怎样评价一个状态的好坏,我们现在都用数字的多少区评价,数字越多越糟糕。这个评价还是很初级简单的。

显然,既然求最小步数,那么最准确的评价就是,这个状态可以(平均、最坏)多少步得到解。

但是,这个评价标准需要递归(太慢,我测试9876用了十几分钟),或者记录状态(太大存不下)

我现在在想这个的优化~希望在可接受时间内跑出所有解~  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:44 左言
@东坡_居士
我猜测你也在考虑“动态规划”方法。
我考虑过“动态规划”算法,递推公式: t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是当前可行集,t(F)为该可行集 F 条件下猜出结果的次数,f 为 F 中的一个可行排列。
但是我没有编程实现,因为担心复杂度太高运行不完。但是可以保证这样能得到最优解。
贪心算法得到的应当不是最优解,但是近似最优解,而且也是可以接受的。  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:49 左言
@东坡_居士
上面公式还可以进一步修改一下:
t(F) = min{ t( F- conf(f) ) + 1, for all f belongs to F}, 其中conf(f)指与f冲突的集合(每一种返回结果就对应一个冲突集,所以复杂度又上升了)。  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 15:55 东坡_居士
@左言

恩,是这样,我现在觉得能存下来,不过需要hash一下,时间上应该还行,一两个小时我也认了~呵呵~

还有一个问题是这样,在一个可行解集合里,每一个数的概率是一样的吧?  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-14 16:06 左言
@东坡_居士

我觉得不应当考虑概率,而应当考虑在任意时刻,可行解集合里任何数都有可能是正确结果。实际上就是在一个状态转移图中,任何可行的路径都有可能沿着走下去,每选择一个数,就走进了一个分支。
  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-15 06:54 空明流转
我当年就是直接枚举法的,没搞那么复杂。。。  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-15 11:35 凡客诚品
没搞那么复杂。。。   回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2009-08-15 20:05 左言
@空明流转

直接枚举法,你说的是对5040种排列依次猜测吗。。。?最坏情况下猜测次数可能5040次吧。或者你有更好的办法吗?
  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现 2010-05-06 18:48 zt
通过信息熵来看,最少的次数应该是3.7次。所以还是有些开发的空间。。求大牛啊。  回复  更多评论
  

# re: 文曲星“猜数字”游戏的计算机模拟 —— 算法分析与实现[未登录] 2011-01-27 17:35 zz
你这不严谨啊。这个问题其实就是博弈,电脑想成会变卦的电脑,猜数的步数取判决步数中最大的,判决步数取猜数字最小的  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理