生成魔术数字的最快方法

huangapple go评论81阅读模式
英文:

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 &amp; -this._bitboard
const lsb_index = this.GetLSBIndex(lsb)
this.XOr(lsb)
return lsb
}
GetLSBIndex(lsb) {
return Math.log2(lsb ? lsb : Number(this._bitboard &amp; -this._bitboard))
}

<!-- language: lang-js -->

function IndexToUBigInt64(index, bits, mask) {
const bitboard_mask = new BitboardClass(mask)
let result = 0n
for (let i = 0; i &lt; bits; i++) {
const square = bitboard_mask.PopLSB()
if (index &amp; (1 &lt;&lt; i)) result |= 1n &lt;&lt; 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 &lt;&lt; bits
//* The slowest part of the generation
for (let index = 0; index &lt; 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; _ &lt; 100000000; _++) {
const magic_number = GenerateMagicNumber()
if (BigInt(new BitboardClass((attack_mask * magic_number) &amp; 0xff00000000000000n).CountBits()) &lt; 6) continue
for (let index = 0, fail; !fail &amp;&amp; index &lt; occupancy_indicies; index++) {
const magic_index = (occupancies[index] * magic_number) &gt;&gt; (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(&quot;***Magic number failed***&quot;)
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 &lt;&lt; bits

	const attacks = new Array(number_of_bits)
	const occupancies = new Array(number_of_bits)

	for (let index = 0; index &lt; 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 &lt; 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
	}
}

huangapple
  • 本文由 发表于 2023年7月3日 02:26:32
  • 转载请务必保留本文链接:https://go.coder-hub.com/76600258.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定