国际象棋逻辑的BitBoard类在TypeScript中的应用

Question

为了学习目的，我正在用JavaScript编写一个象棋逻辑库，我想知道这两种略有不同的BitBoard实现有多好。

第一种存储板为64长的零和1字符串，第二种使用包含8个数字的数组，每个数字代表一个字节。每个主体主要是允许两个BitBoards或一个BitBoard之间的二进制操作的方法，以及一个代表针对1执行该操作的索引的数字。

这是在JavaScript中表示无符号64位数的最佳方法吗？

任何反馈都将是非常感谢的，因为我对编程相当陌生。

字符串BitBoard

/**
 * 
 * @class BitBoard
 * @param bitRows: [optional] Array<number>
 * Each number must be an INTEGER in the range of 0-255; i.e. each number is a byte
 * DEFAULT: bitRows = [0,0,0,0,0,0,0,0].length = 8; i.e. 8 bytes)
 * Each value: n is converted to an integer and then set to 0 if n > 255
 */

class BitBoard {

  public board: string;
  public length: number;

  /**
   * @param bitRows: Array<number>
   */
  constructor(bitRows: number[] = [0, 0, 0, 0, 0, 0, 0, 0]) {
    if (!Array.isArray(bitRows) || bitRows.some(x => typeof x !== 'number')) {
      throw new TypeError('Invalid Input. Must be "Array" of "numbers"')
    }

    for (let i: number = 0, length: number = bitRows.length; i < length; i++) {
      if (Math.floor(bitRows[i]) !== bitRows[i] || bitRows[i] < 0 || bitRows[i] > 255) {
        throw new RangeError('inputs to bitRows array must be integers greater than or equal to zero and less than 256')
      }
    }
    
    this.board = bitRows.map(byte => padString(byte.toString(2), 8, '0', true)).join('');
    this.length = this.board.length;
  }

  /**
   * @param bit: Object
   * @returns boolean
   */
  determineIfBitBoard(bit: BitBoard): boolean {
    const names = Object.getOwnPropertyNames(bit);
    if (typeof bit === 'object' && names.indexOf('board') !== -1 && names.indexOf('length') !== -1) {
      const isLengthByteMultiple: boolean = bit.length % 8 === 0;
      const isBoardString: boolean = typeof bit.board === 'string';
      const isBoardLengthCorrect: boolean = bit.board.length === bit.length;
      const doPrototypesMatch: boolean = Object.getPrototypeOf(bit) === BitBoard.prototype;

      return isLengthByteMultiple && isBoardString && isBoardLengthCorrect && doPrototypesMatch;
    }
    return false;
  }

  /**
   * 
   * @param index: number
   * @returns number
   */
  getIndex(index: number): number {
    if (Math.floor(index) === index && index > -1 && index < this.length) {
      return parseInt(this.board[this.length -  1 - index]);
    }
    throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length');
  }

  /**
   * @returns BitBoard
   */
  copy(): BitBoard {
    let newBoard = new BitBoard();
    newBoard.board = this.board;

    return newBoard;
  }

  /**
   * 
   * @param bitBoardOrIndex: BitBoard | number
   * @returns BitBoard
   */
  and(bitBoardOrIndex: BitBoard | number): BitBoard {
    let newBoard: BitBoard = this.copy();

    if (typeof bitBoardOrIndex === 'number') {
      if (bitBoardOrIndex >= 0 && bitBoardOrIndex < this.length) {      
        return newBoard;
      }
      throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length')

    } else if (this.determineIfBitBoard(bitBoardOrIndex)) {
      if (this.length === bitBoardOrIndex.length) {
        let str: string = '';
  
        for (let i: number = 0; i < this.length; i++) {
          str += String(parseInt(newBoard.board[i]) & parseInt(bitBoardOrIndex.board[i]));
        }
        newBoard.board = str;
        return newBoard;
      }
      throw new RangeError('BitBoard lengths do not match');
    }
    throw new TypeError('Invalid input. Must be of type "BitBoard" or "number"');
  }

  /**
   * 
   * @param bitBoardOrIndex: BitBoard | number
   * @returns BitBoard
   */
  or(bitBoardOrIndex: BitBoard | number): BitBoard {
    let newBoard: BitBoard = this.copy();

    if (typeof bitBoardOrIndex === 'number') {
      if (bitBoardOrIndex >= 0 && bitBoardOrIndex < this.length) {

        const start: string = newBoard.board.slice(0, this.length - bitBoardOrIndex - 1);
        const altered: string = String(parseInt(this.board[this.length - 1 - bitBoardOrIndex]) | 1);
        const end: string = newBoard.board.slice(this.length - bitBoardOrIndex);

        newBoard.board = start + altered + end;

        return newBoard;
      }
      throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length');

    } else if (this.determineIfBitBoard(bitBoardOrIndex)) {
      if (this.length === bitBoardOrIndex.length) {
        let str: string = '';

        for (let i: number = 0; i < this.length; i++) {
          str += String(parseInt(newBoard.board[i]) | parseInt(bitBoardOrIndex.board[i]));
        }
        newBoard.board = str;

        return newBoard;
      }
      throw new RangeError('BitBoard lengths do not match');
    }
    throw new TypeError('Invalid input. Must be of type "BitBoard" or "number"');
  }

