dou di zhu

gistfile1.txt

斗地主人工智能  [2007-3-7]	
http://www.ylog.net/blog_show.asp?log_id=2148  

近一周在制作斗地主纸牌游戏的人工智能

算法主要是用宽度优先生成一棵搜索树

再根据玩牌的技巧进行剪枝与判权....

节点权值判断主要由有限状态机构成

剪枝是非常重要的,刚写成时生成的树居然有几百万个结点 

经过一天的剪枝后,平均只有十万左右了

=======
汇报一下,AI的部分基本做完了. 
这个AI比较好的实现是进行广度优先搜索,然后估价,如果搜索足够的层,就能找出最优解 
因为我是做手机游戏,资源有限,所以一开始就放弃了硬搜索的方法. 
经高人指点,最后采用了一种类似贪婪法的方法对牌进行估价,效果还可以 
实现思路是这样 
给每种牌型一个权重基数,然后用这个基数和该牌型的张数算一手牌的权重值. 
每次从手中所有牌中找出一手权重最大的牌 
一直到所有牌被划分为若干手,能得到一个手中牌的权重值的和 

＝＝＝＝

主动判断是更为复杂的逻辑性判断，即从当前存在的数据中分析，做多次对比后进行状态机的跳转。如“斗地主”中，对手中牌进行分析，达到最小出牌次数，最大出牌量，减少被压制性出牌的可能性的判断。从炸弹到顺子到单牌的出牌，以及对应的方案进行详细分析。这可能需要另一个机制---模糊逻辑的参加才能达到效果，当我们预先把所有数据进行整理后就能清晰看见大致的出牌顺序。这样就有了主动的状态性。当在游戏中，对方使出了招数进行压制，这时就会出现另一套状态机制，被动状态。这里又需要有一套逻辑进行分析，使之返回到主动状态。。。

无论被动状态还是主动状态，这也只是状态机的一级，进行二级后需要对每次出牌或压制式出牌进行第二论逻辑判断，并需要对每次手中牌再次进行分析。得到最佳出牌方案。当然上述也只是思想中的一种模型，实例化还需进一步的测试得出结果.

＝＝＝＝

http://blog.csdn.net/wj008/article/details/5061629

=======

http://blog.sina.com.cn/s/blog_7855dce90100u1qq.html

全新四人斗地主AI实现中 (2011-09-10 15:25:10)转载▼
标签： 杂谈	
四人斗地主的规则是由中国象棋棋王胡荣华总结和定型的，主要流行于浙江、江苏和上海，使用两副牌，包括两张大怪和两张小怪共108张。每个玩家发25张牌，留8张底牌给地主，地主独自拿到33张牌，来对抗其他三个农民。
 
斗地主游戏的计算机实现，已经有很多版本。有很多文章介绍人-机斗地主游戏的人工智能。本博客准备采用全新的算法，实现更加合理的出牌逻辑。这种算法除了考虑牌型外，还考虑牌型的控制力，以及这种控制力的动态变化。这样可以达到，从严格意义讲，计算机的胜率会很高。


http://blog.sina.com.cn/s/blog_7855dce90100u2nb.html

斗地主算法逻辑中的天之道  	 (2011-09-11 20:24:51)转载▼
标签： 杂谈	
声明：本博客的文章，主要是探究斗地主游戏算法的计算机实现。顺便介绍其中的本质性内容。如有游客照此操练，输了家当，本博客概不负责。
 
要在一轮斗地主游戏中获胜，手持的牌，需要具备一定的条件。首先是各中牌型需要有控制力，通常，炸弹、顶级牌型是有控制力的牌；其次，各种牌型的资源消耗要足够小。请看下面的例子，来深入理解这段话。
为简化问题的描述，假设是双人游戏，用红方与黑方来表示。红方手持7、6、5三个单子，而黑方手持8、6、5三个单子，轮到红方出牌。在此残局中，红方先出6能获胜，出5、7都失败。看起来很简单，但为什么出6能获胜，这其中包含的道理是什么？
要说清楚其中的道理，先要做点铺垫工作。
首先我们假设，对于最小的单子3，当发出这张单子后，如果要收回控制权，那么手中必须要有顶级大牌，通常，对于单子，顶级大牌就是大王（暂时不考虑炸弹），这时，我们就定义，3消耗了一个完整资源，反过来，也就是说，3的资源产生能力为负值，我们用记号3(-1)来表示。括弧中的-1表示负资源。
以此类推，单子5，6，7，8的资源产生能力简记为 5(-0.9)、6(-0.8)、7(-0.7)、8(-0.6)。这样假设后，通过简单累加括弧中数字，我们就可以得到红方与黑方的资源产生能力，如下，
红方资源产生能力 = 5(-0.9) + 6(-0.8) + 7(-0.7) = -0.9 - 0.8 - 0.7 = -2.4
黑方资源产生能力 = 5(-0.9) + 6(-0.8) + 8(-0.6) = -0.9 - 0.8 - 0.6 = -2.3
另外，黑方的8，在此残局中，是顶级大牌，属于具有绝对控制权的一张牌，其资源产生能力是正的，算作+1，这样：
红方资源产生能力 = -2.4， 黑方资源产生能力 = -1.3.
从上面的两个数字中可以看到，红方牌的资源产生能力比黑方弱，表面上看，红方似乎必败。当然，如果是黑方先手，黑红具有资源优势，只要黑方不先出8，红方是没有赢的可能的。这里，红方具有优先决定权，他需要决策出哪张牌。那么红方的决策依据是什么？
我们来观察双方各自出掉一张牌后的，手中持有牌的资源产生能力，
红方
出牌/ 剩余牌的资源产生能力
5       -1.5
6       -1.6
7       -1.7
黑方
出牌/ 剩余牌的资源产生能力
5       -1.4   -0.4（加算牌张8的绝对控制力）
6       -1.5   -0.5（加算牌张8的绝对控制力）
8       -1.7   -2.7（加算牌张8的绝对控制力）
上述计算结果，我们用图表来表示，看得更清楚一点
 

