一个老题，扑克博弈

风云剑

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++了，其它语言基本不会用了。

1. 
   
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. }
    
47. 
    
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. }
    
70. 
    
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. }
    
81. 
    
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的局面）