EthFiddle - Solidity IDE in the Browser. Powered By Loom Network

// SPDX-License-Identifier: GPL-3.0
/* today's date: 4/11/2022 08:31
*/
 
pragma solidity >=0.7.0 <0.9.0;
 
import "@openzeppelin/contracts/utils/math/Math.sol";  //openzeppelin's math library to use min and max
 
/* title: TorusTacToe
dev: Play tic tac toe against the contract on a special torus board, player 1 is O (user) and player 2 is X (contract) */
contract TorusTacToe {
    /* the 72 rightmost bits represent the 36 pieces
       with each piece represented by 2 bits
       (00 = empty, 01 = user marker aka O, 10 = contract marker aka X) */
    uint256 torusState;
 
 
    function searchForMove(uint256 possibleTorus, uint256 depth, bool isContract) public pure returns (int) {    //the minimax function, do alpha beta later
        if(depth == 3) {     //max depth is 3
            return evaluateTorus(possibleTorus);
        }
        if(isContract == false){   // user's turn
            bool torusFull = true;
            int minPoints = type(int).max;
            for(uint256 posIndex = 0; posIndex < 36; ++posIndex) {
                if( possibleTorus & (3 << posIndex*2) == 0 ){   // piece at index posIndex is empty
                    torusFull = false;
                    int points = searchForMove(possibleTorus | (1 << posIndex*2), depth + 1, true);
                    if(points < minPoints){
                        minPoints = points;
                    }
                }
            }
            if(torusFull){
                return evaluateTorus(possibleTorus);
            }
            return minPoints;
        }
        else{    //contract's turn
            uint256 optimalMovePos;   // only used if depth is 0
            int maxPoints = type(int).min;
            for(uint256 posIndex = 0; posIndex < 36; ++posIndex) {
                if( possibleTorus & (3 << posIndex*2) == 0 ){
                    int points = searchForMove(possibleTorus | (1 << (posIndex*2+1)), depth + 1, false);
                    if(points > maxPoints){
                        maxPoints = points;
                    }
                    /*if depth is 0 we don't want to return the max points attainable but
                      rather the position that gets us that max point: */
                    if(depth == 0 && maxPoints == points){  
                        optimalMovePos = posIndex;
                    }
                }
            }
            if(depth == 0){
                return int(optimalMovePos);
            }
            return maxPoints;
        }
    }
 
 
    /* dev: Return evaluation of Torus for heuristic minimax
       return: points of a given torus (positive if good for contract) */
    function evaluateTorus(uint256 possibleTorus) public pure returns (int){
        uint256[6][6] memory horizontalGroups = [ [uint256(0x3), 0xC, 0x30, 0xC0, 0x300, 0xC00],
                                        [uint256(0x3000), 0xC000, 0x30000, 0xC0000, 0x300000, 0xC00000],
                                        [uint256(0x3000000), 0xC000000, 0x30000000, 0xC0000000, 0x300000000, 0xC00000000],
                                        [uint256(0x3000000000), 0xC000000000, 0x30000000000, 0xC0000000000, 0x300000000000, 0xC00000000000],
                                        [uint256(0x3000000000000), 0xC000000000000, 0x30000000000000, 0xC0000000000000, 0x300000000000000, 0xC00000000000000],
                                        [uint256(0x3000000000000000), 0xC000000000000000, 0x30000000000000000, 0xC0000000000000000, 0x300000000000000000, 0xC00000000000000000] ];
 
        uint256[6][6] memory verticalGroups = [ [uint256(0x3), 0x3000, 0x3000000, 0x3000000000, 0x3000000000000, 0x3000000000000000],
                                      [uint256(0xC), 0xC000, 0xC000000, 0xC000000000, 0xC000000000000, 0xC000000000000000],
                                      [uint256(0x30), 0x30000, 0x30000000, 0x30000000000, 0x30000000000000, 0x30000000000000000],
                                      [uint256(0xC0), 0xC0000, 0xC0000000, 0xC0000000000, 0xC0000000000000, 0xC0000000000000000],
                                      [uint256(0x300), 0x300000, 0x300000000, 0x300000000000, 0x300000000000000, 0x300000000000000000],
                                      [uint256(0xC00), 0xC00000, 0xC00000000, 0xC00000000000, 0xC00000000000000, 0xC00000000000000000] ];
 
        uint256[6][6] memory rightDownGroups = [ [uint256(0x3), 0xC00000, 0x300000000, 0xC0000000000, 0x30000000000000, 0xC000000000000000],
                                       [uint256(0xC), 0x3000, 0xC00000000, 0x300000000000, 0xC0000000000000, 0x30000000000000000],
                                       [uint256(0x30), 0xC000, 0x3000000, 0xC00000000000, 0x300000000000000, 0xC0000000000000000],
                                       [uint256(0xC0), 0x30000, 0xC000000, 0x3000000000, 0xC00000000000000, 0x300000000000000000],
                                       [uint256(0x300), 0xC0000, 0x30000000, 0xC000000000, 0x3000000000000, 0xC00000000000000000],
                                       [uint256(0xC00), 0x300000, 0xC0000000, 0x30000000000, 0xC000000000000, 0x3000000000000000] ];
                               
        uint256[6][6] memory leftDownGroups = [ [uint256(0x3), 0xC000, 0x30000000, 0xC0000000000, 0x300000000000000, 0xC00000000000000000],
                                      [uint256(0xC), 0x30000, 0xC0000000, 0x300000000000, 0xC00000000000000, 0x3000000000000000],
                                      [uint256(0x30), 0xC0000, 0x300000000, 0xC00000000000, 0x3000000000000, 0xC000000000000000],
                                      [uint256(0xC0), 0x300000, 0xC00000000, 0x3000000000, 0xC000000000000, 0x30000000000000000],
                                      [uint256(0x300), 0xC00000, 0x3000000, 0xC000000000, 0x30000000000000, 0xC0000000000000000],
                                      [uint256(0xC00), 0x3000, 0xC000000, 0x30000000000, 0xC0000000000000, 0x300000000000000000] ];
        int[6] memory points = [int(0), 1, 4, 9, 16, type(int).max];    //amount of points you get/lose for 0 markers, 1 marker,..., 5 markers (we never get 6 markers b/c stopped at 5)
        int totalPoints = 0;
        for(uint256 i = 0; i < 6; i++){
            uint OCount = 0;    //user marker
            uint XCount = 0;    //contract marker
            for(uint256 j = 0; j < 6; j++){
                uint256 markerOnPiece = (possibleTorus & horizontalGroups[i][j]) % 3;  
                if(markerOnPiece == 0){  //piece is empty
                    continue;
                }
                if(markerOnPiece == 1){  //piece contains user marker
                    OCount++;
                }
                if(markerOnPiece == 2){  //piece contains contract marker
                    XCount++;
                }
            }
            if(OCount == 5){
                return type(int).min;       //never pick (from contract's perspective)
            }
            else if(XCount == 5){
                return type(int).max;       //pick this over anything (from contract's perspective)
            }
            else if((OCount >= 2 && XCount >= 2) || (OCount == XCount)){
                continue;
            }
            else if(OCount == 0){
                totalPoints += (int(6-XCount)*points[XCount] + int(XCount)*points[XCount-1]);
            }
            else if(XCount == 0){
                totalPoints -= (int(6-OCount)*points[OCount] + int(OCount)*points[OCount-1]);
            }
            else if(OCount == 1){
                totalPoints = totalPoints + points[XCount];
            }
            else if(XCount == 1){
                totalPoints -= points[OCount];
            }
        }
 
        for(uint i = 0; i < 6; i++){
            uint OCount = 0;    //user marker
            uint XCount = 0;    //contract marker
            for(uint j = 0; j < 6; j++){
                uint markerOnPiece = (possibleTorus & verticalGroups[i][j]) % 3;  
                if(markerOnPiece == 0){  //piece is empty
                    continue;
                }
                if(markerOnPiece == 1){  //piece contains user marker
                    OCount++;
                }
                if(markerOnPiece == 2){  //piece contains contract marker
                    XCount++;
                }
            }
            if(OCount == 5){
                return type(int).min;       //never pick (from contract's perspective)
            }
            else if(XCount == 5){
                return type(int).max;       //pick this over anything (from contract's perspective)
            }
            else if((OCount >= 2 && XCount >= 2) || (OCount == XCount)){
                continue;
            }
            else if(OCount == 0){
                totalPoints += (int(6-XCount)*points[XCount] + int(XCount)*points[XCount-1]);
            }
            else if(XCount == 0){
                totalPoints -= (int(6-OCount)*points[OCount] + int(OCount)*points[OCount-1]);
            }
            else if(OCount == 1){
                totalPoints += points[XCount];
            }
            else if(XCount == 1){
                totalPoints -= points[OCount];
            }
        }
 
        for(uint i = 0; i < 6; i++){
            uint OCount = 0;    //user marker
            uint XCount = 0;    //contract marker
            for(uint j = 0; j < 6; j++){
                uint markerOnPiece = (possibleTorus & rightDownGroups[i][j]) % 3;  
                if(markerOnPiece == 0){  //piece is empty
                    continue;
                }
                if(markerOnPiece == 1){  //piece contains user marker
                    OCount++;
                }
                if(markerOnPiece == 2){  //piece contains contract marker
                    XCount++;
                }
            }
            if(OCount == 5){
                return type(int).min;       //never pick (from contract's perspective)
            }
            else if(XCount == 5){
                return type(int).max;       //pick this over anything (from contract's perspective)
            }
            else if((OCount >= 2 && XCount >= 2) || (OCount == XCount)){
                continue;
            }
            else if(OCount == 0){
                totalPoints += (int(6-XCount)*points[XCount] + int(XCount)*points[XCount-1]);
            }
            else if(XCount == 0){
                totalPoints -= (int(6-OCount)*points[OCount] + int(OCount)*points[OCount-1]);
            }
            else if(OCount == 1){
                totalPoints += points[XCount];
            }
            else if(XCount == 1){
                totalPoints -= points[OCount];
            }
        }
 
        for(uint i = 0; i < 6; i++){
            uint OCount = 0;    //user marker
            uint XCount = 0;    //contract marker
            for(uint j = 0; j < 6; j++){
                uint markerOnPiece = (possibleTorus & leftDownGroups[i][j]) % 3;  
                if(markerOnPiece == 0){  //piece is empty
                    continue;
                }
                if(markerOnPiece == 1){  //piece contains user marker
                    OCount++;
                }
                if(markerOnPiece == 2){  //piece contains contract marker
                    XCount++;
                }
            }
            if(OCount == 5){
                return type(int).min;       //never pick (from contract's perspective)
            }
            else if(XCount == 5){
                return type(int).max;       //pick this over anything (from contract's perspective)
            }
            else if((OCount >= 2 && XCount >= 2) || (OCount == XCount)){
                continue;
            }
            else if(OCount == 0){
                totalPoints += (int(6-XCount)*points[XCount] + int(XCount)*points[XCount-1]);
            }
            else if(XCount == 0){
                totalPoints -= (int(6-OCount)*points[OCount] + int(OCount)*points[OCount-1]);
            }
            else if(OCount == 1){
                totalPoints += points[XCount];
            }
            else if(XCount == 1){
                totalPoints -= points[OCount];
            }
        }
        return totalPoints;
    }
 
 
    /* dev: Checks if contract or user (depending on isContract) has won. Examines possibleTorus around the index of the most recent move because that is all that matters.
       This function enforces the logic of the torus board so we don't need a separate contract for the board logic (engine and board logic is combined).    
       param: mostRecentMove is the index of the new O (if isContract is false) or X (if isContract is true), only need to check if this new move causes a win
       Uses structs Coutns and Markers because too many local variables inside the function would cause stack to run out of depth */
    struct Counts {
        uint hCount;
        uint vCount;
        uint rdCount;
        uint ldCount;
    }
 
    struct Markers {
        uint256 hMarker;
        uint256 vMarker;
        uint256 rdMarker;
        uint256 ldMarker;
    }
 
    function checkWin(uint possibleTorus, uint mostRecentMove, bool isContract) public pure returns (bool) {    // around $2.95
        // the group sums are the sums of each group put in an array
        uint256[6][6] memory horizontalGroups = [ [uint256(0x3), 0xC, 0x30, 0xC0, 0x300, 0xC00],
                                        [uint256(0x3000), 0xC000, 0x30000, 0xC0000, 0x300000, 0xC00000],
                                        [uint256(0x3000000), 0xC000000, 0x30000000, 0xC0000000, 0x300000000, 0xC00000000],
                                        [uint256(0x3000000000), 0xC000000000, 0x30000000000, 0xC0000000000, 0x300000000000, 0xC00000000000],
                                        [uint256(0x3000000000000), 0xC000000000000, 0x30000000000000, 0xC0000000000000, 0x300000000000000, 0xC00000000000000],
                                        [uint256(0x3000000000000000), 0xC000000000000000, 0x30000000000000000, 0xC0000000000000000, 0x300000000000000000, 0xC00000000000000000] ];
        uint256[6][6] memory verticalGroups = [ [uint256(0x3), 0x3000, 0x3000000, 0x3000000000, 0x3000000000000, 0x3000000000000000],
                                      [uint256(0xC), 0xC000, 0xC000000, 0xC000000000, 0xC000000000000, 0xC000000000000000],
                                      [uint256(0x30), 0x30000, 0x30000000, 0x30000000000, 0x30000000000000, 0x30000000000000000],
                                      [uint256(0xC0), 0xC0000, 0xC0000000, 0xC0000000000, 0xC0000000000000, 0xC0000000000000000],
                                      [uint256(0x300), 0x300000, 0x300000000, 0x300000000000, 0x300000000000000, 0x300000000000000000],
                                      [uint256(0xC00), 0xC00000, 0xC00000000, 0xC00000000000, 0xC00000000000000, 0xC00000000000000000] ];
 
        uint256[6][6] memory rightDownGroups = [ [uint256(0x3), 0xC00000, 0x300000000, 0xC0000000000, 0x30000000000000, 0xC000000000000000],
                                       [uint256(0xC), 0x3000, 0xC00000000, 0x300000000000, 0xC0000000000000, 0x30000000000000000],
                                       [uint256(0x30), 0xC000, 0x3000000, 0xC00000000000, 0x300000000000000, 0xC0000000000000000],
                                       [uint256(0xC0), 0x30000, 0xC000000, 0x3000000000, 0xC00000000000000, 0x300000000000000000],
                                       [uint256(0x300), 0xC0000, 0x30000000, 0xC000000000, 0x3000000000000, 0xC00000000000000000],
                                       [uint256(0xC00), 0x300000, 0xC0000000, 0x30000000000, 0xC000000000000, 0x3000000000000000] ];
                               
        uint256[6][6] memory leftDownGroups = [ [uint256(0x3), 0xC000, 0x30000000, 0xC0000000000, 0x300000000000000, 0xC00000000000000000],
                                      [uint256(0xC), 0x30000, 0xC0000000, 0x300000000000, 0xC00000000000000, 0x3000000000000000],
                                      [uint256(0x30), 0xC0000, 0x300000000, 0xC00000000000, 0x3000000000000, 0xC000000000000000],
                                      [uint256(0xC0), 0x300000, 0xC00000000, 0x3000000000, 0xC000000000000, 0x30000000000000000],
                                      [uint256(0x300), 0xC00000, 0x3000000, 0xC000000000, 0x30000000000000, 0xC0000000000000000],
                                      [uint256(0xC00), 0x3000, 0xC000000, 0x30000000000, 0xC0000000000000, 0x300000000000000000] ];
 
       
        if(isContract == false){   //checking if user wins, if this returns true user has won and if it returns false game goes on
            Counts memory oCounts = Counts(0, 0, 0, 0);
            Markers memory markers = Markers(0, 0, 0, 0);
            for(uint i = 0; i < 6; i++){
                markers.hMarker = (possibleTorus & horizontalGroups[mostRecentMove / 6][i]) % 3;
                markers.vMarker = (possibleTorus & verticalGroups[mostRecentMove % 6][i]) % 3;
                markers.rdMarker = (possibleTorus & rightDownGroups[(mostRecentMove + (mostRecentMove / 6)) % 6][i]) % 3;
                markers.ldMarker = (possibleTorus & leftDownGroups[(mostRecentMove - (mostRecentMove / 6)) % 6][i]) % 3;
                if(markers.hMarker == 1){
                    oCounts.hCount++;
                }
                if(markers.vMarker == 1){
                    oCounts.vCount++;
                }
                if(markers.rdMarker == 1){
                    oCounts.rdCount++;
                }
                if(markers.ldMarker == 1){
                    oCounts.ldCount++;
                }
            }
            if(oCounts.hCount >= 5 || oCounts.vCount >= 5 || oCounts.rdCount >= 5 || oCounts.ldCount >= 5){
                return true;
            }
            return false;
        }
        else{                 //checking if contract wins, if this returns true contract has won and if it returns false game goes on
            Counts memory xCounts = Counts(0, 0, 0, 0);
            Markers memory markers = Markers(0, 0, 0, 0);
            for(uint i = 0; i < 6; i++){
                markers.hMarker = (possibleTorus & horizontalGroups[mostRecentMove / 6][i]) % 3;
                markers.vMarker = (possibleTorus & verticalGroups[mostRecentMove % 6][i]) % 3;
                markers.rdMarker = (possibleTorus & rightDownGroups[(mostRecentMove + (mostRecentMove / 6)) % 6][i]) % 3;
                markers.ldMarker = (possibleTorus & leftDownGroups[(mostRecentMove - (mostRecentMove / 6)) % 6][i]) % 3;
                if(markers.hMarker == 2){
                    xCounts.hCount++;
                }
                if(markers.vMarker == 2){
                    xCounts.vCount++;
                }
                if(markers.rdMarker == 2){
                    xCounts.rdCount++;
                }
                if(markers.ldMarker == 2){
                    xCounts.ldCount++;
                }
            }
            if(xCounts.hCount >= 5 || xCounts.vCount >= 5 || xCounts.rdCount >= 5 || xCounts.ldCount >= 5){
                return true;
            }
            return false;
        }
    }
 
 
    /* dev: Changes to torusState variable to reflect the most recent moves made
       param updates user marker at userPieceIndex and contract marker at contractPieceIndex */
    function updateState(uint userPieceIndex, uint contractPieceIndex) public {   //update both user move and contract move at once to change state as less often as possible
        uint updates = (1 << userPieceIndex * 2) | (1 << (contractPieceIndex*2+1));
        torusState |= updates;
    }
 
 
    /* dev: initially called from frontend to start everything else
       param checks if user's move is valid, computes optimal move for contract, and calls updateState to reflect the user's move and contract's response move */
    function userMove(uint userPieceIndex) public returns (int) {
        require(torusState & (3 << userPieceIndex*2) == 0);   //check if piece at userPieceIndex is empty aka 00
        uint torusStateCopy = torusState;
        torusStateCopy |= (1 << userPieceIndex*2);
        if(checkWin(torusStateCopy, userPieceIndex, false) == true) {
            //game ends, display "User wins" on frontend
            return -1;
        }
        uint256 contractPieceIndex = uint256( searchForMove(torusStateCopy, 0, true) );
        updateState(userPieceIndex, contractPieceIndex);
        if(checkWin(torusState, contractPieceIndex, false) == true) {
            //game ends, display "Contract wins" on frontend
            return -1;
        }
        return 314;
    }
 
 
    /* dev: simply allows frontend to access the torusState so it can update the THREE.js object appropriately  */
    function getTorusState() public view returns (uint) {
        return torusState;
    }
}