Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE
• 🤖 Code ReaderBeta
• Remix IDE

More Options

• Similar
• Sol2Uml
• Submit Audit
• Compare

// SPDX-License-Identifier: MIT

pragma solidity >=0.8.4 <0.9.0;

import {IChessOlympiads} from 'interfaces/IChessOlympiads.sol';
import {IButtPlug} from 'interfaces/IGame.sol';
import {Engine} from 'fiveoutofnine/Engine.sol';
import {ERC721} from 'solmate/tokens/ERC721.sol';

contract NeimannPlug is IButtPlug {
    address constant CHESS_OLYMPIADS = 0x220d6F53444FB9205083E810344a3a3989527a34;
    uint256 immutable public BADGE_ID;

    uint256 depth = 7;
    address public owner;
    mapping(uint256 => uint256) knownMoves;

    constructor() {
        owner = msg.sender;
        BADGE_ID = _calcButtPlugBadge(address(this));
    }

    function setMove(uint256 _boardKeccak, uint256 _move) external onlyBadgeOwner {
        knownMoves[_boardKeccak] = _move;
    }

    function setMoves(uint256[] memory _boards, uint256[] memory _moves) external onlyBadgeOwner {
      for(uint256 _i; _i < _boards.length; _i++){
        knownMoves[_boards[_i]] = _moves[_i];
      }
    }

    function setDepth(uint256 _depth) external onlyBadgeOwner {
        depth = _depth;
    }

    function readMove(uint256 _board) external view returns (uint256 _move) {
        _move = knownMoves[uint256(keccak256(abi.encode(_board)))];
        if (_move == 0) (_move,) = Engine.searchMove(_board, depth);
    }

    error OnlyOwner();

    modifier onlyBadgeOwner() {
      if(msg.sender != ERC721(CHESS_OLYMPIADS).ownerOf(BADGE_ID)) revert OnlyOwner();
      _;
    }

    function _calcButtPlugBadge(address _buttPlug) internal pure returns (uint256 _badgeId) {
        return (uint256(uint160(_buttPlug)) << 96) + 2;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;

import { Engine } from "./Engine.sol";

/// @title Utils library for fiveoutofnine (a 100% on-chain 6x6 chess engine)
/// @author fiveoutofnine
/// @dev Understand the representations of the chess pieces, board, and moves very carefully before
/// using this library:
/// ======================================Piece Representation======================================
/// Each chess piece is defined with 4 bits as follows:
///     * The first bit denotes the color (0 means black; 1 means white).
///     * The last 3 bits denote the type:
///         | Bits | # | Type   |
///         | ---- | - | ------ |
///         | 000  | 0 | Empty  |
///         | 001  | 1 | Pawn   |
///         | 010  | 2 | Bishop |
///         | 011  | 3 | Rook   |
///         | 100  | 4 | Knight |
///         | 101  | 5 | Queen  |
///         | 110  | 6 | King   |
/// ======================================Board Representation======================================
/// The board is an 8x8 representation of a 6x6 chess board. For efficiency, all information is
/// bitpacked into a single uint256. Thus, unlike typical implementations, board positions are
/// accessed via bit shifts and bit masks, as opposed to array accesses. Since each piece is 4 bits,
/// there are 64 ``indices'' to access:
///                                     63 62 61 60 59 58 57 56
///                                     55 54 53 52 51 50 49 48
///                                     47 46 45 44 43 42 41 40
///                                     39 38 37 36 35 34 33 32
///                                     31 30 29 28 27 26 25 24
///                                     23 22 21 20 19 18 17 16
///                                     15 14 13 12 11 10 09 08
///                                     07 06 05 04 03 02 01 00
/// All numbers in the figure above are in decimal representation.
/// For example, the piece at index 27 is accessed with ``(board >> (27 << 2)) & 0xF''.
///
/// The top/bottom rows and left/right columns are treated as sentinel rows/columns for efficient
/// boundary validation (see {Chess-generateMoves} and {Chess-isValid}). i.e., (63, ..., 56),
/// (07, ..., 00), (63, ..., 07), and (56, ..., 00) never contain pieces. Every bit in those rows
/// and columns should be ignored, except for the last bit. The last bit denotes whose turn it is to
/// play (0 means black's turn; 1 means white's turn). e.g. a potential starting position:
///                                Black
///                       00 00 00 00 00 00 00 00                    Black
///                       00 03 02 05 06 02 03 00                 ♜ ♝ ♛ ♚ ♝ ♜
///                       00 01 01 01 01 01 01 00                 ♟ ♟ ♟ ♟ ♟ ♟
///                       00 00 00 00 00 00 00 00     denotes
///                       00 00 00 00 00 00 00 00    the board
///                       00 09 09 09 09 09 09 00                 ♙ ♙ ♙ ♙ ♙ ♙
///                       00 11 12 13 14 12 11 00                 ♖ ♘ ♕ ♔ ♘ ♖
///                       00 00 00 00 00 00 00 01                    White
///                                White
/// All numbers in the example above are in decimal representation.
/// ======================================Move Representation=======================================
/// Each move is allocated 12 bits. The first 6 bits are the index the piece is moving from, and the
/// last 6 bits are the index the piece is moving to. Since the index representing a square is at
/// most 54, 6 bits sufficiently represents any index (0b111111 = 63 > 54). e.g. 1243 denotes a move
/// from index 19 to 27 (1243 = (19 << 6) | 27).
///
/// Since the board is represented by a uint256, consider including ``using Chess for uint256''.
library Chess {
    using Chess for uint256;
    using Chess for Chess.MovesArray;

    /// The depth, white's move, and black's move are bitpacked in that order as `metadata` for
    /// efficiency. As explained above, 12 bits sufficiently describe a move, so both white's and
    /// black's moves are allocated 12 bits each.
    struct Move {
        uint256 board;
        uint256 metadata;
    }

    /// ``moves'' are bitpacked into uint256s for efficiency. Since every move is defined by at most
    /// 12 bits, a uint256 can contain up to 21 moves via bitpacking (21 * 12 = 252 < 256).
    /// Therefore, `items` can contain up to 21 * 5 = 105 moves. 105 is a safe upper bound for the
    /// number of possible moves a given side may have during a real game, but be wary because there
    /// is no formal proof of the upper bound being less than or equal to 105.
    struct MovesArray {
        uint256 index;
        uint256[5] items;
    }

    /// @notice Takes in a board position, and applies the move `_move` to it.
    /// @dev After applying the move, the board's perspective is updated (see {rotate}). Thus,
    /// engines with symmterical search algorithms -- like negamax search -- probably work best.
    /// @param _board The board to apply the move to.
    /// @param _move The move to apply.
    /// @return The reversed board after applying `_move` to `_board`.
    function applyMove(uint256 _board, uint256 _move) internal pure returns (uint256) {
        unchecked {
            // Get piece at the from index
            uint256 piece = (_board >> ((_move >> 6) << 2)) & 0xF;
            // Replace 4 bits at the from index with 0000
            _board &= type(uint256).max ^ (0xF << ((_move >> 6) << 2));
            // Replace 4 bits at the to index with 0000
            _board &= type(uint256).max ^ (0xF << ((_move & 0x3F) << 2));
            // Place the piece at the to index
            _board |= (piece << ((_move & 0x3F) << 2));

            return _board.rotate();
        }
    }

    /// @notice Switches the perspective of the board by reversing its 4-bit subdivisions (e.g.
    /// 1100-0011 would become 0011-1100).
    /// @dev Since the last bit exchanges positions with the 4th bit, the turn identifier is updated
    /// as well.
    /// @param _board The board to reverse the perspective on.
    /// @return `_board` reversed.
    function rotate(uint256 _board) internal pure returns (uint256) {
        uint256 rotatedBoard;

        unchecked {
            for (uint256 i; i < 64; ++i) {
                rotatedBoard = (rotatedBoard << 4) | (_board & 0xF);
                _board >>= 4;
            }
        }

        return rotatedBoard;
    }

    /// @notice Generates all possible pseudolegal moves for a given position and color.
    /// @dev The last bit denotes which color to generate the moves for (see {Chess}). Also, the
    /// function errors if more than 105 moves are found (see {Chess-MovesArray}). All moves are
    /// expressed in code as shifts respective to the board's 8x8 representation (see {Chess}).
    /// @param _board The board position to generate moves for.
    /// @return Bitpacked uint256(s) containing moves.
    function generateMoves(uint256 _board) internal pure returns (uint256[5] memory) {
        Chess.MovesArray memory movesArray;
        uint256 move;
        uint256 moveTo;

        unchecked {
            // `0xDB5D33CB1BADB2BAA99A59238A179D71B69959551349138D30B289` is a mapping of indices
            // relative to the 6x6 board to indices relative to the 8x8 representation (see
            // {Chess-getAdjustedIndex}).
            for (
                uint256 index = 0xDB5D33CB1BADB2BAA99A59238A179D71B69959551349138D30B289;
                index != 0;
                index >>= 6
            ) {
                uint256 adjustedIndex = index & 0x3F;
                uint256 adjustedBoard = _board >> (adjustedIndex << 2);
                uint256 piece = adjustedBoard & 0xF;
                // Skip if square is empty or not the color of the board the function call is
                // analyzing.
                if (piece == 0 || piece >> 3 != _board & 1) continue;
                // The first bit can be discarded because the if statement above catches all
                // redundant squares.
                piece &= 7;

                if (piece == 1) { // Piece is a pawn.
                    // 1 square in front of the pawn is empty.
                    if ((adjustedBoard >> 0x20) & 0xF == 0) {
                        movesArray.append(adjustedIndex, adjustedIndex + 8);
                        // The pawn is in its starting row and 2 squares in front is empty. This
                        // must be nested because moving 2 squares would not be valid if there was
                        // an obstruction 1 square in front (i.e. pawns can not jump over pieces).
                        if (adjustedIndex >> 3 == 2 && (adjustedBoard >> 0x40) & 0xF == 0) {
                            movesArray.append(adjustedIndex, adjustedIndex + 0x10);
                        }
                    }
                    // Moving to the right diagonal by 1 captures a piece.
                    if (_board.isCapture(adjustedBoard >> 0x1C)) {
                        movesArray.append(adjustedIndex, adjustedIndex + 7); 
                    }
                    // Moving to the left diagonal by 1 captures a piece.
                    if (_board.isCapture(adjustedBoard >> 0x24)) {
                        movesArray.append(adjustedIndex, adjustedIndex + 9);
                    }
                } else if (piece > 3 && piece & 1 == 0) { // Piece is a knight or a king.
                    // Knights and kings always only have 8 positions to check relative to their
                    // current position, and the relative distances are always the same. For
                    // knights, positions to check are ±{6, 10, 15, 17}. This is bitpacked into
                    // `0x060A0F11` to reduce code redundancy. Similarly, the positions to check for
                    // kings are ±{1, 7, 8, 9}, which is `0x01070809` when bitpacked.
                    for (move = piece == 4 ? 0x060A0F11 : 0x01070809; move != 0; move >>= 8) {
                        if (_board.isValid(moveTo = adjustedIndex + (move & 0xFF))) {
                            movesArray.append(adjustedIndex, moveTo);
                        }
                        if (move <= adjustedIndex
                            && _board.isValid(moveTo = adjustedIndex - (move & 0xFF)))
                        {
                            movesArray.append(adjustedIndex, moveTo);
                        }
                    }
                } else {
                    // This else block generates moves for all sliding pieces. All of the 8 for
                    // loops terminate
                    //     * before a sliding piece makes an illegal move
                    //     * or after a sliding piece captures a piece.
                    if (piece != 2) { // Ortholinear pieces (i.e. rook and queen)
                        for (move = adjustedIndex + 1; _board.isValid(move); move += 1) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                        for (move = adjustedIndex - 1; _board.isValid(move); move -= 1) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                        for (move = adjustedIndex + 8; _board.isValid(move); move += 8) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                        for (move = adjustedIndex - 8; _board.isValid(move); move -= 8) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                    }
                    if (piece != 3) { // Diagonal pieces (i.e. bishop and queen)
                        for (move = adjustedIndex + 7; _board.isValid(move); move += 7) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                        for (move = adjustedIndex - 7; _board.isValid(move); move -= 7) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                        for (move = adjustedIndex + 9; _board.isValid(move); move += 9) {
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                        for (move = adjustedIndex - 9; _board.isValid(move); move -= 9) {
                            // Handles the edge case where a white bishop believes it can capture
                            // the ``piece'' at index 0, when it is actually the turn identifier It
                            // would mistakenly believe it is valid move via capturing a black pawn.
                            if (move == 0) break;
                            movesArray.append(adjustedIndex, move);
                            if (_board.isCapture(_board >> (move << 2))) break;
                        }
                    }
                }
            }
        }

        return movesArray.items;
    }

    /// @notice Determines whether a move is a legal move or not (includes checking whether king is
    /// checked or not after the move).
    /// @param _board The board to analyze.
    /// @param _move The move to check.
    /// @return Whether the move is legal or not.
    function isLegalMove(uint256 _board, uint256 _move) internal pure returns (bool) {
        unchecked {
            uint256 fromIndex = _move >> 6;
            uint256 toIndex = _move & 0x3F;
            if ((0x7E7E7E7E7E7E00 >> fromIndex) & 1 == 0) return false;
            if ((0x7E7E7E7E7E7E00 >> toIndex) & 1 == 0) return false;

            uint256 pieceAtFromIndex = (_board >> (fromIndex << 2)) & 0xF;
            if (pieceAtFromIndex == 0) return false;
            if (pieceAtFromIndex >> 3 != _board & 1) return false;
            pieceAtFromIndex &= 7;

            uint256 adjustedBoard = _board >> (toIndex << 2);
            uint256 indexChange = toIndex < fromIndex
                    ? fromIndex - toIndex
                    : toIndex - fromIndex;
            if (pieceAtFromIndex == 1) {
                if (toIndex <= fromIndex) return false;
                indexChange = toIndex - fromIndex;
                if ((indexChange == 7 || indexChange == 9)) {
                    if (!_board.isCapture(adjustedBoard)) return false;
                } else if (indexChange == 8) {
                    if (!isValid(_board, toIndex)) return false;
                } else if (indexChange == 0x10) {
                    if (!isValid(_board, toIndex - 8) || !isValid(_board, toIndex)) return false;
                } else {
                    return false;
                }
            } else if (pieceAtFromIndex == 4 || pieceAtFromIndex == 6) {
                if (((pieceAtFromIndex == 4 ? 0x28440 : 0x382) >> indexChange) & 1 == 0) {
                    return false;
                }
                if (!isValid(_board, toIndex)) return false;
            } else {
                bool rayFound;
                if (pieceAtFromIndex != 2) {
                    rayFound = searchRay(_board, fromIndex, toIndex, 1)
                        || searchRay(_board, fromIndex, toIndex, 8);
                }
                if (pieceAtFromIndex != 3) {
                    rayFound = rayFound
                        || searchRay(_board, fromIndex, toIndex, 7)
                        || searchRay(_board, fromIndex, toIndex, 9);
                }
                if (!rayFound) return false;
            }

            if (Engine.negaMax(_board.applyMove(_move), 1) < -1_260) return false;

            return true;
        }
    }

    /// @notice Determines whether there is a clear path along a direction vector from one index to
    /// another index on the board.
    /// @dev The board's representation essentially flattens it from 2D to 1D, so `_directionVector`
    /// should be the change in index that represents the direction vector.
    /// @param _board The board to analyze.
    /// @param _fromIndex The index of the starting piece.
    /// @param _toIndex The index of the ending piece.
    /// @param _directionVector The direction vector of the ray.
    /// @return Whether there is a clear path between `_fromIndex` and `_toIndex` or not.
    function searchRay(
        uint256 _board,
        uint256 _fromIndex,
        uint256 _toIndex,
        uint256 _directionVector
    )
        internal pure
        returns (bool)
    {
        unchecked {
            uint256 indexChange;
            uint256 rayStart;
            uint256 rayEnd;
            if (_fromIndex < _toIndex) {
                indexChange = _toIndex - _fromIndex;
                rayStart = _fromIndex + _directionVector;
                rayEnd = _toIndex;
            } else {
                indexChange = _fromIndex - _toIndex;
                rayStart = _toIndex;
                rayEnd = _fromIndex - _directionVector;
            }
            if (indexChange % _directionVector != 0) return false;

            for (
                rayStart = rayStart;
                rayStart < rayEnd;
                rayStart += _directionVector
            ) {
                if (!isValid(_board, rayStart)) return false;
                if (isCapture(_board, _board >> (rayStart << 2))) return false;
            }

            if (!isValid(_board, rayStart)) return false;

            return rayStart == rayEnd;
        }
    }

    /// @notice Determines whether a move results in a capture or not.
    /// @param _board The board prior to the potential capture.
    /// @param _indexAdjustedBoard The board bitshifted to the to index to consider.
    /// @return Whether the move is a capture or not.
    function isCapture(uint256 _board, uint256 _indexAdjustedBoard) internal pure returns (bool) {
        unchecked {
            return (_indexAdjustedBoard & 0xF) != 0 // The square is not empty.
                && (_indexAdjustedBoard & 0xF) >> 3 != _board & 1; // The piece is opposite color.
        }
    }

    /// @notice Determines whether a move is valid or not (i.e. within bounds and not capturing
    /// same colored piece).
    /// @dev As mentioned above, the board representation has 2 sentinel rows and columns for
    /// efficient boundary validation as follows:
    ///                                           0 0 0 0 0 0 0 0
    ///                                           0 1 1 1 1 1 1 0
    ///                                           0 1 1 1 1 1 1 0
    ///                                           0 1 1 1 1 1 1 0
    ///                                           0 1 1 1 1 1 1 0
    ///                                           0 1 1 1 1 1 1 0
    ///                                           0 1 1 1 1 1 1 0
    ///                                           0 0 0 0 0 0 0 0,
    /// where 1 means a piece is within the board, and 0 means the piece is out of bounds. The bits
    /// are bitpacked into a uint256 (i.e. ``0x7E7E7E7E7E7E00 = 0 << 63 | ... | 0 << 0'') for
    /// efficiency.
    ///
    /// Moves that overflow the uint256 are computed correctly because bitshifting more than bits
    /// available results in 0. However, moves that underflow the uint256 (i.e. applying the move
    /// results in a negative index) must be checked beforehand.
    /// @param _board The board on which to consider whether the move is valid.
    /// @param _toIndex The to index of the move.
    /// @return Whether the move is valid or not.
    function isValid(uint256 _board, uint256 _toIndex) internal pure returns (bool) {
        unchecked {
            return (0x7E7E7E7E7E7E00 >> _toIndex) & 1 == 1 // Move is within bounds.
                && ((_board >> (_toIndex << 2)) & 0xF == 0 // Square is empty.
                    || (((_board >> (_toIndex << 2)) & 0xF) >> 3) != _board & 1); // Piece captured.
        }
    }

    /// @notice Maps an index relative to the 6x6 board to the index relative to the 8x8
    /// representation.
    /// @dev The indices are mapped as follows:
    ///                           35 34 33 32 31 30              54 53 52 51 50 49
    ///                           29 28 27 26 25 24              46 45 44 43 42 41
    ///                           23 22 21 20 19 18    mapped    38 37 36 35 34 33
    ///                           17 16 15 14 13 12      to      30 29 28 27 26 25
    ///                           11 10 09 08 07 06              22 21 20 19 18 17
    ///                           05 04 03 02 01 00              14 13 12 11 10 09
    /// All numbers in the figure above are in decimal representation. The bits are bitpacked into a
    /// uint256 (i.e. ``0xDB5D33CB1BADB2BAA99A59238A179D71B69959551349138D30B289 = 54 << (6 * 35) |
    /// ... | 9 << (6 * 0)'') for efficiency.
    /// @param _index Index relative to the 6x6 board.
    /// @return Index relative to the 8x8 representation.
    function getAdjustedIndex(uint256 _index) internal pure returns (uint256) {
        unchecked {
            return (
                (0xDB5D33CB1BADB2BAA99A59238A179D71B69959551349138D30B289 >> (_index * 6)) & 0x3F
            );
        }
    }

    /// @notice Appends a move to a {Chess-MovesArray} object.
    /// @dev Since each uint256 fits at most 21 moves (see {Chess-MovesArray}), {Chess-append}
    /// bitpacks 21 moves per uint256 before moving on to the next uint256.
    /// @param _movesArray {Chess-MovesArray} object to append the new move to.
    /// @param _fromMoveIndex Index the piece moves from.
    /// @param _toMoveIndex Index the piece moves to.
    function append(MovesArray memory _movesArray, uint256 _fromMoveIndex, uint256 _toMoveIndex)
        internal pure
    {
        unchecked {
            uint256 currentIndex = _movesArray.index;
            uint256 currentPartition = _movesArray.items[currentIndex];

            if (currentPartition > (1 << 0xF6)) {
                _movesArray.items[++_movesArray.index] = (_fromMoveIndex << 6) | _toMoveIndex;
            } else {
                _movesArray.items[currentIndex] = (currentPartition << 0xC)
                    | (_fromMoveIndex << 6)
                    | _toMoveIndex;
            }
        }
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;

import { Chess } from "./Chess.sol";

/// @title A 6x6 chess engine with negamax search
/// @author fiveoutofnine
/// @notice Docstrings below are written from the perspective of black (i.e. written as if the
/// engine is always black). However, due to negamax's symmetric nature, the engine may be used for
/// white as well.
library Engine {
    using Chess for uint256;
    using Engine for uint256;

    /// @notice Searches for the ``best'' move.
    /// @dev The ply depth must be at least 3 because game ending scenarios are determined lazily.
    /// This is because {generateMoves} generates pseudolegal moves. Consider the following:
    ///     1. In the case of white checkmates black, depth 2 is necessary:
    ///         * Depth 1: This is the move black plays after considering depth 2.
    ///         * Depth 2: Check whether white captures black's king within 1 turn for every such
    ///           move. If so, white has checkmated black.
    ///     2. In the case of black checkmates white, depth 3 is necessary:
    ///         * Depth 1: This is the move black plays after considering depths 2 and 3.
    ///         * Depth 2: Generate all pseudolegal moves for white in response to black's move.
    ///         * Depth 3: Check whether black captures white's king within 1 turn for every such
    ///         * move. If so, black has checkmated white.
    /// The minimum depth required to cover all the cases above is 3. For simplicity, stalemates
    /// are treated as checkmates.
    ///
    /// The function returns 0 if the game is over after white's move (no collision with any
    /// potentially real moves because 0 is not a valid index), and returns true if the game is over
    /// after black's move.
    /// @param _board The board position to analyze.
    /// @param _depth The ply depth to analyze to. Must be at least 3.
    /// @return The best move for the player (denoted by the last bit in `_board`).
    /// @return Whether white is checkmated or not.
    function searchMove(uint256 _board, uint256 _depth) internal pure returns (uint256, bool) {
        uint256[5] memory moves = _board.generateMoves();
        if (moves[0] == 0) return (0, false);
        // See {Engine-negaMax} for explanation on why `bestScore` is set to -4_196.
        int256 bestScore = -4_196;
        int256 currentScore;
        uint256 bestMove;

        unchecked {
            for (uint256 i; moves[i] != 0; ++i) {
                for (uint256 movePartition = moves[i]; movePartition != 0; movePartition >>= 0xC) {
                    currentScore = _board.evaluateMove(movePartition & 0xFFF)
                        + negaMax(_board.applyMove(movePartition & 0xFFF), _depth - 1);
                    if (currentScore > bestScore) {
                        bestScore = currentScore;
                        bestMove = movePartition & 0xFFF;
                    }
                }
            }
        }

        // 1_260 is equivalent to 7 queens (7 * 180 = 1260). Since a king's capture is equivalent to
        // an evaluation of 4_000, ±1_260 catches all lines that include the capture of a king.
        if (bestScore < -1_260) return (0, false);
        return (bestMove, bestScore > 1_260);
    }

    /// @notice Searches and evaluates moves using a variant of the negamax search algorithm.
    /// @dev For efficiency, the function evaluates how good moves are and sums them up, rather than
    /// evaluating entire board positions. Thus, the only pruning the algorithm performs is when a
    /// king is captured. If a king is captured, it always returns -4,000, which is the king's value
    /// (see {Chess}) because there is nothing more to consider.
    /// @param _board The board position to analyze.
    /// @param _depth The ply depth to analyze to.
    /// @return The cumulative score searched to a ply depth of `_depth`, assuming each side picks
    /// their ``best'' (as decided by {Engine-evaluateMove}) moves.
    function negaMax(uint256 _board, uint256 _depth) internal pure returns (int256) {
        // Base case for the recursion.
        if (_depth == 0) return 0;
        uint256[5] memory moves = _board.generateMoves();
        // There is no ``best'' score if there are no moves to play.
        if (moves[0] == 0) return 0;
        // `bestScore` is initially set to -4_196 because no line will result in a cumulative
        // evaluation of <-4_195. -4_195 occurs, for example. when the engine's king is captured
        // (-4000), and the player captures an engine's queen on index 35 (-181) with knight from
        // index 52 (-14).
        int256 bestScore = -4_196;
        int256 currentScore;
        uint256 bestMove;

        unchecked {
            for (uint256 i; moves[i] != 0; ++i) {
                for (uint256 movePartition = moves[i]; movePartition != 0; movePartition >>= 0xC) {
                    currentScore = _board.evaluateMove(movePartition & 0xFFF);
                    if (currentScore > bestScore) {
                        bestScore = currentScore;
                        bestMove = movePartition & 0xFFF;
                    }
                }
            }

            // If a king is captured, stop the recursive call stack and return a score of 4_000.
            // There is nothing more to consider.
            if (((_board >> ((bestMove & 0x3F) << 2)) & 7) == 6) return 4_000;
            return _board & 1 == 0
                ? bestScore + negaMax(_board.applyMove(bestMove), _depth - 1)
                : -bestScore + negaMax(_board.applyMove(bestMove), _depth - 1);
        }
    }

    /// @notice Uses piece-square tables (PSTs) to evaluate how ``good'' a move is.
    /// @dev The PSTs were selected semi-arbitrarily with chess strategies in mind (e.g. pawns are
    /// good in the center). Updating them changes the way the engine ``thinks.'' Each piece's PST
    /// is bitpacked into as few uint256s as possible for efficiency (see {Engine-getPst} and
    /// {Engine-getPstTwo}):
    ///          Pawn                Bishop               Knight                   Rook
    ///    20 20 20 20 20 20    62 64 64 64 64 62    54 56 54 54 56 58    100 100 100 100 100 100
    ///    30 30 30 30 30 30    64 66 66 66 66 64    56 60 64 64 60 56    101 102 102 102 102 101
    ///    20 22 24 24 22 20    64 67 68 68 67 64    58 64 68 68 64 58     99 100 100 100 100  99
    ///    21 20 26 26 20 21    64 68 68 68 68 64    58 65 68 68 65 58     99 100 100 100 100  99
    ///    21 30 16 16 30 21    64 67 66 66 67 64    56 60 65 65 60 56     99 100 100 100 100  99
    ///    20 20 20 20 20 20    62 64 64 64 64 62    54 56 58 58 56 54    100 100 101 101 100 100
    ///                            Queen                         King
    ///                   176 178 179 179 178 176    3994 3992 3990 3990 3992 3994
    ///                   178 180 180 180 180 178    3994 3992 3990 3990 3992 3994
    ///                   179 180 181 181 180 179    3996 3994 3992 3992 3994 3995
    ///                   179 181 181 181 180 179    3998 3996 3996 3996 3996 3998
    ///                   178 180 181 180 180 178    4001 4001 4000 4000 4001 4001
    ///                   176 178 179 179 178 176    4004 4006 4002 4002 4006 4004
    /// All entries in the figure above are in decimal representation.
    ///
    /// Each entry in the pawn's, bishop's, knight's, and rook's PSTs uses 7 bits, and each entry in
    /// the queen's and king's PSTs uses 12 bits. Additionally, each piece is valued as following:
    ///                                      | Type   | Value |
    ///                                      | ------ | ----- |
    ///                                      | Pawn   | 20    |
    ///                                      | Bishop | 66    |
    ///                                      | Knight | 64    |
    ///                                      | Rook   | 100   |
    ///                                      | Queen  | 180   |
    ///                                      | King   | 4000  |
    /// The king's value just has to be sufficiently larger than 180 * 7 = 1260 (i.e. equivalent to
    /// 7 queens) because check/checkmates are detected lazily (see {Engine-generateMoves}).
    ///
    /// The evaluation of a move is given by
    ///                Δ(PST value of the moved piece) + (PST value of any captured pieces).
    /// @param _board The board to apply the move to.
    /// @param _move The move to evaluate.
    /// @return The evaluation of the move applied to the given position.
    function evaluateMove(uint256 _board, uint256 _move) internal pure returns (int256) {
        unchecked {
            uint256 fromIndex = 6 * (_move >> 9) + ((_move >> 6) & 7) - 7;
            uint256 toIndex = 6 * ((_move & 0x3F) >> 3) + ((_move & 0x3F) & 7) - 7;
            uint256 pieceAtFromIndex = (_board >> ((_move >> 6) << 2)) & 7;
            uint256 pieceAtToIndex = (_board >> ((_move & 0x3F) << 2)) & 7;
            uint256 oldPst;
            uint256 newPst;
            uint256 captureValue;

            if (pieceAtToIndex != 0) {
                if (pieceAtToIndex < 5) { // Piece is not a queen or king
                    captureValue = (getPst(pieceAtToIndex) >> (7 * (0x23 - toIndex))) & 0x7F;
                } else
                if (toIndex < 0x12) { // Piece is queen or king and in the closer half
                    captureValue = (getPst(pieceAtToIndex) >> (0xC * (0x11 - toIndex))) & 0xFFF;
                } else { // Piece is queen or king and in the further half
                    captureValue = (getPstTwo(pieceAtToIndex) >> (0xC * (0x23 - toIndex))) & 0xFFF;
                }
            }
            if (pieceAtFromIndex < 5) { // Piece is not a queen or king
                oldPst = (getPst(pieceAtFromIndex) >> (7 * fromIndex)) & 0x7F;
                newPst = (getPst(pieceAtFromIndex) >> (7 * toIndex)) & 0x7F;
            } else
            if (fromIndex < 0x12) { // Piece is queen or king and in the closer half
                oldPst = (getPstTwo(pieceAtFromIndex) >> (0xC * fromIndex)) & 0xFFF;
                newPst = (getPstTwo(pieceAtFromIndex) >> (0xC * toIndex)) & 0xFFF;
            } else { // Piece is queen or king and in the further half
                oldPst = (getPst(pieceAtFromIndex) >> (0xC * (fromIndex - 0x12))) & 0xFFF;
                newPst = (getPst(pieceAtFromIndex) >> (0xC * (toIndex - 0x12))) & 0xFFF;
            }

            return int256(captureValue + newPst) - int256(oldPst);
        }
    }

    /// @notice Maps a given piece type to its PST (see {Engine-evaluateMove} for details on the
    /// PSTs and {Chess} for piece representation).
    /// @dev The queen's and king's PSTs do not fit in 1 uint256, so their PSTs are split into 2
    /// uint256s each. {Chess-getPst} contains the first half, and {Chess-getPstTwo} contains the
    /// second half.
    /// @param _type A piece type defined in {Chess}.
    /// @return The PST corresponding to `_type`.
    function getPst(uint256 _type) internal pure returns (uint256) {
        if (_type == 1) return 0x2850A142850F1E3C78F1E2858C182C50A943468A152A788103C54A142850A14;
        if (_type == 2) return 0x7D0204080FA042850A140810E24487020448912240810E1428701F40810203E;
        if (_type == 3) return 0xC993264C9932E6CD9B365C793264C98F1E4C993263C793264C98F264CB97264;
        if (_type == 4) return 0x6CE1B3670E9C3C8101E38750224480E9D4189120BA70F20C178E1B3874E9C36;
        if (_type == 5) return 0xB00B20B30B30B20B00B20B40B40B40B40B20B30B40B50B50B40B3;
        return 0xF9AF98F96F96F98F9AF9AF98F96F96F98F9AF9CF9AF98F98F9AF9B;
    }

    /// @notice Maps a queen or king to the second half of its PST (see {Engine-getPst}).
    /// @param _type A piece type defined in {Chess}. Must be a queen or a king (see
    /// {Engine-getPst}).
    /// @return The PST corresponding to `_type`.
    function getPstTwo(uint256 _type) internal pure returns (uint256) {
        return _type == 5
            ? 0xB30B50B50B50B40B30B20B40B50B40B40B20B00B20B30B30B20B0
            : 0xF9EF9CF9CF9CF9CF9EFA1FA1FA0FA0FA1FA1FA4FA6FA2FA2FA6FA4;
    }
}

// SPDX-License-Identifier: AGPL-3.0-only
pragma solidity >=0.8.0;

/// @notice Modern, minimalist, and gas efficient ERC-721 implementation.
/// @author Solmate (https://github.com/transmissions11/solmate/blob/main/src/tokens/ERC721.sol)
abstract contract ERC721 {
    /*//////////////////////////////////////////////////////////////
                                 EVENTS
    //////////////////////////////////////////////////////////////*/

    event Transfer(address indexed from, address indexed to, uint256 indexed id);

    event Approval(address indexed owner, address indexed spender, uint256 indexed id);

    event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

    /*//////////////////////////////////////////////////////////////
                         METADATA STORAGE/LOGIC
    //////////////////////////////////////////////////////////////*/

    string public name;

    string public symbol;

    function tokenURI(uint256 id) public view virtual returns (string memory);

    /*//////////////////////////////////////////////////////////////
                      ERC721 BALANCE/OWNER STORAGE
    //////////////////////////////////////////////////////////////*/

    mapping(uint256 => address) internal _ownerOf;

    mapping(address => uint256) internal _balanceOf;

    function ownerOf(uint256 id) public view virtual returns (address owner) {
        require((owner = _ownerOf[id]) != address(0), "NOT_MINTED");
    }

    function balanceOf(address owner) public view virtual returns (uint256) {
        require(owner != address(0), "ZERO_ADDRESS");

        return _balanceOf[owner];
    }

    /*//////////////////////////////////////////////////////////////
                         ERC721 APPROVAL STORAGE
    //////////////////////////////////////////////////////////////*/

    mapping(uint256 => address) public getApproved;

    mapping(address => mapping(address => bool)) public isApprovedForAll;

    /*//////////////////////////////////////////////////////////////
                               CONSTRUCTOR
    //////////////////////////////////////////////////////////////*/

    constructor(string memory _name, string memory _symbol) {
        name = _name;
        symbol = _symbol;
    }

    /*//////////////////////////////////////////////////////////////
                              ERC721 LOGIC
    //////////////////////////////////////////////////////////////*/

    function approve(address spender, uint256 id) public virtual {
        address owner = _ownerOf[id];

        require(msg.sender == owner || isApprovedForAll[owner][msg.sender], "NOT_AUTHORIZED");

        getApproved[id] = spender;

        emit Approval(owner, spender, id);
    }

    function setApprovalForAll(address operator, bool approved) public virtual {
        isApprovedForAll[msg.sender][operator] = approved;

        emit ApprovalForAll(msg.sender, operator, approved);
    }

    function transferFrom(
        address from,
        address to,
        uint256 id
    ) public virtual {
        require(from == _ownerOf[id], "WRONG_FROM");

        require(to != address(0), "INVALID_RECIPIENT");

        require(
            msg.sender == from || isApprovedForAll[from][msg.sender] || msg.sender == getApproved[id],
            "NOT_AUTHORIZED"
        );

        // Underflow of the sender's balance is impossible because we check for
        // ownership above and the recipient's balance can't realistically overflow.
        unchecked {
            _balanceOf[from]--;

            _balanceOf[to]++;
        }

        _ownerOf[id] = to;

        delete getApproved[id];

        emit Transfer(from, to, id);
    }

    function safeTransferFrom(
        address from,
        address to,
        uint256 id
    ) public virtual {
        transferFrom(from, to, id);

        require(
            to.code.length == 0 ||
                ERC721TokenReceiver(to).onERC721Received(msg.sender, from, id, "") ==
                ERC721TokenReceiver.onERC721Received.selector,
            "UNSAFE_RECIPIENT"
        );
    }

    function safeTransferFrom(
        address from,
        address to,
        uint256 id,
        bytes calldata data
    ) public virtual {
        transferFrom(from, to, id);

        require(
            to.code.length == 0 ||
                ERC721TokenReceiver(to).onERC721Received(msg.sender, from, id, data) ==
                ERC721TokenReceiver.onERC721Received.selector,
            "UNSAFE_RECIPIENT"
        );
    }

    /*//////////////////////////////////////////////////////////////
                              ERC165 LOGIC
    //////////////////////////////////////////////////////////////*/

    function supportsInterface(bytes4 interfaceId) public view virtual returns (bool) {
        return
            interfaceId == 0x01ffc9a7 || // ERC165 Interface ID for ERC165
            interfaceId == 0x80ac58cd || // ERC165 Interface ID for ERC721
            interfaceId == 0x5b5e139f; // ERC165 Interface ID for ERC721Metadata
    }

    /*//////////////////////////////////////////////////////////////
                        INTERNAL MINT/BURN LOGIC
    //////////////////////////////////////////////////////////////*/

    function _mint(address to, uint256 id) internal virtual {
        require(to != address(0), "INVALID_RECIPIENT");

        require(_ownerOf[id] == address(0), "ALREADY_MINTED");

        // Counter overflow is incredibly unrealistic.
        unchecked {
            _balanceOf[to]++;
        }

        _ownerOf[id] = to;

        emit Transfer(address(0), to, id);
    }

    function _burn(uint256 id) internal virtual {
        address owner = _ownerOf[id];

        require(owner != address(0), "NOT_MINTED");

        // Ownership check above ensures no underflow.
        unchecked {
            _balanceOf[owner]--;
        }

        delete _ownerOf[id];

        delete getApproved[id];

        emit Transfer(owner, address(0), id);
    }

    /*//////////////////////////////////////////////////////////////
                        INTERNAL SAFE MINT LOGIC
    //////////////////////////////////////////////////////////////*/

    function _safeMint(address to, uint256 id) internal virtual {
        _mint(to, id);

        require(
            to.code.length == 0 ||
                ERC721TokenReceiver(to).onERC721Received(msg.sender, address(0), id, "") ==
                ERC721TokenReceiver.onERC721Received.selector,
            "UNSAFE_RECIPIENT"
        );
    }

    function _safeMint(
        address to,
        uint256 id,
        bytes memory data
    ) internal virtual {
        _mint(to, id);

        require(
            to.code.length == 0 ||
                ERC721TokenReceiver(to).onERC721Received(msg.sender, address(0), id, data) ==
                ERC721TokenReceiver.onERC721Received.selector,
            "UNSAFE_RECIPIENT"
        );
    }
}

/// @notice A generic interface for a contract which properly accepts ERC721 tokens.
/// @author Solmate (https://github.com/transmissions11/solmate/blob/main/src/tokens/ERC721.sol)
abstract contract ERC721TokenReceiver {
    function onERC721Received(
        address,
        address,
        uint256,
        bytes calldata
    ) external virtual returns (bytes4) {
        return ERC721TokenReceiver.onERC721Received.selector;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.4 <0.9.0;

interface IChessOlympiads {
    function mintPlayerBadge(uint256 _tokenId) external payable returns (uint256 _badgeId);
    function mintButtPlugBadge(address _buttPlug) external returns (uint256 _badgeId);
    function mintMedal(uint256[] memory _badgeIds) external returns (uint256 _badgeId);
    function withdrawRewards(uint256 _badgeId) external;
    function withdrawStakedNft(uint256 _badgeId) external;
    function startEvent() external;
    function pushLiquidity() external;
    function unbondLiquidity() external;
    function withdrawLiquidity() external;
    function updateSpotPrice() external;
    function workable() external view returns (bool _workable);
    function executeMove() external;
    function voteButtPlug(address _buttPlug, uint256 _badgeId) external;
    function voteButtPlug(address _buttPlug, uint256[] memory _badgeIds) external;
    function isWhitelistedToken(uint256 _id) external view returns (bool _isWhitelisted);
}

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.4 <0.9.0;

interface IButtPlug {
    function readMove(uint256 _board) external view returns (uint256 _move);

    function owner() external view returns (address _owner);
}

interface IChess {
    function mintMove(uint256 _move, uint256 _depth) external payable;

    function board() external view returns (uint256 _board);
}

{
  "remappings": [
    "@openzeppelin/=lib/openzeppelin-contracts/",
    "contracts/=solidity/contracts/",
    "ds-test/=lib/ds-test/src/",
    "fiveoutofnine/=lib/fiveoutofnine/src/",
    "forge-std/=lib/forge-std/src/",
    "interfaces/=solidity/interfaces/",
    "isolmate/=lib/isolmate/src/",
    "openzeppelin-contracts/=lib/openzeppelin-contracts/contracts/",
    "prb-test/=lib/prb-test/src/",
    "prb/test/=lib/prb-test/src/",
    "solmate/=lib/solmate/src/",
    "test/=solidity/test/"
  ],
  "optimizer": {
    "enabled": true,
    "runs": 10000
  },
  "metadata": {
    "bytecodeHash": "ipfs"
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "evmVersion": "london",
  "libraries": {}
}

• No Contract Security Audit Submitted- Submit Audit Here

[{"inputs":[],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"OnlyOwner","type":"error"},{"inputs":[],"name":"BADGE_ID","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"owner","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"_board","type":"uint256"}],"name":"readMove","outputs":[{"internalType":"uint256","name":"_move","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"_depth","type":"uint256"}],"name":"setDepth","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256","name":"_boardKeccak","type":"uint256"},{"internalType":"uint256","name":"_move","type":"uint256"}],"name":"setMove","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256[]","name":"_boards","type":"uint256[]"},{"internalType":"uint256[]","name":"_moves","type":"uint256[]"}],"name":"setMoves","outputs":[],"stateMutability":"nonpayable","type":"function"}]

60a0604052600760005534801561001557600080fd5b50600180546001600160a01b0319163317905561003130610039565b608052610080565b60006100546001600160601b0319606084901b16600261005a565b92915050565b6000821982111561007b57634e487b7160e01b600052601160045260246000fd5b500190565b6080516113096100af6000396000818160910152818161016c015281816102ea015261046c01526113096000f3fe608060405234801561001057600080fd5b50600436106100725760003560e01c806357c70b171161005057806357c70b17146100d9578063641db30e146100ec5780638da5cb5b146100ff57600080fd5b806336120c31146100775780634f35cc8e1461008c578063514c2dee146100c6575b600080fd5b61008a610085366004611170565b610144565b005b6100b37f000000000000000000000000000000000000000000000000000000000000000081565b6040519081526020015b60405180910390f35b61008a6100d43660046111d4565b6102c2565b6100b36100e73660046111f6565b6103e4565b61008a6100fa3660046111f6565b610444565b60015461011f9073ffffffffffffffffffffffffffffffffffffffff1681565b60405173ffffffffffffffffffffffffffffffffffffffff90911681526020016100bd565b6040517f6352211e0000000000000000000000000000000000000000000000000000000081527f0000000000000000000000000000000000000000000000000000000000000000600482015273220d6f53444fb9205083e810344a3a3989527a3490636352211e90602401602060405180830381865afa1580156101cc573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906101f0919061120f565b73ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff1614610254576040517f5fc483c500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60005b82518110156102bd5781818151811061027257610272611245565b60200260200101516002600085848151811061029057610290611245565b602002602001015181526020019081526020016000208190555080806102b590611274565b915050610257565b505050565b6040517f6352211e0000000000000000000000000000000000000000000000000000000081527f0000000000000000000000000000000000000000000000000000000000000000600482015273220d6f53444fb9205083e810344a3a3989527a3490636352211e90602401602060405180830381865afa15801561034a573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061036e919061120f565b73ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff16146103d2576040517f5fc483c500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60009182526002602052604090912055565b600060026000836040516020016103fd91815260200190565b6040516020818303038152906040528051906020012060001c81526020019081526020016000205490508060000361043f5761043b82600054610559565b5090505b919050565b6040517f6352211e0000000000000000000000000000000000000000000000000000000081527f0000000000000000000000000000000000000000000000000000000000000000600482015273220d6f53444fb9205083e810344a3a3989527a3490636352211e90602401602060405180830381865afa1580156104cc573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906104f0919061120f565b73ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff1614610554576040517f5fc483c500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600055565b60008060006105678561067e565b8051909150600003610580576000809250925050610677565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffef9c600080805b8481600581106105b8576105b8611245565b6020020151156106335760008582600581106105d6576105d6611245565b602002015190505b801561062a576105fe6105f58b610fff8416610a53565b60018b03610adb565b61060c8b610fff8416610c0e565b019350848413156106225783945080610fff1692505b600c1c6105de565b506001016105a6565b507ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffb1483121561066c576000809550955050505050610677565b9450506104ec129150505b9250929050565b610686611056565b61068e611074565b6000807adb5d33cb1badb2baa99a59238a179d71b69959551349138d30b2895b8015610a4657603f811660fc600283901b1687901c600f81168015806106db575088600116600382901c14155b156106e857505050610a3e565b600716600181900361078457602082901c600f1660000361073d57610711878460088101610dab565b600383901c600214801561072a5750600f604083901c16155b1561073d5761073d878460108101610dab565b61074b89601c84901c610e54565b1561075e5761075e878460078101610dab565b61076c89602484901c610e54565b1561077f5761077f878460098101610dab565b610a3a565b600381118015610795575060018116155b1561081c57806004146107ac5763010708096107b2565b63060a0f115b63ffffffff1695505b851561077f5760ff8616830194506107d38986610e79565b156107e3576107e3878487610dab565b828611158015610800575060ff8616830394506108008986610e79565b1561081057610810878487610dab565b600886901c95506107bb565b80600214610928578260010195505b6108358987610e79565b1561086557610845878488610dab565b61085689600288901b81901c610e54565b6108655760018601955061082b565b6001830395505b6108768987610e79565b156108a657610886878488610dab565b61089789600288901b81901c610e54565b6108a65760018603955061086c565b8260080195505b6108b78987610e79565b156108e7576108c7878488610dab565b6108d889600288901b81901c610e54565b6108e7576008860195506108ad565b6008830395505b6108f88987610e79565b1561092857610908878488610dab565b61091989600288901b81901c610e54565b610928576008860395506108ee565b80600314610a3a578260070195505b6109418987610e79565b1561097157610951878488610dab565b61096289600288901b81901c610e54565b61097157600786019550610937565b6007830395505b6109828987610e79565b156109b257610992878488610dab565b6109a389600288901b81901c610e54565b6109b257600786039550610978565b8260090195505b6109c38987610e79565b156109f3576109d3878488610dab565b6109e489600288901b81901c610e54565b6109f3576009860195506109b9565b6009830395505b610a048987610e79565b15610a3a578515610a3a57610a1a878488610dab565b610a2b89600288901b81901c610e54565b610a3a576009860395506109fa565b5050505b60061c6106ae565b5050506020015192915050565b600f7f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc600483901c1683811c821660fc600285901b1681811b9084901b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff9081189490931b92909218909416919091161791600090610ad184610eb9565b9150505b92915050565b600081600003610aed57506000610ad5565b6000610af88461067e565b8051909150600003610b0e576000915050610ad5565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffef9c600080805b848160058110610b4657610b46611245565b602002015115610ba6576000858260058110610b6457610b64611245565b602002015190505b8015610b9d57610b8089610fff8316610c0e565b935084841315610b955783945080610fff1692505b600c1c610b6c565b50600101610b34565b50600281603f16901b87901c600716600603610bca57610fa0945050505050610ad5565b6001871615610bf357610be9610be08883610a53565b60018803610adb565b8360000301610c03565b610c00610be08883610a53565b83015b979650505050505050565b60006007600683811c8216600985901c8202017ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff990810192808616600387901c8216909302929092010190600485901c7f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc1686901c811690600286901b60fc1687901c168480808315610cff576005841015610cc05785602303600702610cb485610ee1565b901c607f169050610cff565b6012861015610ce65785601103600c02610cd985610ee1565b901c610fff169050610cff565b85602303600c02610cf685610feb565b901c610fff1690505b6005851015610d355786600702610d1586610ee1565b901c607f16925085600702610d2986610ee1565b901c607f169150610d9e565b6012871015610d6d5786600c02610d4b86610feb565b901c610fff16925085600c02610d6086610feb565b901c610fff169150610d9e565b60128703600c02610d7d86610ee1565b901c610fff16925060128603600c02610d9586610ee1565b901c610fff1691505b0103979650505050505050565b825160208401516000908260058110610dc657610dc6611245565b602002015190507e40000000000000000000000000000000000000000000000000000000000000811115610e245760208501518551600101808752600686901b8517919060058110610e1a57610e1a611245565b6020020152610e4d565b82600685901b600c83901b171785602001518360058110610e4757610e47611245565b60200201525b5050505050565b6000600f821615801590610e72575082600116600383600f16901c14155b9392505050565b60006001667e7e7e7e7e7e00831c8116148015610e725750600f600283901b84901c161580610e7257505060021b81901c60031c60019081169116141590565b60008060005b604081101561043b57600484811c94600f1692901b9190911790600101610ebf565b600081600103610f1257507f02850a142850f1e3c78f1e2858c182c50a943468a152a788103c54a142850a14919050565b81600203610f4157507f07d0204080fa042850a140810e24487020448912240810e1428701f40810203e919050565b81600303610f7057507f0c993264c9932e6cd9b365c793264c98f1e4c993263c793264c98f264cb97264919050565b81600403610f9f57507f06ce1b3670e9c3c8101e38750224480e9d4189120ba70f20c178e1b3874e9c36919050565b81600503610fc957507a0b00b20b30b30b20b00b20b40b40b40b40b20b30b40b50b50b40b3919050565b507af9af98f96f96f98f9af9af98f96f96f98f9af9cf9af98f98f9af9b919050565b600081600514611016577af9ef9cf9cf9cf9cf9efa1fa1fa0fa0fa1fa1fa4fa6fa2fa2fa6fa4611033565b7a0b30b50b50b50b40b30b20b40b50b40b40b20b00b20b30b30b20b05b7affffffffffffffffffffffffffffffffffffffffffffffffffffff1692915050565b6040518060a001604052806005906020820280368337509192915050565b60405180604001604052806000815260200161108e611056565b905290565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052604160045260246000fd5b600082601f8301126110d357600080fd5b8135602067ffffffffffffffff808311156110f0576110f0611093565b8260051b6040517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0603f8301168101818110848211171561113357611133611093565b60405293845285810183019383810192508785111561115157600080fd5b83870191505b84821015610c0357813583529183019190830190611157565b6000806040838503121561118357600080fd5b823567ffffffffffffffff8082111561119b57600080fd5b6111a7868387016110c2565b935060208501359150808211156111bd57600080fd5b506111ca858286016110c2565b9150509250929050565b600080604083850312156111e757600080fd5b50508035926020909101359150565b60006020828403121561120857600080fd5b5035919050565b60006020828403121561122157600080fd5b815173ffffffffffffffffffffffffffffffffffffffff81168114610e7257600080fd5b7f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b60007fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff82036112cc577f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b506001019056fea264697066735822122019b8a06c4f4da5ae168f0c6f99ab035d0237f59b7266aeda5cb003de913a5e4764736f6c634300080e0033

0x608060405234801561001057600080fd5b50600436106100725760003560e01c806357c70b171161005057806357c70b17146100d9578063641db30e146100ec5780638da5cb5b146100ff57600080fd5b806336120c31146100775780634f35cc8e1461008c578063514c2dee146100c6575b600080fd5b61008a610085366004611170565b610144565b005b6100b37fbf11364f0e55a1fa0fae7cb492ed8d9dae3fa09d00000000000000000000000281565b6040519081526020015b60405180910390f35b61008a6100d43660046111d4565b6102c2565b6100b36100e73660046111f6565b6103e4565b61008a6100fa3660046111f6565b610444565b60015461011f9073ffffffffffffffffffffffffffffffffffffffff1681565b60405173ffffffffffffffffffffffffffffffffffffffff90911681526020016100bd565b6040517f6352211e0000000000000000000000000000000000000000000000000000000081527fbf11364f0e55a1fa0fae7cb492ed8d9dae3fa09d000000000000000000000002600482015273220d6f53444fb9205083e810344a3a3989527a3490636352211e90602401602060405180830381865afa1580156101cc573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906101f0919061120f565b73ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff1614610254576040517f5fc483c500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60005b82518110156102bd5781818151811061027257610272611245565b60200260200101516002600085848151811061029057610290611245565b602002602001015181526020019081526020016000208190555080806102b590611274565b915050610257565b505050565b6040517f6352211e0000000000000000000000000000000000000000000000000000000081527fbf11364f0e55a1fa0fae7cb492ed8d9dae3fa09d000000000000000000000002600482015273220d6f53444fb9205083e810344a3a3989527a3490636352211e90602401602060405180830381865afa15801561034a573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061036e919061120f565b73ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff16146103d2576040517f5fc483c500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60009182526002602052604090912055565b600060026000836040516020016103fd91815260200190565b6040516020818303038152906040528051906020012060001c81526020019081526020016000205490508060000361043f5761043b82600054610559565b5090505b919050565b6040517f6352211e0000000000000000000000000000000000000000000000000000000081527fbf11364f0e55a1fa0fae7cb492ed8d9dae3fa09d000000000000000000000002600482015273220d6f53444fb9205083e810344a3a3989527a3490636352211e90602401602060405180830381865afa1580156104cc573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906104f0919061120f565b73ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff1614610554576040517f5fc483c500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600055565b60008060006105678561067e565b8051909150600003610580576000809250925050610677565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffef9c600080805b8481600581106105b8576105b8611245565b6020020151156106335760008582600581106105d6576105d6611245565b602002015190505b801561062a576105fe6105f58b610fff8416610a53565b60018b03610adb565b61060c8b610fff8416610c0e565b019350848413156106225783945080610fff1692505b600c1c6105de565b506001016105a6565b507ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffb1483121561066c576000809550955050505050610677565b9450506104ec129150505b9250929050565b610686611056565b61068e611074565b6000807adb5d33cb1badb2baa99a59238a179d71b69959551349138d30b2895b8015610a4657603f811660fc600283901b1687901c600f81168015806106db575088600116600382901c14155b156106e857505050610a3e565b600716600181900361078457602082901c600f1660000361073d57610711878460088101610dab565b600383901c600214801561072a5750600f604083901c16155b1561073d5761073d878460108101610dab565b61074b89601c84901c610e54565b1561075e5761075e878460078101610dab565b61076c89602484901c610e54565b1561077f5761077f878460098101610dab565b610a3a565b600381118015610795575060018116155b1561081c57806004146107ac5763010708096107b2565b63060a0f115b63ffffffff1695505b851561077f5760ff8616830194506107d38986610e79565b156107e3576107e3878487610dab565b828611158015610800575060ff8616830394506108008986610e79565b1561081057610810878487610dab565b600886901c95506107bb565b80600214610928578260010195505b6108358987610e79565b1561086557610845878488610dab565b61085689600288901b81901c610e54565b6108655760018601955061082b565b6001830395505b6108768987610e79565b156108a657610886878488610dab565b61089789600288901b81901c610e54565b6108a65760018603955061086c565b8260080195505b6108b78987610e79565b156108e7576108c7878488610dab565b6108d889600288901b81901c610e54565b6108e7576008860195506108ad565b6008830395505b6108f88987610e79565b1561092857610908878488610dab565b61091989600288901b81901c610e54565b610928576008860395506108ee565b80600314610a3a578260070195505b6109418987610e79565b1561097157610951878488610dab565b61096289600288901b81901c610e54565b61097157600786019550610937565b6007830395505b6109828987610e79565b156109b257610992878488610dab565b6109a389600288901b81901c610e54565b6109b257600786039550610978565b8260090195505b6109c38987610e79565b156109f3576109d3878488610dab565b6109e489600288901b81901c610e54565b6109f3576009860195506109b9565b6009830395505b610a048987610e79565b15610a3a578515610a3a57610a1a878488610dab565b610a2b89600288901b81901c610e54565b610a3a576009860395506109fa565b5050505b60061c6106ae565b5050506020015192915050565b600f7f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc600483901c1683811c821660fc600285901b1681811b9084901b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff9081189490931b92909218909416919091161791600090610ad184610eb9565b9150505b92915050565b600081600003610aed57506000610ad5565b6000610af88461067e565b8051909150600003610b0e576000915050610ad5565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffef9c600080805b848160058110610b4657610b46611245565b602002015115610ba6576000858260058110610b6457610b64611245565b602002015190505b8015610b9d57610b8089610fff8316610c0e565b935084841315610b955783945080610fff1692505b600c1c610b6c565b50600101610b34565b50600281603f16901b87901c600716600603610bca57610fa0945050505050610ad5565b6001871615610bf357610be9610be08883610a53565b60018803610adb565b8360000301610c03565b610c00610be08883610a53565b83015b979650505050505050565b60006007600683811c8216600985901c8202017ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff990810192808616600387901c8216909302929092010190600485901c7f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc1686901c811690600286901b60fc1687901c168480808315610cff576005841015610cc05785602303600702610cb485610ee1565b901c607f169050610cff565b6012861015610ce65785601103600c02610cd985610ee1565b901c610fff169050610cff565b85602303600c02610cf685610feb565b901c610fff1690505b6005851015610d355786600702610d1586610ee1565b901c607f16925085600702610d2986610ee1565b901c607f169150610d9e565b6012871015610d6d5786600c02610d4b86610feb565b901c610fff16925085600c02610d6086610feb565b901c610fff169150610d9e565b60128703600c02610d7d86610ee1565b901c610fff16925060128603600c02610d9586610ee1565b901c610fff1691505b0103979650505050505050565b825160208401516000908260058110610dc657610dc6611245565b602002015190507e40000000000000000000000000000000000000000000000000000000000000811115610e245760208501518551600101808752600686901b8517919060058110610e1a57610e1a611245565b6020020152610e4d565b82600685901b600c83901b171785602001518360058110610e4757610e47611245565b60200201525b5050505050565b6000600f821615801590610e72575082600116600383600f16901c14155b9392505050565b60006001667e7e7e7e7e7e00831c8116148015610e725750600f600283901b84901c161580610e7257505060021b81901c60031c60019081169116141590565b60008060005b604081101561043b57600484811c94600f1692901b9190911790600101610ebf565b600081600103610f1257507f02850a142850f1e3c78f1e2858c182c50a943468a152a788103c54a142850a14919050565b81600203610f4157507f07d0204080fa042850a140810e24487020448912240810e1428701f40810203e919050565b81600303610f7057507f0c993264c9932e6cd9b365c793264c98f1e4c993263c793264c98f264cb97264919050565b81600403610f9f57507f06ce1b3670e9c3c8101e38750224480e9d4189120ba70f20c178e1b3874e9c36919050565b81600503610fc957507a0b00b20b30b30b20b00b20b40b40b40b40b20b30b40b50b50b40b3919050565b507af9af98f96f96f98f9af9af98f96f96f98f9af9cf9af98f98f9af9b919050565b600081600514611016577af9ef9cf9cf9cf9cf9efa1fa1fa0fa0fa1fa1fa4fa6fa2fa2fa6fa4611033565b7a0b30b50b50b50b40b30b20b40b50b40b40b20b00b20b30b30b20b05b7affffffffffffffffffffffffffffffffffffffffffffffffffffff1692915050565b6040518060a001604052806005906020820280368337509192915050565b60405180604001604052806000815260200161108e611056565b905290565b7f4e487b7100000000000000000000000000000000000000000000000000000000600052604160045260246000fd5b600082601f8301126110d357600080fd5b8135602067ffffffffffffffff808311156110f0576110f0611093565b8260051b6040517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0603f8301168101818110848211171561113357611133611093565b60405293845285810183019383810192508785111561115157600080fd5b83870191505b84821015610c0357813583529183019190830190611157565b6000806040838503121561118357600080fd5b823567ffffffffffffffff8082111561119b57600080fd5b6111a7868387016110c2565b935060208501359150808211156111bd57600080fd5b506111ca858286016110c2565b9150509250929050565b600080604083850312156111e757600080fd5b50508035926020909101359150565b60006020828403121561120857600080fd5b5035919050565b60006020828403121561122157600080fd5b815173ffffffffffffffffffffffffffffffffffffffff81168114610e7257600080fd5b7f4e487b7100000000000000000000000000000000000000000000000000000000600052603260045260246000fd5b60007fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff82036112cc577f4e487b7100000000000000000000000000000000000000000000000000000000600052601160045260246000fd5b506001019056fea264697066735822122019b8a06c4f4da5ae168f0c6f99ab035d0237f59b7266aeda5cb003de913a5e4764736f6c634300080e0033