  /**
   * 
   * @param bitBoardOrIndex: BitBoard | number
   * @returns BitBoard
   */
  xOr(bitBoardOrIndex: BitBoard | number): BitBoard {
    let newBoard: BitBoard = this.copy();

    if (typeof bitBoardOrIndex === 'number') {
      if (bitBoardOrIndex >= 0 && bitBoardOrIndex < this.length) {

        const start: string = newBoard.board.slice(0, this.length - bitBoardOrIndex - 1);
        const altered: string = String(parseInt(this.board[this.length - 1 - bitBoardOrIndex]) ^ 1);
        const end: string = newBoard.board.slice(this.length - bitBoardOrIndex);

        newBoard.board = start + altered + end;

        return newBoard;
      }
      throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length');

    } else if (this.determineIfBitBoard(bitBoardOrIndex)) {
      if (this.length === bitBoardOrIndex.length) {
        let str: string = '';

        for (let i: number = 0; i < this.length; i++) {
          str += String(parseInt(newBoard.board[i]) ^ parseInt(bitBoardOrIndex.board[i]));
        }
        newBoard.board = str;

        return newBoard;
      }
      throw new RangeError('BitBoard lengths do not match');
    }
    throw new TypeError('Invalid input. Must be of type "BitBoard" or "number"')
  }

  /**
   * @returns BitBoard
   */
  not(): BitBoard {
    let newBoard: BitBoard = this.copy();
    let str: string = '';

    for (let i: number = 0; i < this.length; i++) {
      str += newBoard.board[i] === '1' ? '0' : '1';
    }
    newBoard.board = str;

    return newBoard;
  }

  /**
   * 
   * @param shiftAmount: number
   * @returns BitBoard
   */
  shiftLeft(shiftAmount: number): BitBoard {
    if (typeof shiftAmount === 'number') {
      if (shiftAmount >= 0 && shiftAmount <= this.length) {
        let newBoard: BitBoard = this.copy();
  
        newBoard.board = padString(newBoard.board, this.length + shiftAmount, '0', false).slice(shiftAmount);
  
        return newBoard;
      }
      throw new RangeError('Invalid input. Must be greater than or equal to zero and less than or equal to BitBoard.length');
    }
    throw new TypeError('Invalid input. Must be "number"');
  }

  /**
   * 
   * @param shiftAmount: number
   * @returns BitBoard
   */
  shiftRight(shiftAmount: number): BitBoard {
    if (typeof shiftAmount === 'number') {
      if (shiftAmount >= 0 && shiftAmount <= this.length) {
        let newBoard: BitBoard = this.copy();
  
        newBoard.board = padString(newBoard.board, this.length + shiftAmount, '0', true).slice(0, this.length);
  
        return newBoard;
      }
      throw new RangeError('Invalid input. Must be greater than or equal to zero and less than or equal to BitBoard.length');
    }
    throw new TypeError('Invalid input. Must be "number"');
  }
}

/**
 * @param str: string
 * @param length: number
 * @param padValue: string
 * @param start: boolean
 * @returns string
 */
function padString(str: string, length: number, padValue: string, start: boolean): string {
  if (start) {
    for (let i: number = str.length; i < length; i++) {
      str = padValue + str;
    }
  } else {
    for (let i: number = str.length; i < length; i++) {
      str += padValue;
    }
  }

  return str;
}

export = BitBoard;

数列BitBoard

/**
 * 
 * @class BitBoard
 * @param bitRows: [optional] Array<number>
 * Each number must be an INTEGER in the range of 0-255; i.e. each number is a byte
 * DEFAULT: bitRows = [0,0,0,0,0,0,0,0].length = 8; i.e. 8 bytes)
 * Each value: n is converted to an integer and then set to 0 if n > 255
 */

class BitBoard {

  public board: Array<number>;
  public length: number;
  private bitsPerByte: number;

  /**
   * @param bitRows: Array<number>
   */
  constructor(bitRows: number[] = [0, 0, 0, 0, 0, 0, 0, 0]) {
    if (!Array.isArray(bitRows) || bitRows.some(x => typeof x !== 'number')) {
      throw new TypeError('Invalid Input. Must be "Array" of "numbers"')
    }

    for (let i: number = 0, length: number = bitRows.length; i < length; i++) {
      if (Math.floor(bitRows[i]) !== bitRows[i] || bitRows[i] < 0 || bitRows[i] > 255) {
        throw new RangeError('inputs to bitRows array must be integers greater than or equal to zero and less than 256')
      }
    }
    
    this.board = bitRows;
    this.length = this.board.length * 8;
    this.bitsPerByte = 8;
  }

  /**
   * @param bit: Object
   * @returns boolean
   */
  determineIfBitBoard(bit: BitBoard): boolean {
    const names = Object.getOwnPropertyNames(bit);
    if (typeof bit === 'object' && names.indexOf('board') !== -1 && names.indexOf('length') !== -1 && names.indexOf('bitsPerByte') !== -1) {
      const isLengthByteMultiple: boolean = bit.length % 8 === 0;
      const isBoardArray: boolean = Array.isArray(bit.board);
      const isBoardValidNumber: boolean = bit.board.every(b => typeof b === 'number' && b >= 0 && b <= 255 && Math.floor(b) === b);
      const isBoardLengthCorrect: boolean = bit.board.length * 8 === bit.length;
      const doPrototypesMatch: boolean = Object.getPrototypeOf(bit) === BitBoard.prototype;

      return isLengthByteMultiple && isBoardArray && isBoardValidNumber && isBoardLengthCorrect && doPrototypesMatch;
    }
    return false;
  }
  
  /**
   * @returns string
   */
  boardToString() {
    let str = '';
    for (let i = 0; i < this.board.length; i++) {
      str += padString(this.board[i].toString(2), this.bitsPerByte, '0', true);
    }
    return str;
  }

  /**
   * 
   * @param index: number
   * @returns number
   */
  getIndex(index: number): number {
    if (Math.floor(index) === index && index > -1 && index < this.length) {
      const powOfTwo = 2 ** (index % this.bitsPerByte);
      const numberOfBuckets = this.length / this.bitsPerByte;
      return (this.board[numberOfBuckets - 1 - Math.floor(index / this.bitsPerByte)] & (powOfTwo)) / powOfTwo;
    }
    throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length');
  }

  /**
   * @returns BitBoard
   */
  copy = (): BitBoard => new BitBoard(this.board.slice());

  /**
   * 
   * @param bitBoardOrIndex: BitBoard | number
   * @returns BitBoard
   */
  and(bitBoardOrIndex: BitBoard | number): BitBoard {
    let newBoard: BitBoard = this.copy();

    if (typeof bitBoardOrIndex === 'number') {
      if (bitBoardOrIndex >= 0 && bitBoardOrIndex < this.length) {
        return newBoard;
      }
      throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length')

    } else if (this.determineIfBitBoard(bitBoardOrIndex)) {
      if (this.length === bitBoardOrIndex.length) {
        for (let i = 0; i < this.board.length; i++) {
          newBoard.board[i] &= bitBoardOrIndex.board[i];
        }
        return newBoard;
      }
      throw new RangeError('BitBoard lengths do not match');
    }
    throw new TypeError('Invalid input. Must be of type "BitBoard" or "number"');
  }

  /**
   * 
   * @param bitBoardOrIndex: BitBoard | number
   * @returns BitBoard
   */
  or(bitBoardOrIndex: BitBoard | number): BitBoard {
    let newBoard: BitBoard = this.copy();

    if (typeof bitBoardOrIndex === 'number') {
      if (bitBoardOrIndex >= 0 && bitBoardOrIndex < this.length) {
        const numberOfBuckets = this.length / this.bitsPerByte;
        newBoard.board[numberOfBuckets - 1 - Math.floor(bitBoardOrIndex / this.bitsPerByte)] |= 2 ** (bitBoardOrIndex % this.bitsPerByte);

        return newBoard;
      }
      throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length')

    } else if (this.determineIfBitBoard(bitBoardOrIndex)) {
      if (this.length === bitBoardOrIndex.length) {
        for (let i = 0; i < this.board.length; i++) {
          newBoard.board[i] |= bitBoardOrIndex.board[i];
        }
        return newBoard;
      }
      throw new RangeError('BitBoard lengths do not match');
    }
    throw new TypeError('Invalid input. Must be of type "BitBoard" or "number"');
  }

  /**
   * 
   * @param bitBoardOrIndex: BitBoard | number
   * @returns BitBoard
   */
  xOr(bitBoardOrIndex: BitBoard | number): BitBoard {
    let newBoard: BitBoard = this.copy();

    if (typeof bitBoardOrIndex === 'number') {
      if (bitBoardOrIndex >= 0 && bitBoardOrIndex < this.length) {
        const numberOfBuckets = this.length / this.bitsPerByte;
        newBoard.board[numberOfBuckets - 1 - Math.floor(bitBoardOrIndex / this.bitsPerByte)] ^= 2 ** (bitBoardOrIndex % this.bitsPerByte);

        return newBoard;
      }
      throw new RangeError('index must be integer greater than or equal to 0 and less than BitBoard.length')

    } else if (this.determineIfBitBoard(bitBoardOrIndex)) {
      if (this.length === bitBoardOrIndex.length) {
        for (let i = 0; i < this.board.length; i++) {
          newBoard.board[i] ^= bitBoardOrIndex.board[i];
        }
        return newBoard;
      }
      throw new RangeError('BitBoard lengths do not match');
    }
    throw new TypeError('Invalid input. Must be of type "BitBoard" or "number"');
  }