从上图，我们可以看到，当黑方某牌张消失后，黑方剩余牌的资源产生能力将严重恶化，至少不比红方占有，此变化点出现在第二手牌之后。这是黑方的死穴。这样，红方的决策目标就是寻找这样的死穴。
红方先手出5，黑方盖过6后，黑方剩余牌的资源产生能力仍然强于红方。而红方先手出6后，黑方的任何决策都将导致资源产生能力的严重恶化。这充分体现了老子在道德经中所描述的“天之道损有余而补不足”，用在此场合，就是要消耗对方的资源。
实际上，在斗地主过程中，各位游客也都是这样实践的。这篇文章要说的一个规律是，手持三手同种牌型的先手方，出中间张，胜算概率最大。 

斗地主中庸之道  	 (2011-09-12 14:58:13)转载▼
标签： 杂谈	
声明：本博客，旨在探究斗地主游戏算法的计算机实现。顺便介绍游戏技巧。如有游客照此操练，输了赌局赔了钱，本博客概不负责。
 
这篇博文，介绍”三单子出中间张“这一规律的形式证明。作为结论，取中庸之道，游戏获胜的概率大。对证明过程不感兴趣的游客，请跳过此博文。
 
前文《。。。天之道》引入了两个基本概念，牌张的控制力和牌张的资源消耗力。控制力描述对牌局的控制能力，如手中的大牌；而资源消耗力，描述的是一张牌出手后，重新夺回控制权需要消耗的资源。理论上讲，在不考虑炸弹、牌张顶死情况下（这些情况，放在后续博文讨论），大王具有绝对控制权，我们可以说，大王的资源消耗力为0；对于最小的牌3，它的资源消耗力可以被定义为-1；
我们用R(X)来表示牌张X的资源消耗力，那么R(大王) = 0, R(3) = -1;
对于大王、小王、2AKQJT9876543顺次排列的各张牌，假定各张牌的消耗力符合线性规律。那么，对于任何牌张X，存在表达式R(X) = ( 17 -  X ) * k; 其中 k = -1/14,表示线性分布的斜率。
如果手持X、Y、Z三张单子，那么，资源消耗力是R(X)、R(Y)、R(Z)的和，简记为R(X,Y,Z)。不难证明R(X,Y,Z)=51*k - (X+Y+Z)*k;
继续采用前文的残局例子，红方手持5、6、7三张牌，黑方手持5、6、8三张牌，我们用r、R分别表示红方、黑方资源消耗力。这样：
r(5,6,7) = -2.36; R(5,6,8)= - 2.29;
当红黑各方出手一张牌后，其手持牌的资源消耗力分别为：
红方：r(5,6) = -1.64, r(5,7) = -1.57, r(6,7) = -1.50;
黑方：R(5,6) = -1.64, R(5,8)  = -1.50, R(6,8)   = -1.43;
上述计算结果，我们用下图来表示。其中横向表示出牌方向，纵向表示资源消耗力。


上图表示，只要黑方的资源消耗力态势与红方存在交叉，红方合理选择出手的第一张牌，红方就有可能获得优于黑方的资源优势。r(5,7)真是体现这种优势的一手牌。关于这张图的更一般性解释，在这里，博客要埋设一个关卡。有兴趣的游客不难通过其他例子来获得中庸之道的秘密。

============

克牌的存储方式 (2011-09-12 15:35:15)转载▼
标签： 杂谈	
一张扑克牌的面值及花色用一字节表示，高四位表示花色，低四位表示面值。如高四位1、2、3、4、5分别表示黑桃、红桃、方块、梅花、王牌。低四位从0x00到0x0C,分别表示123456789，10JQK。大王0x5E,小王0x5D。
这样一副牌就可以表示为：
0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1A,0x1B,0x1C（黑桃）
0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2A,0x2B,0x2C（红桃）
0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3A,0x3B,0x3C（方块）
0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4A,0x4B,0x4C（梅花）
0x5D,0x5E（王牌）
这样表示后，游戏AI的编制非常方便。