Yolanda R position.cpp

#include "position.h"
#include <algorithm>

// Initialize ray table
RayTable Rays;

// Generate all legal moves for the current player
std::vector<Move> Position::generateMoves() const {
    std::vector<Move> moves;

    // Masks for empty and occupied squares
    Bitboard emptyMask = emptySquares;

    // Mask of stones belonging to side to move
    Bitboard playerBits = whiteToMove ? whitePieces : blackPieces;
    int stonesInHand = whiteToMove ? whiteStonesInHand : blackStonesInHand;

    // 1. Mandatory FLIP moves: flip the nearest non-flipped blocker (own or opponent)
    std::vector<Move> flipMoves;

    // Mask of all stones (including flipped)
    Bitboard allStonesMask = whitePieces | blackPieces | flippedPieces;

    // Mask of non-flipped stones that can be flipped
    Bitboard nonFlippedStoneMask = whitePieces | blackPieces;

    for (Bitboard bb = playerBits; bb; bb &= bb - 1) {
        int fromSq = __builtin_ctz(bb);

        // Helper: find the first blocker (of any type) along a ray
        auto firstBlock = [&](const Bitboard ray, bool reversed) -> int {
            Bitboard blockers = ray & allStonesMask;
            if (!blockers) return -1; // No blocker found

            // Use ctz directly for forward direction, adjusted clz for reversed
            return reversed ? 31 - __builtin_clz(blockers) : __builtin_ctz(blockers);
        };

        // Check all four orthogonal directions
        int northBlocker = firstBlock(Rays.getNorth(fromSq), false);
        int eastBlocker = firstBlock(Rays.getEast(fromSq), false);
        int southBlocker = firstBlock(Rays.getSouth(fromSq), true);
        int westBlocker = firstBlock(Rays.getWest(fromSq), true);

        // Add FLIP moves for non-flipped blockers
        if (northBlocker != -1 && (nonFlippedStoneMask & (Bitboard(1) << northBlocker))) {
            flipMoves.emplace_back(fromSq, northBlocker, FLIP);
        }
        if (eastBlocker != -1 && (nonFlippedStoneMask & (Bitboard(1) << eastBlocker))) {
            flipMoves.emplace_back(fromSq, eastBlocker, FLIP);
        }
        if (southBlocker != -1 && (nonFlippedStoneMask & (Bitboard(1) << southBlocker))) {
            flipMoves.emplace_back(fromSq, southBlocker, FLIP);
        }
        if (westBlocker != -1 && (nonFlippedStoneMask & (Bitboard(1) << westBlocker))) {
            flipMoves.emplace_back(fromSq, westBlocker, FLIP);
        }
    }

    // FLIP has absolute priority - if any available, return only those
    if (!flipMoves.empty()) {
        return flipMoves;
    }

    // 2. No FLIP possible: generate DROP, MOVE, REMOVE

    // 2a) DROP: place from hand onto any empty square
    if (stonesInHand > 0) {
        for (Bitboard em = emptyMask; em; em &= em - 1) {
            int sq = __builtin_ctz(em);
            moves.emplace_back(NO_SQUARE, sq, DROP);
        }
    }

    // 2b) MOVE: slide stones to empty squares before first blocker or edge
    for (Bitboard bb = playerBits; bb; bb &= bb - 1) {
        int fromSq = __builtin_ctz(bb);

        // Process each direction
        auto collectSlides = [&](const Bitboard ray, bool reversed) {
            Bitboard blockers = ray & allStonesMask;
            Bitboard reach;

            if (blockers) {
                int blockSq = reversed ? 31 - __builtin_clz(blockers) : __builtin_ctz(blockers);

                // Calculate reachable squares up to blocker
                if (!reversed)
                    reach = ray & ((Bitboard(1) << blockSq) - 1);
                else
                    reach = ray & ~((Bitboard(1) << (blockSq + 1)) - 1);
            } else {
                // No blockers - can reach all squares in this direction
                reach = ray;
            }

            // Generate moves to all empty squares in reach
            for (Bitboard tgt = reach & emptyMask; tgt; tgt &= tgt - 1) {
                int toSq = __builtin_ctz(tgt);
                moves.emplace_back(fromSq, toSq, MOVE);
            }
        };

        collectSlides(Rays.getNorth(fromSq), false);
        collectSlides(Rays.getEast(fromSq), false);
        collectSlides(Rays.getSouth(fromSq), true);
        collectSlides(Rays.getWest(fromSq), true);
    }

    // 2c) REMOVE: move onto flipped stone, removing it
    for (Bitboard bb = playerBits; bb; bb &= bb - 1) {
        int fromSq = __builtin_ctz(bb);

        auto collectRemoves = [&](const Bitboard ray, bool reversed) {
            Bitboard blockers = ray & allStonesMask;
            if (!blockers) return;

            int blockSq = reversed ? 31 - __builtin_clz(blockers) : __builtin_ctz(blockers);
            Bitboard mask = Bitboard(1) << blockSq;

            // Can only remove flipped stones
            if (flippedPieces & mask) {
                moves.emplace_back(fromSq, blockSq, REMOVE);
            }
        };

        collectRemoves(Rays.getNorth(fromSq), false);
        collectRemoves(Rays.getEast(fromSq), false);
        collectRemoves(Rays.getSouth(fromSq), true);
        collectRemoves(Rays.getWest(fromSq), true);
    }

    return moves;
}

// Execute a move and update position state
void Position::makeMove(const Move& move) {
    // Store the previous Zobrist key for unmake
    uint64_t previousKey = zobristKey;

    // Compute bit masks for source and target
    Bitboard fromBit = move.from == NO_SQUARE ? 0 : (Bitboard(1) << move.from);
    Bitboard toBit = Bitboard(1) << move.to;

    // Update side to move in zobrist key
    zobristKey ^= ZOBRIST_SIDE;

    switch (move.type) {
        case FLIP:
            // Remove moving stone into hand
            if (whiteToMove) {
                whitePieces &= ~fromBit;
                whiteStonesInHand++;
                zobristKey ^= Zobrist::whitePiece[move.from];
                zobristKey ^= Zobrist::whiteHandCount[whiteStonesInHand-1];
                zobristKey ^= Zobrist::whiteHandCount[whiteStonesInHand];
            } else {
                blackPieces &= ~fromBit;
                blackStonesInHand++;
                zobristKey ^= Zobrist::blackPiece[move.from];
                zobristKey ^= Zobrist::blackHandCount[blackStonesInHand-1];
                zobristKey ^= Zobrist::blackHandCount[blackStonesInHand];
            }

            // Mark target as flipped
            flippedPieces |= toBit;
            zobristKey ^= Zobrist::flipped[move.to];

            // Remove target from whichever pieces it belonged to
            if (whitePieces & toBit) {
                whitePieces &= ~toBit;
                zobristKey ^= Zobrist::whitePiece[move.to];
            } else if (blackPieces & toBit) {
                blackPieces &= ~toBit;
                zobristKey ^= Zobrist::blackPiece[move.to];
            }
            break;

        case DROP:
            // Place stone from hand to board
            if (whiteToMove) {
                whiteStonesInHand--;
                whitePieces |= toBit;
                zobristKey ^= Zobrist::whiteHandCount[whiteStonesInHand+1];
                zobristKey ^= Zobrist::whiteHandCount[whiteStonesInHand];
                zobristKey ^= Zobrist::whitePiece[move.to];
            } else {
                blackStonesInHand--;
                blackPieces |= toBit;
                zobristKey ^= Zobrist::blackHandCount[blackStonesInHand+1];
                zobristKey ^= Zobrist::blackHandCount[blackStonesInHand];
                zobristKey ^= Zobrist::blackPiece[move.to];
            }
            break;

        case MOVE:
            // Move stone on board
            if (whiteToMove) {
                whitePieces &= ~fromBit;
                whitePieces |= toBit;
                zobristKey ^= Zobrist::whitePiece[move.from];
                zobristKey ^= Zobrist::whitePiece[move.to];
            } else {
                blackPieces &= ~fromBit;
                blackPieces |= toBit;
                zobristKey ^= Zobrist::blackPiece[move.from];
                zobristKey ^= Zobrist::blackPiece[move.to];
            }
            break;

        case REMOVE:
            // Move onto flipped stone and remove it
            if (whiteToMove) {
                whitePieces &= ~fromBit;
                whitePieces |= toBit;
                zobristKey ^= Zobrist::whitePiece[move.from];
                zobristKey ^= Zobrist::whitePiece[move.to];
            } else {
                blackPieces &= ~fromBit;
                blackPieces |= toBit;
                zobristKey ^= Zobrist::blackPiece[move.from];
                zobristKey ^= Zobrist::blackPiece[move.to];
            }
            // Unflip the target
            flippedPieces &= ~toBit;
            zobristKey ^= Zobrist::flipped[move.to];
            break;
    }

    // Recompute empty squares mask using direct hex value
    emptySquares = ~(whitePieces | blackPieces | flippedPieces) & 0xFFFF;

    // Update move counters and history
    halfmoveClock++;
    fullmoveNumber += (whiteToMove ? 0 : 1);
    history.push_back(previousKey); // Store the previous key

    // Switch side to move
    whiteToMove = !whiteToMove;
}

// Check if the game is over
bool Position::isGameOver() const {
    // Game is over if no legal moves
    return generateMoves().empty();
}

// Determine the winner (if game is over)
StoneColor Position::getWinner() const {
    if (!isGameOver()) {
        return NONE; // Game still in progress
    }

    // The player who has no legal moves WINS (according to Yolanda rules)
    return whiteToMove ? WHITE : BLACK;
}

// Evaluation function
int Position::evaluate() const {
    // Material difference
    int whiteMaterial = __builtin_popcount(whitePieces) + whiteStonesInHand;
    int blackMaterial = __builtin_popcount(blackPieces) + blackStonesInHand;

    // Count flipped stones
    int flippedCount = __builtin_popcount(flippedPieces);

    // Evaluate mobility (number of legal moves)
    int mobilityBonus = 3;
    int moveCount = generateMoves().size();
    int mobilityScore = 0;

    // In Yolanda, having no moves is a WIN
    if (moveCount == 0) {
        return whiteToMove ? +10000 : -10000;
    } else {
        mobilityScore = moveCount * mobilityBonus * (whiteToMove ? 1 : -1);
    }

    // Return evaluation from white's perspective
    return (whiteMaterial - blackMaterial) * 15 + mobilityScore;
}

// Unmake a move (for search)
void Position::unmakeMove(const Move& move, StoneColor originalTarget) {
    // Switch side to move back
    whiteToMove = !whiteToMove;

    // Revert history tracking
    halfmoveClock--;
    if (!whiteToMove) {
        fullmoveNumber--;
    }

    // Get the previous Zobrist key
    uint64_t previousKey = 0;
    if (!history.empty()) {
        previousKey = history.back();
        history.pop_back();
    }

    // Handle each move type differently
    switch (move.type) {
        case FLIP:
            // Restore moving stone from hand
            if (whiteToMove) {
                whitePieces |= (Bitboard(1) << move.from);
                whiteStonesInHand--;
            } else {
                blackPieces |= (Bitboard(1) << move.from);
                blackStonesInHand--;
            }

            // Unflip the target
            flippedPieces &= ~(Bitboard(1) << move.to);

            // Restore original color of target
            if (originalTarget == WHITE) {
                whitePieces |= (Bitboard(1) << move.to);
            } else if (originalTarget == BLACK) {
                blackPieces |= (Bitboard(1) << move.to);
            }
            break;

        case DROP:
            // Remove stone from board back to hand
            if (whiteToMove) {
                whitePieces &= ~(Bitboard(1) << move.to);
                whiteStonesInHand++;
            } else {
                blackPieces &= ~(Bitboard(1) << move.to);
                blackStonesInHand++;
            }
            break;

        case MOVE:
            // Move stone back to original position
            if (whiteToMove) {
                whitePieces &= ~(Bitboard(1) << move.to);
                whitePieces |= (Bitboard(1) << move.from);
            } else {
                blackPieces &= ~(Bitboard(1) << move.to);
                blackPieces |= (Bitboard(1) << move.from);
            }
            break;

        case REMOVE:
            // Move stone back to original position
            if (whiteToMove) {
                whitePieces &= ~(Bitboard(1) << move.to);
                whitePieces |= (Bitboard(1) << move.from);
            } else {
                blackPieces &= ~(Bitboard(1) << move.to);
                blackPieces |= (Bitboard(1) << move.from);
            }

            // Restore flipped stone
            flippedPieces |= (Bitboard(1) << move.to);
            break;
    }

    // Recompute empty squares with direct hex value
    emptySquares = ~(whitePieces | blackPieces | flippedPieces) & 0xFFFF;

    // Restore the previous Zobrist key directly
    zobristKey = previousKey;
}

// Display the board state
void Position::printBoard() const {
    std::cout << "\n  +---+---+---+---+\n";
    for (int row = BOARD_SIZE - 1; row >= 0; row--) {
        std::cout << (row + 1) << " |";
        for (int col = 0; col < BOARD_SIZE; col++) {
            int square = row * BOARD_SIZE + col;
            Bitboard mask = Bitboard(1) << square;
            char piece = ' ';
            if (whitePieces & mask) piece = 'W';
            else if (blackPieces & mask) piece = 'B';
            else if (flippedPieces & mask) piece = 'O';
            else piece = '.';
            std::cout << ' ' << piece << ' ' << '|';
        }
        if (row == BOARD_SIZE - 1) {
            std::cout << "  [" << blackStonesInHand << "]";
            if (!whiteToMove) std::cout << "*";
        } else if (row == 0) {
            std::cout << "  [" << whiteStonesInHand << "]";
            if (whiteToMove) std::cout << "*";
        }
        std::cout << "\n  +---+---+---+---+\n";
    }
    std::cout << "    a   b   c   d  \n";
}

