// 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; } }
0.7.1