我的大脑在试图理解这种比特板技术的原理。为了简单起见,让我们想象一下,与国际象棋和许多复杂的棋子动作不同,我们的游戏只有两个棋子,一个棋子有一排8个位置。一块是三角形,另一块是圆形,如下所示:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ ▲ │ │ │ ● │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
三角形可以像车一样移动。任意数量的水平位置,但不能跳过圆圈。
现在假设用户将三角形移动到最后一个位置,如下所示:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ ● │ │ ▲ │
└───┴───┴───┴───┴───┴───┴───┴───┘
对于这个例子,三角形移动位板是
1 1 0 1 1 1 1 1
圆圈位置遮罩是
0 0 0 0 0 1 0 0
很明显,这种移动是非法的,因为三角形不能跳过圆圈,但是软件如何使用魔法比特板技术来检查这种移动是否合法?
你是对的,不可能只使用按位操作来确定滑动块的有效移动。您需要按位操作和预先计算的查找表。
最新的国际象棋引擎正在使用一种被称为“魔法比特板”的技术。
实施方式各不相同,但基本原则始终相同:
>
执行T的按位与,并在板上使用占用方格的位掩码。让我们称后者为O(表示占用)。
将结果乘以一个神奇的值M,并将结果向右移动一个神奇的量S。这给我们I(代表索引)。
在查找表中使用I作为索引,以检索使用此配置可以实际访问的正方形位掩码。
总而言之:
I = ((T & O) * M) >> S
reachable_squares = lookup[I]
T、M、S和查找都是预先计算的,取决于工件的位置(P=0...63)。因此,更准确的公式是:
I = ((T[P] & O) * M[P]) >> S[P]
reachable_squares = lookup[P][I]
步骤#3的目的是转换64位值T
该算法的“魔法”部分是确定M和S值,这将产生一个尽可能小的无冲突查找表。正如Bo Persson在评论中指出的,这是一个完美的哈希函数问题。然而,到目前为止,还没有为magic Bitboard找到完美的哈希,这意味着使用中的查找表通常包含许多未使用的“孔”。大多数情况下,它们都是通过大规模的暴力搜索建立起来的。
现在回到你的例子:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ ▲ │ │ │ ● │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
7 6 5 4 3 2 1 0
这里,工件的位置在
[0…7]
中,占用位掩码在[0x00…0xFF]
中(因为它是8位宽)。
因此,基于位置和当前板构建直接查找表是完全可行的,无需应用“魔法”部分。
我们会:
reachable_squares = lookup[P][board]
这将生成一个包含以下内容的查找表:
8 * 2^8 = 2048 entries
显然,我们不能为国际象棋这样做,因为它将包含:
64 * 2^64 = 1,180,591,620,717,411,303,424 entries
因此,需要神奇的乘法和移位操作,以更紧凑的方式存储数据。
下面是一个JS片段来说明这种方法。单击棋盘以切换敌人的棋子。
var xPos = 5, // position of the 'X' piece
board = 1 << xPos, // initial board
lookup = []; // lookup table
function buildLookup() {
var i, pos, msk;
// iterate on all possible positions
for(pos = 0; pos < 8; pos++) {
// iterate on all possible occupancy masks
for(lookup[pos] = [], msk = 0; msk < 0x100; msk++) {
lookup[pos][msk] = 0;
// compute valid moves to the left
for(i = pos + 1; i < 8 && !(msk & (1 << i)); i++) {
lookup[pos][msk] |= 1 << i;
}
// compute valid moves to the right
for(i = pos - 1; i >= 0 && !(msk & (1 << i)); i--) {
lookup[pos][msk] |= 1 << i;
}
}
}
}
function update() {
// get valid target squares from the lookup table
var target = lookup[xPos][board];
// redraw board
for(var n = 0; n < 8; n++) {
if(n != xPos) {
$('td').eq(7 - n)
.html(board & (1 << n) ? 'O' : '')
.toggleClass('reachable', !!(target & (1 << n)));
}
}
}
$('td').eq(7 - xPos).html('X');
$('td').click(function() {
var n = 7 - $('td').index($(this));
n != xPos && (board ^= 1 << n);
update();
});
buildLookup();
update();
td { width:16px;border:1px solid #777;text-align:center;cursor:pointer }
.reachable { background-color:#8f8 }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</table>
我刚刚开始编写国际象棋引擎,但最近刚刚完成了我的第一个程序。但它运行得很慢,所以我切换到了比特板,现在切换到了魔法比特板。我经常使用国际象棋编程维基。 我现在尝试一个测试位置和perft函数,看看程序每秒可以计算多少节点(包括批量计数)。现在,我的perft函数被设置为只计算伪合法移动,我已经设置make_move函数不切换回合。因此我可以用perft分析位置R7/8/8/8/8/8/8 w。 然
此指令可与锁前缀一起使用,以允许指令原子执行。为了简化与处理器总线的接口,目的操作数接收一个写周期,而不考虑比较的结果。如果比较失败,则写回目标操作数;否则,将源操作数写入目标。 我很难理解最后一句(但可能也很难理解整个图表) 写回什么? 源操作数是什么?是吗?据我所知,这个CAS指令只接受一个操作数(内存目标)。 如果有人能重新措辞和/或解释关于无条件写入的这一点,我将不胜感激。
本文向大家介绍深入了解Java GC的工作原理,包括了深入了解Java GC的工作原理的使用技巧和注意事项,需要的朋友参考一下 JVM学习笔记之JVM内存管理和JVM垃圾回收的概念,JVM内存结构由堆、栈、本地方法栈、方法区等部分组成,另外JVM分别对新生代下载地址 和旧生代采用不同的垃圾回收机制。 首先来看一下JVM内存结构,它是由堆、栈、本地方法栈、方法区等部分组成,结构图如下所示。 JVM
正如标题所解释的,我有一个非常基本的编程问题,但我还没有找到。过滤掉所有(非常聪明的)“为了理解递归,你必须首先理解递归。”各种在线线程的回复我仍然不太明白。 当我们面对不知道自己不知道的事情时,我们可能会提出错误的问题或错误地提出正确的问题。我将分享我的“想法”。我的问题是希望有类似观点的人能够分享一些知识,帮助我打开递归灯泡! 以下是函数(语法用Swift编写): 我们将使用2和5作为参数:
备注:Electron 的原名是 Atom Shell。 与 NW.js 相似,Electron 提供了一个能通过 JavaScript 和 HTML 创建桌面应用的平台,同时集成 Node 来授予网页访问底层系统的权限。 但是这两个项目也有本质上的区别,使得 Electron 和 NW.js 成为两个相互独立的产品。 1. 应用的入口 在 NW.js 中,一个应用的主入口是一个页面。你在 pac
我不明白嵌套for循环是如何工作的。正在执行升序程序,请逐步解释它的工作原理 输出: 之后: