BA5ED.sol

// SPDX-License-Identifier: MIT
pragma solidity 0.8.13;
import "./Car.sol";

// The strategy used to reach #5 (1486.41 ELO) in 0xMonaco
// https://twitter.com/0xBA5ED

// This contract contains bugs and has ineffecient gas usage, do not use it in production
contract BA5ED is Car {
    uint256 internal constant PANIC_MODE_MOVES = 5;
    uint256 internal constant FINISH_DISTANCE = 1000;
    uint256 internal constant INITIAL_ACCELERATION_COST = 12;

    constructor(Monaco _monaco) Car(_monaco) {}

     function takeYourTurn(Monaco.CarData[] calldata allCars, uint256 ourCarIndex) external override {
        Monaco.CarData memory ourCar = allCars[ourCarIndex];

        // If this is the first move
        if(ourCar.y == 0){
            // Check if we are the first car to be allowed a move
            if(monaco.getAccelerateCost(1) <= INITIAL_ACCELERATION_COST){
                // Price gouge acceleration 
                ourCar.balance -= uint24(monaco.buyAcceleration(15));
            // Make sure no one else is price gouging
            }else if(ourCar.balance / 11 > monaco.getAccelerateCost(8)){
                ourCar.balance -= uint24(monaco.buyAcceleration(8));
            // Try a lower amount
            }else if(ourCar.balance / 10 > monaco.getAccelerateCost(1)){
                ourCar.balance -= uint24(monaco.buyAcceleration(1));
            }else{
                // Cost to buy acceleration is too high, so check if we can shell someone and incurr them cost
                (bool canWeShell, uint256 nearestSpeed, uint256 nearestPosition,) = canShell(ourCar, allCars, ourCarIndex);
                uint256 shellCost = monaco.getShellCost(1);

                // Is the cost of buying speed higher for them than it is for us to shell them? 
                if(shellCost < (ourCar.balance / 10) && nearestSpeed > 1 && monaco.getAccelerateCost(nearestSpeed - 1) > shellCost){
                    ourCar.balance -= uint24(monaco.buyShell(1));
                }
            }

            return;
        }

        // We got shelled? Poomp it
        if(ourCar.speed == 1){
            // If we have plenty left
            if(ourCar.balance / 5 > monaco.getAccelerateCost(3)){
                ourCar.balance -= uint24(monaco.buyAcceleration(3));
                ourCar.speed += 3;
            }
        }

        // Always buy acceleration below floor price
        ourCar = scoopFloor(ourCar);
        
        // accelaration is cheap, scoop it
        if(monaco.getAccelerateCost(1) < ourCar.balance / (4 * ourCar.speed)){
            ourCar.balance -= uint24(monaco.buyAcceleration(1));
            ourCar.speed += 1;
        }

        // Check the cost of buying an instant win, if we have enough do it
        uint256 distanceUntilWin = FINISH_DISTANCE - ourCar.y;
        if(distanceUntilWin < 200 && distanceUntilWin > ourCar.speed && monaco.getAccelerateCost(distanceUntilWin - ourCar.speed) < ourCar.balance){
            ourCar.balance -= uint24(monaco.buyAcceleration(distanceUntilWin - ourCar.speed));
            ourCar.speed = uint24(distanceUntilWin);
        }else{
            // Check if we need to enter panic mode or not
            (bool inPanicMode,) = panicModeCheck(ourCar, allCars, ourCarIndex);
            // Check if we have entered panic mode or not, if we have no further actions are needed
            if(inPanicMode){
                return;
            }
        }

        // If we are not in the lead
        if(ourCarIndex != 0){
            // Can we shell em?
            (bool canWeShell, uint256 nearestSpeed, uint256 nearestPosition, uint256 nearestBalance) = canShell(ourCar, allCars, ourCarIndex);
            uint256 distanceUntilNearestWins = FINISH_DISTANCE - nearestPosition;

            uint256 shellCost = monaco.getShellCost(1);

            // Will they win next turn or can they instant buy a win, if so attempt to shell them and gain warpSpeed
            // This is a last restort
            if(distanceUntilNearestWins < 200 && (distanceUntilNearestWins <= nearestSpeed || monaco.getAccelerateCost(distanceUntilNearestWins - nearestSpeed) < nearestBalance) && canWeShell){
                // SHELL
                ourCar.balance -= uint24(monaco.buyShell(1));   
                // WARP
                warpSpeed(ourCar);

                // Can we shell? Will we lose if we don't? Will we win if we do? 
            }else if(canWeShell && !willPass(ourCar.y, ourCar.speed, nearestPosition, nearestSpeed) && willPass(ourCar.y, ourCar.speed, nearestPosition, 1)){
                // Check how close we are to the finish, shell if worth it
                if(distanceUntilWin < 100){
                     ourCar.balance -= uint24(monaco.buyShell(1));
                }else if(distanceUntilWin < 400 && shellCost < (ourCar.balance / 2)){
                     ourCar.balance -= uint24(monaco.buyShell(1));
                }else if(shellCost < (ourCar.balance / 20)){
                    ourCar.balance -= uint24(monaco.buyShell(1));   
                }
            }
        }
    }

    /**
     * Can we shell someone, if we can return all the info regarding who we are shelling
     */
    function canShell(Monaco.CarData memory ourCar, Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal returns(bool canWeShell, uint256 speed, uint256 position, uint256 carBalance){
        uint256 nOfCars = allCars.length;

        if(ourCar.balance < monaco.getShellCost(1)){
            return (false, 0, 0, 0);
        }

        Car closestCar; // Used to determine who to shell.
        uint256 distanceFromClosestCar = type(uint256).max;

        for (uint256 i = 0; i < 3; i++) {
            if(i == ourCarIndex){
                continue;
            }

            Monaco.CarData memory nextCar = allCars[i];

            // If the car is behind or on us, skip it.
            if (nextCar.y <= ourCar.y) continue;

            // Measure the distance from the car to us.
            uint256 distanceFromNextCar = nextCar.y - ourCar.y;

            // If this car is closer than all other cars we've
            // looked at so far, we'll make it the closest one.
            if (distanceFromNextCar < distanceFromClosestCar) {
                canWeShell = true;

                carBalance = nextCar.balance;
                closestCar = nextCar.car;
                position = nextCar.y;
                speed = nextCar.speed;
            }
        }
    }

    /**
     * Check if CarA will pas CarB before the end of the game
     */
    function willPass(uint256 carAPosition, uint256 carASpeed, uint256 carBPosition, uint256 carBSpeed) internal returns(bool) {
        uint256 distanceToClose = carBPosition - carAPosition;
        uint256 movesTillTheyFinish = (FINISH_DISTANCE - carBPosition) / carBSpeed;
        uint256 movesTillWeFinish = (FINISH_DISTANCE - carAPosition) / carASpeed;

        return movesTillTheyFinish > movesTillWeFinish;
    }

    /**
     * Attempt to gain max speed spending all our coins in the process
     */
    function warpSpeed(Monaco.CarData memory ourCar) internal returns (Monaco.CarData memory) {
        // Attempt to get the max speed we can
        while(ourCar.balance > monaco.getAccelerateCost(1)){
            ourCar.balance -= uint24(monaco.buyAcceleration(1));
            ourCar.speed += 1;
        }

        return ourCar;
    }

    /**
     * Buy cheap acceleration, force others to buy at a price above this floor
     */
    function scoopFloor(Monaco.CarData memory ourCar) internal returns (Monaco.CarData memory) {
        // Buy all acceleration at floor price and below
        while(monaco.getAccelerateCost(1) <= INITIAL_ACCELERATION_COST && ourCar.balance <= INITIAL_ACCELERATION_COST){
            ourCar.balance -= uint24(monaco.buyAcceleration(1));
            ourCar.speed += 1;
        }

        return ourCar;
    }

    /**
     * Check if the game is about to end and we need to make drastic moves
     */
    function panicModeCheck(Monaco.CarData memory ourCar, Monaco.CarData[] calldata allCars, uint256 ourCarIndex) internal returns(bool, Monaco.CarData memory) {
        Monaco.CarData memory closestToFinish;
        // if true this means we can shell the car closest to winning
        bool carBehindUs = false;
        bool carInFront = false;
        
        for (uint256 i = 0; i < 3; i++) {
            if(i == ourCarIndex){
                continue;
            }

            Monaco.CarData memory nextCar = allCars[i];

            if(nextCar.y > closestToFinish.y){
                closestToFinish = nextCar;
                if(closestToFinish.y > ourCar.y){
                    carInFront = true;
                }
            }
            
            if(nextCar.y < ourCar.y){
                carBehindUs = true;
            }
        }
        
        uint256 distanceUntilLose = (FINISH_DISTANCE - closestToFinish.y);
        uint256 movesUntilLose = distanceUntilLose / closestToFinish.speed;

        // If they are close enough where they can buy enough speed to finish next turn we price gouge to prevent that
        if(!carBehindUs && distanceUntilLose < 200 && distanceUntilLose > closestToFinish.speed && monaco.getAccelerateCost(distanceUntilLose - closestToFinish.speed) <= closestToFinish.balance){
            return (true, warpSpeed(ourCar));
        }

        // Check if panic mode should be active or not
        if(movesUntilLose > PANIC_MODE_MOVES){
            return (false, ourCar);
        }

        // if there is no car behind us we should do a quick pass by at the end
        if(!carBehindUs){
            return (true, attemptQuickPass(ourCar, allCars, ourCarIndex, movesUntilLose));
        }

        // we are middle in the pack
        if(carBehindUs && carInFront){
            return (true, attemptQuickPass(ourCar, allCars, ourCarIndex, movesUntilLose));
        }

        // we are in front
        if(!carInFront){
            ourCar = warpSpeed(ourCar);
            return (true, ourCar);
        }
    }

    /**
     * Used when in second or last place to attempt getting a position ahead, at any cost
     */
    function attemptQuickPass(Monaco.CarData memory ourCar, Monaco.CarData[] calldata allCars, uint256 ourCarIndex, uint256 movesUntilLose) internal returns (Monaco.CarData memory){
        (bool canWeShell, uint256 nearestSpeed, uint256 nearestPosition, uint256 nearestBalance) = canShell(ourCar, allCars, ourCarIndex);
        uint256 theirPositionOnEnd = nearestPosition + (nearestSpeed * movesUntilLose);
        uint256 ourPositionOnEnd = ourCar.y + (ourCar.speed * movesUntilLose);

        // Can we pass the person in front before we lose 
        if(theirPositionOnEnd >= ourPositionOnEnd){
            uint256 extraSpeedNeeded;
            if(movesUntilLose != 0){
                extraSpeedNeeded = (theirPositionOnEnd - ourPositionOnEnd) / movesUntilLose;
            }else{
                extraSpeedNeeded = (theirPositionOnEnd - ourPositionOnEnd);
            }

            // Check if slowing them down also works
            if(canWeShell && nearestSpeed * movesUntilLose >= extraSpeedNeeded && monaco.getShellCost(1) < ourCar.balance){
                // Slowing them down is cheaper
                ourCar.balance -= uint24(monaco.buyShell(1));
                // Buy slight bit extra speed to poomp the price for them and to be sure we pass
                if(monaco.getAccelerateCost(2) < ourCar.balance){
                    ourCar.balance -= uint24(monaco.buyAcceleration(2));
                }
                // hopefully that is enough
                return ourCar;
            }

            // If we can't shell because we lack the funds, or they are going to slow for it to matter attempt to increase our speed
            if(monaco.getAccelerateCost(extraSpeedNeeded) < ourCar.balance){
                ourCar.balance -= uint24(monaco.buyAcceleration(extraSpeedNeeded));
                return ourCar;
            }

            // we have to try something, warp speed it is
            return warpSpeed(ourCar);
        }

        return ourCar;
    }
}