英文:
Fastest way to generate magic numbers
问题
我了解魔术位棋盘的工作原理,它主要用于减少特定占用位棋盘上的位数,以将已有的占用位棋盘转换为较小的值以提高速度。
您有一段代码,允许您生成车和象的魔术数字,目前在A i5 10400F上生成车的时间约为5.9秒,而生成象的时间约为0.05秒。
您正在尝试多次生成车和象的魔术数字,试图获得更小的魔术数字,但由于某个索引的占用生成需要一些时间,等待生成完成可能会有点疲惫。
我认为与弹出最不显著的位有关:
//* 位棋盘类
PopLSB() {
if (this._bitboard === 0n) return -1n
const lsb = this._bitboard & -this._bitboard
const lsb_index = this.GetLSBIndex(lsb)
this.XOr(lsb)
return lsb
}
GetLSBIndex(lsb) {
return Math.log2(lsb ? lsb : Number(this._bitboard & -this._bitboard))
}
function IndexToUBigInt64(index, bits, mask) {
const bitboard_mask = new BitboardClass(mask)
let result = 0n
for (let i = 0; i < bits; i++) {
const square = bitboard_mask.PopLSB()
if (index & (1 << i)) result |= 1n << BigInt(square)
}
return result
}
function FindMagicNumber(square_index, bits, diagonal) {
const occupancies = new Array(4096)
const attacks = new Array(4096)
const used_attacks = new Array(4096).fill(0n)
const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
const occupancy_indicies = 1 << bits
//* 生成中最慢的部分
for (let index = 0; index < occupancy_indicies; index++) {
//* 导致生成需要一段时间的部分
occupancies[index] = IndexToUBigInt64(index, occupancy_indicies, attack_mask)
attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
}
for (let _ = 0, fail = 0; _ < 100000000; _++) {
const magic_number = GenerateMagicNumber()
if (BigInt(new BitboardClass((attack_mask * magic_number) & 0xff00000000000000n).CountBits()) < 6) continue
for (let index = 0, fail; !fail && index < occupancy_indicies; index++) {
const magic_index = (occupancies[index] * magic_number) >> (64n - BigInt(bits))
if (used_attacks[magic_index] === 0n) {
used_attacks[magic_index] = attacks[index]
} else if (used_attacks[magic_index] !== attacks[index]) {
fail = 1
}
}
if (!fail) return magic_number
}
console.log("***魔术数字失败***")
return 0n
}
我已尝试使用Math.clz32
,但这只会使生成变得更慢。还有其他尝试方法,比如使用while循环,我也想尝试使用wasm i64,但不知道如何使用它。
英文:
I have some idea of how the magic bitboard works, really it just lessen the amount of bits on a certain occupied bitboard and to convert the already available to save occupied bitboard to a smaller value to increase its speed.
So I have this code which allows me to generate the rooks and bishops magic number, currently the generation time for rooks is about 5.9s on A i5 10400F, while on the bishops takes about 0.05s.
I am trying to generate the magic numbers for both the rook and bishop multiple times, trying to get a smaller and smaller magic number, however since the generation for the occupancy for a certain index takes a while, its quite tiring waiting for the generation to complete.
I think it has to do with poping the least significant bit:
<!-- language: lang-js -->
//* bitboard class
PopLSB() {
if (this._bitboard === 0n) return -1n
const lsb = this._bitboard & -this._bitboard
const lsb_index = this.GetLSBIndex(lsb)
this.XOr(lsb)
return lsb
}
GetLSBIndex(lsb) {
return Math.log2(lsb ? lsb : Number(this._bitboard & -this._bitboard))
}
<!-- language: lang-js -->
function IndexToUBigInt64(index, bits, mask) {
const bitboard_mask = new BitboardClass(mask)
let result = 0n
for (let i = 0; i < bits; i++) {
const square = bitboard_mask.PopLSB()
if (index & (1 << i)) result |= 1n << BigInt(square)
}
return result
}
function FindMagicNumber(square_index, bits, diagonal) {
const occupancies = new Array(4096)
const attacks = new Array(4096)
const used_attacks = new Array(4096).fill(0n)
const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
const occupancy_indicies = 1 << bits
//* The slowest part of the generation
for (let index = 0; index < occupancy_indicies; index++) {
//* Responsible for the generation to take a while
occupancies[index] = IndexToUBigInt64(index, occupancy_indicies, attack_mask)
attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
}
for (let _ = 0, fail = 0; _ < 100000000; _++) {
const magic_number = GenerateMagicNumber()
if (BigInt(new BitboardClass((attack_mask * magic_number) & 0xff00000000000000n).CountBits()) < 6) continue
for (let index = 0, fail; !fail && index < occupancy_indicies; index++) {
const magic_index = (occupancies[index] * magic_number) >> (64n - BigInt(bits))
if (used_attacks[magic_index] === 0n) {
used_attacks[magic_index] = attacks[index]
} else if (used_attacks[magic_index] !== attacks[index]) {
fail = 1
}
}
if (!fail) return magic_number
}
console.log("***Magic number failed***")
return 0n
}
I have tried using the Math.clz32
but this just made the generation slower. there where also other ways that I have tried such as using a while loop, I also wanted to try the wasm i64 but have no idea how to use it.
答案1
得分: 0
我想到了不同的方法,并提出了在调用生成函数时初始化攻击和占位的想法。我认为生成过程一遍又一遍地使用相同的攻击和占位。因此,我只需将攻击和占位保存在 A 对象上,然后为下一代索引攻击和占位以供使用。
现在,从车到目标的秒数约为 0.125 秒,而从主教约为 0.008 秒。我能够在 13-14 秒内完成 100 代。
function GenerateAttacksAndOccupancies(square_index, bits, diagonal) {
const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
const number_of_bits = 1 << bits
const attacks = new Array(number_of_bits)
const occupancies = new Array(number_of_bits)
for (let index = 0; index < number_of_bits; index++) {
attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
occupancies[index] = IndexToUBigInt64(index, number_of_bits, attack_mask)
}
return { attacks, occupancies }
}
function InitSliderAttacksAndOccupancies() {
for (let square_index = 0; square_index < 64; square_index++) {
const _level = GenerateAttacksAndOccupancies(square_index, LEVEL_BITS[square_index], false)
LEVEL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _level.attacks
LEVEL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _level.occupancies
const _diagonal = GenerateAttacksAndOccupancies(square_index, DIAGONAL_BITS[square_index], true)
DIAGONAL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _diagonal.attacks
DIAGONAL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _diagonal.occupancies
}
}
英文:
I thought of something different and came up with the idea of initializing the attacks and occupancies, when the Generation function is called. I figured that the generation is using the same attacks and occupancies over and over again. With that, I just need to save the attacks and occupancies on A object, then index the attacks and occupancies for the next generation to use it.
Now the amount of seconds from the rook is about 0.125s, as for the bishop about 0.008s. I am able to complete 100 generation in 13-14 seconds.
function GenerateAttacksAndOccupancies(square_index, bits, diagonal) {
const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
const number_of_bits = 1 << bits
const attacks = new Array(number_of_bits)
const occupancies = new Array(number_of_bits)
for (let index = 0; index < number_of_bits; index++) {
attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
occupancies[index] = IndexToUBigInt64(index, number_of_bits, attack_mask)
}
return { attacks, occupancies }
}
function InitSliderAttacksAndOccupancies() {
for (let square_index = 0; square_index < 64; square_index++) {
const _level = GenerateAttacksAndOccupancies(square_index, LEVEL_BITS[square_index], false)
LEVEL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _level.attacks
LEVEL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _level.occupancies
const _diagonal = GenerateAttacksAndOccupancies(square_index, DIAGONAL_BITS[square_index], true)
DIAGONAL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _diagonal.attacks
DIAGONAL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _diagonal.occupancies
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论