一个老题，扑克博弈

风云剑

A,B两人玩一个游戏,每位参加者发18张牌:三张6点,三张5点,三张4点,三张3点,三张2点,三张1点. 他们轮流出牌,A先出一张,B再出一张,每轮不能不出牌. 谁先出的牌使得桌子上的牌的全部点数之和等于50谁就算赢了, 但若那张牌使全部点数之和超过了50,他就算输了.问A和B谁有必胜策略?

zgg___

倒想起了原来编递归函数来算阶乘。

gxqcn

A先出1点，以后看B出x点，则自己出(7-x)点，这样使桌面上的点数总和保持为(7k+1)型，可拿到50的情形。 B看出了苗头，并利用A手头1点数目不足的弱点，最后三轮中连出6点，让A无法形成上述策略而告输。 抛砖引玉。具体怎样设计策略而稳赢，还没想好。

无心人

那显然A的策略是必输策略阿 呵呵

mathe

可以用程序解决吗？用程序复杂度不高

mathe

有简单的方法吗？计算机说只要先手先出3,4,5或6都可以赢

无心人

能不能出示你的程序 另外，这种策略类的游戏 能不能不用C/C++程序 Prolog/Lisp/Haskell/SML/Python等都可以 唯独不要用C/C++，呵呵

mathe

习惯用C/C++了，其它语言基本不会用了。

2. #include <stdio.h>
3. #define LIMIT (1<<24)
4. int states[LIMIT];
5. #define FAIL -1
6. #define SUCC -2
7. void gen(int left){
8. int first_u=left&((1<<12)-1);
9. int second_u=left>>12;
10. int cfirst,csecond;
11. int i,sum;
12. cfirst=csecond=0,sum=0;
13. for(i=0;i<6;i++){
14. int c1=(first_u>>(2*i))&3;
15. int c2=(second_u>>(2*i))&3;
16. cfirst+=c1;
17. csecond+=c2;
18. sum+=(c1+c2)*(i+1);
19. }
20. sum=126-sum;
21. if(sum>50){
22. states[left]=FAIL;
23. }else if(sum==50){
24. states[left]=SUCC;
25. }else{
26. int s[6],j;
27. for(i=0;i<6;i++){
28. s[i]=(first_u>>(2*i))&3;
29. }
30. for(i=0;i<6;i++){
31. int new_u=first_u;
32. int reach;
33. if(s[i]>0){
34. new_u-=1<<(2*i);
35. }
36. reach=second_u|(new_u<<12);
37. if(states[reach]==SUCC)
38. break;
39. }
40. if(i<6){
41. states[left]=FAIL;
42. }else{
43. states[left]=SUCC;
44. }
45. }
46. }
48. void output_states(int x);
49. int next_state(int x)
50. {
51. int first_u=x&((1<<12)-1);
52. int second_u=x>>12;
53. int i,s[6];
54. for(i=0;i<6;i++){
55. s[i]=(first_u>>(2*i))&3;
56. }
57. int reach=-1;
58. for(i=0;i<6;i++){
59. int new_u=first_u;
60. if(s[i]>0){
61. new_u-=1<<(2*i);
62. reach=second_u|(new_u<<12);
63. if(states[reach]==SUCC){
64. output_states(reach);
65. }
66. }
67. }
68. return reach;
69. }
71. void output_states(int x)
72. {
73. printf("State %06x:",x);
74. if(states[x]==SUCC){
75. printf("F");
76. }else{
77. printf("S");
78. }
79. printf("\n");
80. }
82. int main()
83. {
84. int i;
85. for(i=0;i<LIMIT;i++){
86. gen(i);
87. }
88. output_states(LIMIT-1);
89. printf("next states:\n");
90. next_state(LIMIT-1);
91. return 0;
92. }

复制代码

gxqcn

原帖由 mathe 于 2008-7-2 09:31 发表 有简单的方法吗？计算机说只要先手先出3,4,5或6都可以赢

可否用文字具体叙述之后的出牌策略？

mathe

程序用一个24比特的整数表示牌局中一个状态， 低12比特代表接下去出牌的人手中牌的状态，高12比特代表另外一个人手中牌的状态。 其中12比特可以看成6个两比特的数据，分别代表持有1,2,3,...,6的数目(0~3张) 然后一次计算各个局面是先手胜还是先手负，结果SUCC表示先手负(无论怎么出牌都会达到FAIL局面)，FAIL表示先手胜局面(存在一种出牌方案留下SUCC的局面）