下次自动登录
现在的位置:
& 综合 & 正文
围棋AI之路（二）棋盘的实现
先公布：http://download.csdn.net/source/891878
到现在为止，我只实现了一个棋盘，确切的说是在棋盘上随机走棋的速度测试，我借鉴了lib-ego，在上面做了一些改进，现在这个棋盘可以使用围棋规则或者五子棋规则。我的目标是让我的AI程序用同样的来对待围棋、五子棋甚至小时候玩过的黑白棋，它不需要任何棋类知识，你只要告诉它下棋的规则。我们的脑细胞可曾了解究竟什么是围棋？它们只是机械的执行自己的职能，而亿万个细胞堆叠在一起就使人类会下棋了。
上面说的三种棋的棋盘有一些共同的特点：棋盘是由n行n列的平行线段交叉组成的格子，棋子分黑白两种颜色，棋手分为两方，分执一种颜色的棋子。双方轮流下子，每次下一个子，棋子要下在空的交叉点上（黑白棋似乎是下在格子里，但是应该没有本质区别）。
根据这些特点我们开始设计棋盘的结构。
一、比特棋盘
很想在围棋中使用比特棋盘，就像国际象棋中那样，用一个64bit的数就描述了棋盘上的一种棋子。围棋上尽管也可以做到，例如用一个361bit的数来描述棋盘上的黑棋，另一个361bit数描述白棋，但是没见过谁这么做。
一般还是用传统的数组来描述棋盘，数组的每个元素有三个状态：黑(black)、白(white)、空(empty)。
为何计算机不是三进制的？我以前曾经这么想过，如果计算机是三进制的，会不会能更好的描述围棋？
后来我发现，其实棋盘上的点不只三个状态，还漏掉了一个off_board，也就是棋盘外的点。因此棋盘其实是4进制的，和2进制的计算机还是契合的不错的。
如何理解off_board也是一种状态？我们可以观察一下棋盘的边界，边界再往外就是off_board了，对围棋来说，通常的一颗子有4口气，但是到边界上就变成三口气或者两口气了，就仿佛边界外有敌人的子一样。对于五子棋，如果对方冲四冲到边界上，就不用挡了，就好像棋盘外有自己的棋子给它挡住了一样。
我按这种物理意义来为这些状态指派2进制数：
10off_board 11
这里empty就是没有棋子，black和white分别有一个棋子，而off_board则是同时有两个棋子，哪方的棋子靠近它，它就表现为另一方。
这样做的好处是，我可以用一个8bit的数来描述一个棋子的邻点，8bit总共256种情况，非常适合查表，通过查表，我就能得知任何情况下交叉点的“气”了。
关于计算交叉点的“气”，lib-ego中采用的另一种方法，它仅仅只增量计算交叉点周围黑、白、空三种情况的数量（off_board就分摊到黑白两种情况上了），而不管具体分布情况。目前我还没有发现我的方法表现出来的优势，但是我坚信我的方法比lib-ego中的好，因为它合乎道。
看起来，可以用一个8bit的数来存4个位置的状态，那么整个棋盘总共需要56个64bit数，比国际象棋没多太多，然而最终我没有贯彻比特棋盘的思想，因为我觉得那样不自然，我仍然选用传统的数组方式。
二、代码优化
许多人都指出优化应该晚做。但是对一份已经优化过的代码，如果不了解其优化手段，很难明白一些代码的意义。
1 使用编译期常量来代替变量。
例如棋盘的尺寸这个量，棋子的坐标计算依赖于它，为一些结构分配多大空间也与这个量相关。为了避免运行期再去计算这些东西，我们可以用宏或者const int来定义它：
const uint board_size = 9;
但是我们希望程序可以运行在9路，13路，19路棋盘上，而且运行中可以改变棋盘，因此我采用了template。基本棋盘结构类似下面这样：
template&uint T&
class Vertex {
const static uint cnt = (T + 2) * (T + 2);
template&uint T&
class Board {
static const uint board_size = T;
Color color_at[Vertex&T&::cnt];
这里Vertex表示棋盘的交叉点，Vertex的内部实现不用类似class CPoint{};这样的方式实现，而只用一个整数来表示坐标，因为许多时候处理一维数组时的速度要快过二维数组，尽管理论上它们是一样的。
2 控制循环
如果在代码中看到这样的宏定义
#define color_for_each(col) /
for (Color col = 0; color::in_range(col); ++col)
而充斥在代码中的大片的vertex_for_each_all、vertex_for_each_nbr的使用，C++的死忠们不要急于排斥它，(我知道C++中有“优雅”的不依赖宏的方式来实现for_each，我也知道这样带来了一种方言)，请先考虑一下为何需要for_each。
首先我们不希望在代码中出现大量for(;;)这样的语句，因为它会让代码行变的难看，并且以后修改困难。其次，我们有根据情况选择是否循环展开的需求。
for(int i = 0; i & 4; i++) {}
循环展开的效率提升不能一概而论，它与代码块的长度和循环次数都有关系，但是宏赋予了我们控制的能力。
这两个要求我不知道除了宏还有什么简单的方法可以做到。
3 避免条件语句
因为条件语句会影响CPU的指令缓存的命中率。为人熟知的一个用位运算来取代条件语句的例子是：
Player other(Player pl) {
if(pl == black) return
else return
改为位运算就是这样：
Player other(Player pl) {
return Player(pl ^ 3);
这里要假定black为1，white为2才能成立。如果black为0，white为1，则代码要改成(pl ^ 1)。
不过就这个例子来看，在我的CPU上没发现有什么效率的变化。在没有什么有说服力的例子出来之前，姑且存疑。
4 控制inline
需要清楚一点，inline不一定能提高运行速度。作为一个例子，请将代码中play_eye函数前面的no_inline修饰换成all_inline（表示总是内联），再编译运行一次看看，消耗的时间居然翻倍，为什么会这样？
这个函数的调用场景是：
return play_eye(player, v);
} else ...
实际运行中，play_eye的调用频度不太高，如果内联的话，那么前面的if判断如果走的不是play_eye的这个分支，就会导致指令指针跳过很长一段代码到达下面的分支，因此指令缓存会失效。
你也许会说现代编译器能把这些做的很好，不用你操心这些细节了。那好吧，其实我只是建议，在瓶颈的地方手工指定一下是否内联，也许会有意想不到的性能提升。（注意inline这个关键字只是建议编译器内联，编译器不做保证，但是编译器通常都提供了额外的指令让你精确控制要不要内联。）
5 查表代替运算
不要迷信查表，因为表通常存在内存中，而你的指令放在CPU的指令缓存中，如果一两条指令能算出来的东西你去查表有可能得不偿失。
三、类的设计
一般来说，表示规则和表示棋盘的类会实现为一个类，如果把规则和棋盘分开来的话，那么应用代码可以创建一个棋盘类，再根据要求附加不同的规则类，类似下面这样写：
board.attach(new GoRule&T&());
board.play(...);
看起来很优雅对不对？
但是在最终决定如何设计类结构之前，先看两点性能上的要求：
1) 不使用虚函数
原因是，除了虚函数表的空间开销，以及调用时多出来的几条机器指令外，虚函数使得编译器难以实现inline，因为虚函数是迟绑定，运行时才决定调用的函数是哪个，而C++编译器一般只能进行编译期的inline。
2) 棋盘可以快速被拷贝
记得我们的目的是让棋盘可以模拟很多盘随机对局，每一次随机对局都应该在原有棋盘的一个拷贝上进行，如果拷贝一次棋盘的代价很高的话，模拟的效率会很低。
现在，我们要否决上面的代码了，因为我们不能new一个规则类，这会破坏棋盘的快速拷贝能力，我所能想到的最快的棋盘拷贝代码是用memcpy，如果棋盘的数据成员含有指针，memcpy出来的棋盘会有问题。
继承怎么样呢？我们定义一个Board接口，也就是纯虚类，然后从这个接口继承，这是很通用的优雅解决方案，但是用到了虚函数。而且单继承会导致类数量过多，例如，我有一个基础的BasicBoard类，现在我希望能实现邻点计数功能，那么我写了一个NbrCounterBoard从BasicBoard类继承，我们的GoBoard可以从NbrCounterBoard继承。围棋还需要计算每一步棋的hash值，用以判定局面重复，那么我要实现一个ZorbistBoard，它从NbrCounterBoard继承，最终的GoBoard就从ZorbistBoard继承。黑白棋不需要计算hash，它可以直接从NbrCounterBoard继承，五子棋两个特性都不需要，那么它直接就从BasicBoard继承。一切听起来很完美，但这只是运气好而已，如果有一种棋需要hash但不需要邻点计算，这样的设计就over了。
组合可以吗？当然可以。看下面：
class GoBoard {
void GoBoard::foo(){ return zb.foo(); }
board.bb.bar();
void ZorbistBoard::foo(GoBoard* pGB) {
pGB-&bb.bar();
void GoBoard::foo(){ return zb.foo(this); }
我们看到，这样子代码显得很罗嗦。这把我由组合引向了多继承：
class GoBoard:
public BasicBoard&GoBoard&,
public ZobristBoard&GoBoard&
我借鉴了ATL库的做法，把GoBoard当做模板参数传进去，这样，当ZobristBoard需要调用BasicBoard方法时，可以这样做：
template&typename Derive&
class ZobristBoard {
void foo() {
Derive* p = static_cast&Derive*&(this);
四、模拟对局
我们这样来进行一场模拟对局：双方在规则的允许下，轮流下棋，当一方没有棋可下时，就pass，而双方接连pass时对局终止。对围棋和黑白棋来说，这样的过程是适应的，对于五子棋，我们需要加上中盘获胜的判断，实际上围棋中也可以用中盘胜来加快模拟速度，即一方已经明显优势的情况下，就不需要进行到双pass终局了。
首先我们看看围棋规则如何实现，围棋的三大规则，即提子（气尽棋亡）、打劫、禁同，造就了围棋的复杂性。如果没有提子，双方无论怎么下结果都是一样，如果没有打劫，双方互不相让也使得没有终局的可能。而禁同，也就是禁止全局同形，则可以看成是打劫的一般情况，也是为了防止对局无法终止。
还有一种情况也会导致对局无法终止，那就是双方都自填眼位，虽然这种情况理论上可以被禁同规则所限制，但是我是等不到对局结束的那一天了，何况这种求败并且寄希望于对方也求败的下法，在博弈程序中是不必考虑的。因此，在我们的随机模拟中，还要加上一条不填眼的规则。
在提子中还有一个分支，就是提自己的子，也即是自杀，一般比赛中是不允许自杀的，但是应氏规则中好像是允许的。模拟中肯定要禁止单个棋子的自杀行为，因为这也会导致无法终局（同上面一样，这种情况可以被禁同所限制，后面再说禁同的问题），但是多子的自杀究竟要不要在模拟中禁止？lib-ego中没有禁止，但是我发现禁止或不禁止导致的模拟胜率是有差异的，为了让模拟对局更贴近实际对局规则，我选择禁止多子自杀，尽管这需要更多的计算。
这样，在模拟中需要实现提子、打劫、不填眼、不自杀、禁同5个规则。而理论上我们只需要实现提子和禁同两个规则。
如果要实现禁同，我们需要为每一步棋形成的局面记录一个hash值，为了减少冲突的可能，一般使用64bit的hash值，然后如果这个hash值与以前的hash重复，则把这一步棋撤销。平均一局棋大概不超过1000步，那么进行二分查找是能够快速的判断hash重复的，但是如何撤销一步棋呢？要知道围棋是有提子的，如果这步棋出现提子，则撤销时还要将提去的子也放回来。每次提子记住那些被移走的棋子的位置，这是一个办法。lib-ego中采用了一种简单的、低效的的手段：无论是判断是否重复还是进行撤销，都根据历史棋步，把整个棋局重新下一遍。这种方法我初看时也觉得效率太低了，但是后来想通了，因为这样做，只额外存储了历史棋步，额外计算了hash。
其实这就是在表明，放弃在模拟对局中实现禁同，禁同只用到真正下棋的判断中。甚至我觉得更进一步，在模拟棋盘中，历史棋步与hash计算都不需要。因为现实对局中的全局同型是少之又少的，而检测全局同型的开销又太大，我们在模拟中设定一个棋局最大步数，凡是超过这个步数的模拟对局都弃掉不用，这样就绕开了禁同的问题。
为了高效的判断棋子的气，这里用到了“伪气”的技巧。只要有一个空的交叉点，那么这个交叉点周围的每个棋子都能得到一口气，这就叫伪气。举图为例
├┼┼┼┼
├┼┼┼┼
○○○┼┼
●●○┼┼
└●○┴┴
上图黑棋真实的气只有一口，但是按伪气来说，就有两口，因为那个空点连着两个黑子，每个黑子都算有一口气。
按照伪气的计算法，每下一子，就减掉上下左右共4口气，每提走一子，则加上4口气。有了伪气这个工具，再来计算提子就简单多了，伪气为0的棋串就从棋盘上移走。
那么棋串怎么弄呢？我们把棋串实现为一个循环链表。一开始单个棋子就自己和自己首尾相连，并且拥有一个棋串id（就取它的位置作为id值），如果两个棋子相邻了，而棋串id不同，那么把它们合并为一个棋串，由于它们都是循环链表，合并的过程就相当于两个环扭断再对接成一个更大的环，于是合并的结果依然是循环链表。
打劫用了一个简单的方式来判定：如果能够在对方眼的位置下子，并且刚好只提了一个子，那么提去的那个子的位置被记录为劫争位，劫争位每次下子前被清除，也就是说只要不下在劫争位，pass也好，劫争位就被清除，下次那个位置就被允许下子。
下围棋的应该知道如何判断真眼和假眼，当在棋盘中间被对方占据两个“肩”或者边角处被对方占据一个“肩”，眼就是假眼了，我们随机模拟时，只要这个眼还没有确诊为假眼，我们就不往眼里下子。这里会存在误判，例如下图，白棋两个眼按照我们的规则判断是假眼，但白棋是活棋：
├┼┼┼┼┼┼┼
●●●●●●┼┼
○○○○○●●┼
├○●●○○●┼
○●●┼●○●┼
○●┼●●○●┼
○●●○○○●┼
└○○○●●●┴
不过没有关系，我们禁止填眼的目的是让大多数情况都能终局，而不是防止电脑把活棋走死。
单子自杀的判定是，当在对方眼中下棋时，将上下左右的棋串的气依次减1，如果没有棋串的气等于0，那么这就是一次自杀行为，我们把气加回去，然后禁止它下这一手。如下图，白棋下A点是自杀，下B点不是自杀。
├┼┼┼┼
○┼┼┼┼
●○○┼┼
Ｂ●○┼┼
●●○┼┼
Ａ●○┴┴
多子自杀的判定是，当在一个没有气的交叉点上下子时，先把上下左右的棋串的气减1，然后判断，如果既没有让对方棋串的气为0，也没有使自己的至少一个棋串的气不为0，那么这就是一次自杀，我们再把气加回去。如下图，黑棋下A点是自杀，下B点或者c点不是自杀。
├○┼┼┼┼┼
○┼○○┼┼┼
●●Ｂ●○┼┼
○○●○○┼┼
●○○●○○┼
Ａ●○Ｃ●○┴
这里的要点是在合并棋串之前做判断，因为棋串一旦合并后就不方便拆开了。
五子棋规则的实现相比围棋要容易很多，只用仿照围棋棋串的合并算法，在4个方向上分别建立棋串，合并棋串后，判断一下4个方向上是否有棋串的长度大于等于5。对于五子棋的职业规则，如禁手和三手交换五手两打，我暂时就不考虑了。毕竟有黑石那么牛的程序在那里。
五、下一步
自然是引入UCT算法了，也有可能是UCG，也就是UCB for Graph。
&&&&推荐文章:
【上篇】【下篇】您现在的位置：&>&&>&&>&
育龙网&WWW.CHINA-B.C0M&& 日&&来源：互联网
核心提示：
快速小测试：如何重写下面的语句？要求不使用条件判断语句交换两个常量的值。ifx=b;elsex=a;答案：x=a^b^x;//此处变量x等于a或者等于
快速小测试：如何重写下面的语句？要求不使用条件判断语句交换两个常量的值。ifx=b;elsex=a;答案：x=a^b^x;//此处变量x等于a或者等于b字符^是逻辑异或XOR运算符。上面代码为什么能工作呢？使用XOR运算符，一个变量执行2次异或运算与另一个变量，总是返回变量自身。虽然Java位操作的魔术不是很普及，但是深入研究此技术有助于改善程序性能。在的机器下进行基准测试，重写版本需5.2秒，使用逻辑判断的版本需5.6秒。。减少使用判断语句通常可以提高在现代多管道处理器上的程序性能。对于Java程序员来说，特别有益的是一些用来处理所谓bitsets位集的技巧。Java语言中的原始类型int和long也可被视为32位或64位的位集合。可以组合这些简单的结构来表示大型，比如数组。另外，还有一些特定的运算，可以有效的将多个不同的运算压缩为一个运算。使用以bit为单位的细粒度数据，而不是以integer整数为运算单位，我们会发现――对于integer整数来说有时进行的仅仅一步运算，如果使用bit位作为运算单位实际上可能进行了许多操作。可以认为Java语言中的位并行运算是软件多通路技术的一种应用。高级对弈程序如Crafty使用了特殊的数据结构――bitboard位图棋盘来表示棋子的位置，这样比使用数组的速度快很多。与C程序员相比，Java程序员更不应该使用数组。与C语言中数组的高效实现相比，Java语言中的数组实现效率低下。为比较使用整数方案以及使用数组方案的性能，在机器上进行的简单测试显示使用数组方案的运行时间是使用整数方案的160%，并且此处未考虑无用单元回收对性能的影响。在某些情况下，可以使用整数位集替代数组。下面会探讨一下从时代就存在的古董技巧，同时特别关注这些技巧在位集上的应用。Java作为可移植语言本身对位运算提供了良好的支持。进一步，JavaTiger版本的API中又添加了一些用于位处理的方法。典型Java环境下的位优化Java程序运行在机器和之上，但是与机器和操作系统中充斥的位运算不同，Java程序基本上不包含大量的位运算。虽然现代提供了特殊的位操作指令，不过在Java语言中无法执行这些特殊指令。JVM仅提供了有符号移位、无符号移位、位异或、位或、位并以及位否等位运算。有意思的是，并不仅仅是Java没有提供额外的位运算，很多汇编程序员编写操作CPU的程序时，也会发现缺少同样的位运算指令。两类程序员在位运算上的境遇其实一样。汇编程序员不得不通过软件模拟来实现这些指令，同时尽可能的保证效率。Tiger版本的Java中许多方法也是通过使用纯java代码来模拟实现这些指令的。进行性能微调操作的C程序员可能会审查实际产生的汇编代码、参考目标CPU的优化器手册、统计代码执行的指令周期数目等方式来改善程序性能。与之相对，在Java程序里进行这样的底层优化的一个实际问题是无法确定优化的效果。Sun公司的Java虚拟机规范未给出某特定操作执行的相对速度。可以将自己认为执行速度快的代码一部分再一部分的在Java虚拟机中执行，结果只能令人震惊――速度没有提高甚至优化部分可能降低原来程序性能。Java虚拟机可能会搅乱破坏你做出的优化，也可能在内部对一般的代码优化。在任何情况下，通过JVM实现优化，即使编译过后的程序提供这样的支持，相应得优化也需要进行基准测试。标准的查看字节码的工具是JDK中包含的javap命令。的使用者也可以利用由AndreiLoskutov开发的字节码查看插件。Sun的网站上提供了JVM设计和指令集合的参考书的在线版本。注意，每个Java虚拟机内包含两种类型的内存.一种是栈，用来存储局部原始类型变量和表达式；另一种是堆，用来存储对象和数组。堆内存储的对象会被无用单元回收机制处理，而栈具有固定大小的内存块。虽然大多数程序仅仅使用了栈空间的很小部分，JVM规范声明认为栈至少有64k大小。请注意JVM可以被认为是一个32位或者64位的机器，所以字节byte以及位数少的原始类型的运算不大可能比整数int的运算更快。2的补数Java语言中，所有的整数原始类型都是有符号数字，使用2的补数形式表示。要操作这些原始类型，我们需要理解一些相关理论。2的补数分成两种：非负补数和负补数。补数的最高位，也是符号位，在一般系统上在最左边。非负补数的此位是0。可以简单的从左到右读取这些普通的非负补数，将他们转换到任意进制的整数。如果符号位设置为1，此数就是负数，除去符号位的右边位集合与符号位一起表示此负数。有两种方法来考察负的补数。首先，可以从可能的最小负数数起直到-1，比如，8位字节，从最小的开始，然后是，一直到。另外一种考虑负的补数的方式有些古怪，当存在符号位时，用前面都是1后面跟着个0来代替前面都是0后面跟着个1的方式。然而，你最后需要从结果中减去1。比如时符号位后面跟着7个1，表示负零，然后添加1，得到-1，同样是-2，是-3，以此类推。感觉上有些怪，我们可以混合位运算符号和数学运算符号来进行多种操作。比如将x变换为-x，可以表示为对x按位求反，然后加1，即+1，具体运算过程见下表。下面部分，就像烈酒伏特加和变幻莫测的镜子一样，其中的位运算变得很复杂。在冷战发展到顶点的时期，国际象棋是科学的一个研究热点。原苏联和美国各自独立的提出了新的象棋数据结构――位图棋盘。美国团队――Slate和Atkin，基于Chess4.x软件出版了《人类和机器的国际象棋技能》一书，其中有一章讨论了位图棋盘算法，这可能是最早的关于位图棋盘算法的印刷品。原苏联团队，包括Donskoy以及其他人员，开发了使用位图棋盘算法的程序Kaissa。这两个软件在世界范围都具有胜利性的竞争力。在讨论位图棋盘算法前，我们先来看看使用Java语言表示棋盘的标准方法。//棋盘上64个格子所有可能状态的整数枚举finalintEMPTY=0;finalintWHITE_PAWN=1;finalintWHITE_KNIGHT=2;finalintWHITE_BISHOP=3;finalintWHITE_ROOK=4;finalintWHITE_QUEEN=5;finalintWHITE_KING=6;finalintBLACK_PAWN=7;finalintBLACK_KNIGHT=8;finalintBLACK_BISHOP=9;finalintBLACK_ROOK=10;finalintBLACK_QUEEN=11;finalintBLACK_KING=12;//使用含有64个元素的整数数组表示64个格子intboard=newint[64];使用数组方法很直观，相反，位图棋盘算法的数据结构是使用12个64位的位集表示，每个表示一种类型的棋子。如下图，视觉上看上去好像是一个堆在另一个的上面。//为棋盘声明12个64位整数longWP，WN，WB，WR，WQ，WK，BP，BN，BB，BR，BQ，BK;图1.位图棋盘数据结构空的位图棋盘在那里？由于EMPTY位图棋盘可以通过其他12计算出来，因此声明它会产生冗余数据。为计算空位图棋盘，将12个位图棋盘相加后求反即可。longNOT_EMPTY=WPWNWBWRWQWKBPBNBBBRBQBK;longEMPTY=~NOT_EMPTY;象棋程序运行时需要生成很多合理的走棋步骤，从中挑选最佳的。这需要完成一些计算，以确定棋盘上被攻击的棋格，避免棋子在这些棋格上被攻击，这样王棋子被将的棋格以及被将死的棋格能够确定下来。每个棋子具有不同的攻击方式。考察处理这些不同攻击方式的代码，可以看到位图棋盘算法的一些优缺点。使用位图棋盘方案可以很优雅的解决一些程序任务，但在另外一些方面却不是这样。首先看王棋子，很简单的，王只攻击相邻棋格内的棋子。根据王在棋盘上的棋格的不同位置，被攻击的有3个到8个棋格。王可能位于棋盘中间格上、边上、或者角上，所有情况都需要代码处理。程序在运行时计算王的可能的64种攻击方式，首先从基本的方式考虑，具有8种攻击方式，然后推出特殊的情形下的攻击方式。首先，在中间的棋格上生成掩码，比如在第10个即B2。图2显示了几个表示掩码的long数值。图2确定王的攻击方式longKING_ON_B2=1L1L<<11L<<21L<<71L<<91L<<151L<<161L<<17;//王在B2时，被攻击的格子。"/>图4.有多少个兵在红色方格上位图棋盘模式的优势和不足国际象棋规则相当复杂，这也意味着用位图棋盘方法来处理这些规则时有优势也有不足。使用位图棋盘处理某些规则很快，处理另外一些时就比较慢。上面已经给出了使用位图棋盘方法的低效代码片断，位图棋盘算法并不是魔法粉，什么都可以高效实现。可以想象一种与国际象棋非常相近的游戏，应用位集运算会导致相反的效果或者根本不需要这样复杂。使用位集运算进行优化必须经过审慎的考虑。一般来说，位运算具有如下的优势和不足：优势：占用内存少具有高效的拷贝、设值、比较运算等位并行运算的可能不足:难于调试访问单独位的复杂性，易出错难于扩展不符合面向对象的风格不能处理所有的任务；需要大量的工作位图棋盘模式的概括为概括上面的象棋例子，可以将棋盘的水平和纵向的位置想象为两个独立的变量或者属性，这需要8x8一共64位来表示。另外，需要12层――每个棋子用一层表示。位图棋盘方案的扩展方式有两种：1)使用更多的位来扩展棋盘，添加更多的棋格2)使用更多的层来增加棋子。实际对弈每方有64位的最大限制。但是假设我们拥有一个128位的JVM，里面的具有128位的doublelong类型，有了这128位，棋盘上就有了足够的空间来在同一层中摆放黑白双方的16个兵。如此可以减少需要的层数量，并且可能简化一些难以理解的运算，但是却会增加处理单独一方兵的运算的复杂度并降低其速度。所有的Java位运算都会操作基本类型的所有位。数据在自己所在层内仅使用本身的各位进行位运算或者函数调用时，效率会高一些。使用位并行运算处理层内的所有位的速度比处理其中一些位的速度要快。对于增加的64位，我们可以获得一些巧妙的使用方法，但是我们不希望将12个棋子也混合进来。如果在同一层内使用多于2个变量，也可以同时改变一层的所有变量。考虑图5中表示的3Dtic-tac-toe游戏，3个轴向的每个轴向的上面可能有3变量，一共有333一共27个可能值。这样对局的每方需要使用一个32位的位集合。图5.3Dtic-tac-toe游戏的位模型进一步，串联多个64位集合可以用于实现Conway生命游戏，一个在大的栅格上进行的模拟游戏。游戏中新单元的生死由相邻单元的数量确定，游戏在一代代的单元繁衍中进行。当一个死去单元的周围具有3个生存单元时会复活。一个单元的相邻单元中没有生存的或者仅有一个生存的，这个单元就死亡了。具有多于三个相邻生存单元的单元也会死亡。相邻单元的出生、生活，死亡，会对当前单元的状态造成很多改变。图6中显示了一个生命构造图，它会不断繁衍，生存下去，从而通过栅格。使用下面描述的算法我们可以生成模拟生存过程的下一步：1.首先，与象棋游戏相似，除主栅格外另外声明8个栅格层，每层表示某单元格的八个相邻单元格中的一个。通过移位运算计算相邻单元格的生存数量。2.已经有了八个层次，需要计算每个单元格的运算和，声明9个额外的位集合来表示这些结果。比如，位集合变量SUM_IS_0到SUM_IS_8。这里可以使用递归算法，先计算2层的，然后计算3层、4层......直道第8层。3.获得相邻单元格生存数量后，可以容易的应用游戏规则产生单元格的下一代。统计各层表示的相邻单元格生存数量//S0表示“和为0”，其余类似//L1表示“第一层”，其余类似//Lookatjustthefirsttwolayers:层1和层2S0=~;S1=L1^L2;S2=L1&L2;//Nowlookatthethirdlayer:第3层S3=L3&S2;S2=;S1=;S0=S0&~L3;//Thefourthlayer.第4层S4=S3&L4;S3=;S2=;S1=;S0=S0&~L4;//Repeatthispatternuptothe8thlayer.重复此模式直到第8层计算8层的全部代码有42行，如果需要也可以增加些。不过这42行代码有些优点，其中没有使用逻辑判断――逻辑判断会降低处理器的速度，代码明了简单，可以通过即时或者热部署Java编译器的编译。最重要的是，对于全部64个单元格所需要的数值，是通过获得的。图6.生命游戏的模型与非游戏应用相比，位运算在游戏等应用中更容易得到应用。其原因是游戏应用如象棋的数据模型中位与位之间具有丰富的关系。象棋的数据模型具有12层64位的位集，合计共764位。768位中的每位基本上都同其余各位有一定形式的关联。在商业应用中，通常不具有这样紧密的关系。结论思想开放的程序员，可能在任何问题领域中应用位运算。然而，在特定情形下应用位运算合适与否取决于开发者的判断。老实说，可能根本就不需要使用这些技巧。不过，上面提到的方法在特定Java应用可能正是优化程序所需要的。如果不是这样，也可以使用这些方法以非常hacking的方式解决一些问题，同时迷惑你的朋友们！享受位运算的快乐吧！
相关热词搜索:
-- 本站部分信息来源于互联网，不代表本站观点或立场，如有侵权，请来电告知，我们将及时处理