生成魔术数字的最快方法

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

Fastest way to generate magic numbers

问题

我了解魔术位棋盘的工作原理，它主要用于减少特定占用位棋盘上的位数，以将已有的占用位棋盘转换为较小的值以提高速度。

您有一段代码，允许您生成车和象的魔术数字，目前在A i5 10400F上生成车的时间约为5.9秒，而生成象的时间约为0.05秒。

您正在尝试多次生成车和象的魔术数字，试图获得更小的魔术数字，但由于某个索引的占用生成需要一些时间，等待生成完成可能会有点疲惫。

我认为与弹出最不显著的位有关：

  1. //* 位棋盘类
  2. PopLSB() {
  3. 	if (this._bitboard === 0n) return -1n
  5. 	const lsb = this._bitboard & -this._bitboard
  6. 	const lsb_index = this.GetLSBIndex(lsb)
  7. 	this.XOr(lsb)
  9. 	return lsb
  10. }
  12. GetLSBIndex(lsb) {
  13. 	return Math.log2(lsb ? lsb : Number(this._bitboard & -this._bitboard))
  14. }
  1. function IndexToUBigInt64(index, bits, mask) {
  2. 	const bitboard_mask = new BitboardClass(mask)
  4. 	let result = 0n
  6. 	for (let i = 0; i < bits; i++) {
  7. 		const square = bitboard_mask.PopLSB()
  9. 		if (index & (1 << i)) result |= 1n << BigInt(square)
  10. 	}
  12. 	return result
  13. }
  15. function FindMagicNumber(square_index, bits, diagonal) {
  16. 	const occupancies = new Array(4096)
  17. 	const attacks = new Array(4096)
  18. 	const used_attacks = new Array(4096).fill(0n)
  20. 	const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
  21. 	const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
  22. 	const occupancy_indicies = 1 << bits
  24. 	//* 生成中最慢的部分
  25. 	for (let index = 0; index < occupancy_indicies; index++) {
  26. 		//* 导致生成需要一段时间的部分
  27. 		occupancies[index] = IndexToUBigInt64(index, occupancy_indicies, attack_mask)
  29. 		attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
  30. 	}
  32. 	for (let _ = 0, fail = 0; _ < 100000000; _++) {
  33. 		const magic_number = GenerateMagicNumber()
  35. 		if (BigInt(new BitboardClass((attack_mask * magic_number) & 0xff00000000000000n).CountBits()) < 6) continue
  37. 		for (let index = 0, fail; !fail && index < occupancy_indicies; index++) {
  38. 			const magic_index = (occupancies[index] * magic_number) >> (64n - BigInt(bits))
  40. 			if (used_attacks[magic_index] === 0n) {
  41. 				used_attacks[magic_index] = attacks[index]
  42. 			} else if (used_attacks[magic_index] !== attacks[index]) {
  43. 				fail = 1
  44. 			}
  45. 		}
  47. 		if (!fail) return magic_number
  48. 	}
  50. 	console.log("***魔术数字失败***")
  51. 	return 0n
  52. }