  /**
   * @returns BitBoard
   */
  not(): BitBoard {
    let strBoard: string = this.boardToString();
    let newStr: string;
    let notBoard: Array<number> = [];
    let i: number = 0

    while (i < this.length) {
      newStr = '';

      while(i % this.bitsPerByte !== 0) {
        newStr += strBoard[i] === '1' ? '0' : '1';
        i++;
      }
      notBoard.push(parseInt(newStr, 2))
    }
    const newBoard = this.copy();
    newBoard.board = notBoard;
    
    return newBoard;
  }

  /**
   * 
   * @param shiftAmount: number
   * @returns BitBoard
   */
  shiftLeft(shiftAmount: number): BitBoard {
    if (typeof shiftAmount === 'number') {
      if (shiftAmount >= 0 && shiftAmount <= this.length) {
        let str: string = this.boardToString();
        str += '0'.repeat(shiftAmount);
        str = str.slice(shiftAmount);

        let newBoard = this.copy();
        
        for (let i: number = 0, b = 0; i < this.board.length; i++ , b += this.bitsPerByte) {
          newBoard.board[i] = parseInt(str.slice(b, b + this.bitsPerByte), 2);
        }
        return newBoard;
      }
      throw new RangeError('Invalid input. Must be greater than or equal to zero and less than or equal to BitBoard.length');
    }
    throw new TypeError('Invalid input. Must be "number"');
  }

  /**
   * 
   * @param shiftAmount: number
   * @returns BitBoard
   */
  shiftRight(shiftAmount: number): BitBoard {
    if (typeof shiftAmount === 'number') {
      if (shiftAmount >= 0 && shiftAmount <= this.length) {
        let str = this.boardToString();
        str = '0'.repeat(shiftAmount) + str;
        str = str.slice(0, this.length);

        let newBoard = this.copy();

        for (let i = 0, b = 0; i < this.board.length; i++ , b += this.bitsPerByte) {
          newBoard.board[i] = parseInt(str.slice(b, b + this.bitsPerByte), 2);
        }
        return newBoard;
      }
      throw new RangeError('Invalid input. Must be greater than or equal to zero and less than or equal to BitBoard.length');
    }
    throw new TypeError('Invalid input. Must be "number"');
  }
}

/**
 * @function padString: function
 * @param str: string
 * @param length: number
 * @param padValue: string
 * @param start: boolean
 * @returns string
 */
function padString(str: string, length: number, padValue: string, start: boolean): string {
  if (start) {
    for (let i: number = str.length; i < length; i++) {
      str = padValue + str;
    }
  } else {
    for (let i: number = str.length; i < length; i++) {
      str += padValue;
    }
  }

  return str;
}

export = BitBoard;

Answer 1

简单地说，比特板的主要吸引力在于：

1. 使用位并行操作的性质来替换一些简单的循环。
2. 使用算术运算的力量来代替非平凡的算法(如o^(o-2r))。

如果使用二进制字符串对位板进行仿真，则这两种情况都不会实现。实际上，您要处理的是一个布尔数组，但是存储在一个字符串中。我觉得它没抓住重点。比特板并不仅仅是因为它们将数据编码为1和0，而是因为它们可以以对计算机友好的方式操作，而且该属性已经丢失。

基于数字的板阵列做得更好，它至少可以从编码中得到一些利用。同时，它可以对8个细胞进行一些操作。在某些地方(班次、not)，代码仍然非常“严格”，但这一点可以改进。这不是所有的比特板的力量，但它也不是没有，有点介于两者之间。

这是在JavaScript中表示无符号64位数的最佳方法吗？

不幸的是，这是一个困难的问题。但也有其他的选择。

BigInt存储64位整数没有问题。操纵许多小实例BigInt存在一些性能问题，我只是做了一些快速测试，看看它是否发生了变化，但它们并不令人鼓舞。而且，浏览器对它的支持并不是通用的。也许有一天这会是一个很好的方法。

现在，一个更好的选择是:使用一对数字，每个数字存储32位。这样，您就可以最大限度地利用JavaScript可以执行的32位按位操作。甚至仿真64位加/减(对于更先进的比特板技术)似乎是合理的。例如，Scala.js对其64位整数使用这种方法。