// Debug function for FLIP detection
void Position::debugFlipDetection(int fromSquare, int toSquare) const {
    // Validate squares
    if (fromSquare < 0 || fromSquare >= SQUARE_COUNT || toSquare < 0 || toSquare >= SQUARE_COUNT) {
        std::cout << "Invalid square indices!" << std::endl;
        return;
    }

    // Check if 'from' square has a piece
    Bitboard fromBit = Bitboard(1) << fromSquare;
    if (!(whitePieces & fromBit) && !(blackPieces & fromBit)) {
        std::cout << "No piece at " << SQUARE_NAMES[fromSquare] << std::endl;
        return;
    }

    // Check if 'to' square has a piece
    Bitboard toBit = Bitboard(1) << toSquare;
    if (!(whitePieces & toBit) && !(blackPieces & toBit) && !(flippedPieces & toBit)) {
        std::cout << "No piece at " << SQUARE_NAMES[toSquare] << std::endl;
        return;
    }

    // Check if 'to' square has a flipped piece
    if (flippedPieces & toBit) {
        std::cout << "Target at " << SQUARE_NAMES[toSquare] << " is already flipped" << std::endl;
        return;
    }

    // Determine direction
    int fromRow = fromSquare / BOARD_SIZE;
    int fromCol = fromSquare % BOARD_SIZE;
    int toRow = toSquare / BOARD_SIZE;
    int toCol = toSquare % BOARD_SIZE;

    // Calculate deltas
    int rowDelta = toRow - fromRow;
    int colDelta = toCol - fromCol;

    std::cout << "From " << SQUARE_NAMES[fromSquare] << " to " << SQUARE_NAMES[toSquare] << ":" << std::endl;
    std::cout << "Row delta: " << rowDelta << ", Col delta: " << colDelta << std::endl;

    // Check if orthogonal
    if (rowDelta != 0 && colDelta != 0) {
        std::cout << "Not orthogonal movement!" << std::endl;
        return;
    }

    // Determine ray direction
    Bitboard ray;
    bool reversed = false;

    if (rowDelta > 0 && colDelta == 0) {
        std::cout << "Direction: North" << std::endl;
        ray = Rays.getNorth(fromSquare);
    } else if (rowDelta < 0 && colDelta == 0) {
        std::cout << "Direction: South" << std::endl;
        ray = Rays.getSouth(fromSquare);
        reversed = true;
    } else if (rowDelta == 0 && colDelta > 0) {
        std::cout << "Direction: East" << std::endl;
        ray = Rays.getEast(fromSquare);
    } else if (rowDelta == 0 && colDelta < 0) {
        std::cout << "Direction: West" << std::endl;
        ray = Rays.getWest(fromSquare);
        reversed = true;
    }

    // Print ray content
    std::cout << "Ray bitmap: 0x" << std::hex << ray << std::dec << std::endl;

    // Check if target is in ray
    if (!(ray & toBit)) {
        std::cout << "Target is not in ray path!" << std::endl;
        return;
    }

    // Mask of all stones
    Bitboard allStonesMask = whitePieces | blackPieces | flippedPieces;

    // Find the first blocker
    Bitboard blockers = ray & allStonesMask;
    if (!blockers) {
        std::cout << "No blockers found in ray!" << std::endl;
        return;
    }

    int blockSq = reversed
        ? 31 - __builtin_clz(blockers)
        : __builtin_ctz(blockers);

    std::cout << "First blocker: " << SQUARE_NAMES[blockSq] << std::endl;

    if (blockSq != toSquare) {
        std::cout << "First blocker is not the target!" << std::endl;
        return;
    }

    // Check if a FLIP move would be possible
    Bitboard targetBit = Bitboard(1) << blockSq;
    if ((whitePieces & targetBit) || (blackPieces & targetBit)) {
        std::cout << "A FLIP move is possible from " << SQUARE_NAMES[fromSquare]
                 << " to " << SQUARE_NAMES[blockSq] << std::endl;
    } else {
        std::cout << "Target is flipped - cannot FLIP" << std::endl;
    }
}