我已尝试使用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 -->

  1. //* bitboard class
  2. PopLSB() {
  3. if (this._bitboard === 0n) return -1n
  4. const lsb = this._bitboard &amp; -this._bitboard
  5. const lsb_index = this.GetLSBIndex(lsb)
  6. this.XOr(lsb)
  7. return lsb
  8. }
  9. GetLSBIndex(lsb) {
  10. return Math.log2(lsb ? lsb : Number(this._bitboard &amp; -this._bitboard))
  11. }

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

  1. function IndexToUBigInt64(index, bits, mask) {
  2. const bitboard_mask = new BitboardClass(mask)
  3. let result = 0n
  4. for (let i = 0; i &lt; bits; i++) {
  5. const square = bitboard_mask.PopLSB()
  6. if (index &amp; (1 &lt;&lt; i)) result |= 1n &lt;&lt; BigInt(square)
  7. }
  8. return result
  9. }
  10. function FindMagicNumber(square_index, bits, diagonal) {
  11. const occupancies = new Array(4096)
  12. const attacks = new Array(4096)
  13. const used_attacks = new Array(4096).fill(0n)
  14. const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
  15. const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
  16. const occupancy_indicies = 1 &lt;&lt; bits
  17. //* The slowest part of the generation
  18. for (let index = 0; index &lt; occupancy_indicies; index++) {
  19. //* Responsible for the generation to take a while
  20. occupancies[index] = IndexToUBigInt64(index, occupancy_indicies, attack_mask)
  21. attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
  22. }
  23. for (let _ = 0, fail = 0; _ &lt; 100000000; _++) {
  24. const magic_number = GenerateMagicNumber()
  25. if (BigInt(new BitboardClass((attack_mask * magic_number) &amp; 0xff00000000000000n).CountBits()) &lt; 6) continue
  26. for (let index = 0, fail; !fail &amp;&amp; index &lt; occupancy_indicies; index++) {
  27. const magic_index = (occupancies[index] * magic_number) &gt;&gt; (64n - BigInt(bits))
  28. if (used_attacks[magic_index] === 0n) {
  29. used_attacks[magic_index] = attacks[index]
  30. } else if (used_attacks[magic_index] !== attacks[index]) {
  31. fail = 1
  32. }
  33. }
  34. if (!fail) return magic_number
  35. }
  36. console.log(&quot;***Magic number failed***&quot;)
  37. return 0n
  38. }

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 代。

  1. function GenerateAttacksAndOccupancies(square_index, bits, diagonal) {
  2. 	const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
  3. 	const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
  4. 	const number_of_bits = 1 << bits
  6. 	const attacks = new Array(number_of_bits)
  7. 	const occupancies = new Array(number_of_bits)
  9. 	for (let index = 0; index < number_of_bits; index++) {
  10. 		attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
  11. 		occupancies[index] = IndexToUBigInt64(index, number_of_bits, attack_mask)
  12. 	}
  14. 	return { attacks, occupancies }
  15. }
  17. function InitSliderAttacksAndOccupancies() {
  18. 	for (let square_index = 0; square_index < 64; square_index++) {
  19. 		const _level = GenerateAttacksAndOccupancies(square_index, LEVEL_BITS[square_index], false)
  20. 		LEVEL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _level.attacks
  21. 		LEVEL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _level.occupancies
  23. 		const _diagonal = GenerateAttacksAndOccupancies(square_index, DIAGONAL_BITS[square_index], true)
  24. 		DIAGONAL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _diagonal.attacks
  25. 		DIAGONAL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _diagonal.occupancies
  26. 	}
  27. }
英文:

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.

  1. function GenerateAttacksAndOccupancies(square_index, bits, diagonal) {
  2. 	const attack_mask = diagonal ? diagonal_masks[square_index] : level_masks[square_index]
  3. 	const target_squares = diagonal ? diagonal_squares[square_index] : level_squares[square_index]
  4. 	const number_of_bits = 1 &lt;&lt; bits
  6. 	const attacks = new Array(number_of_bits)
  7. 	const occupancies = new Array(number_of_bits)
  9. 	for (let index = 0; index &lt; number_of_bits; index++) {
  10. 		attacks[index] = MaskSlidingAttaks(occupancies[index], target_squares)
  11. 		occupancies[index] = IndexToUBigInt64(index, number_of_bits, attack_mask)
  12. 	}
  14. 	return { attacks, occupancies }
  15. }
  17. function InitSliderAttacksAndOccupancies() {
  18. 	for (let square_index = 0; square_index &lt; 64; square_index++) {
  19. 		const _level = GenerateAttacksAndOccupancies(square_index, LEVEL_BITS[square_index], false)
  20. 		LEVEL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _level.attacks
  21. 		LEVEL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _level.occupancies
  23. 		const _diagonal = GenerateAttacksAndOccupancies(square_index, DIAGONAL_BITS[square_index], true)
  24. 		DIAGONAL_ATTACKS_AND_OCCUPANCIES.attacks[square_index] = _diagonal.attacks
  25. 		DIAGONAL_ATTACKS_AND_OCCUPANCIES.occupancies[square_index] = _diagonal.occupancies
  26. 	}
  27. }

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

发表评论

匿名网友

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

确定