How to efficiently store a large Java map?

Question

I am brute-forcing one game and I need to store data for all positions and outcomes. Data will likely be hundreds of Gb in size. I considered SQL, but I am afraid that lookups in a tight loop might kill performance. Program will iterate over possible positions and return winning move if it is known, return longest losing sequence if all moves are known to lose and check outcome for unknown moves.

What is the best way to store a large Map<Long,Long[]> positionIdToBestMoves? I am considering SQL or data serialization.

I want to solve tiny checkers by brute-forcing all viable moves in Java. The upper limit of positions is around 100 billions. Most of them are not plausible (i.e. more pieces than were present in the beginning of the game). Some 10 Billions is a reasonable estimate. Each Map<Long, Long[]> position maps Long positionID to Long whiteToMove and Long blackToMove. Positive value indicate that position is winning and a move that leads to position stored in value should be chosen. Negative value -n means position is losing in at most n moves.

Search itself would have a recursion like this:

//this is a stub

private Map<Long, Long[]> boardBook =...

//assuming that all winning positions are known
public Long nextMove(Long currentPos, int whiteOrBlack){
Set<Long> validMoves = calculateValidMoves(currentPos, whiteOrBlack);
boolean hasWinner = checkIfValidMoveIsKnownToWin(validMoves, whiteOrBlack);

if(hasWinner){  //there is a winning move - play it
    Long winningMove = getWinningMove(validMoves, whiteOrBlack);
    boardBook.get(currentPos)[whiteOrBlack] = winningMove ;    
    return winningMove ;
    }
boolean areAllPositionsKnown = checkIfAllPositionsKnown(validMoves, whiteOrBlack);
if(areAllPositionsKnown){  //all moves are losing.. choose longest struggle
    Long longestSequenceToDefeat = findPositionToLongestSequenceToDefeat(validMoves, whiteOrBlack);
    int numberOfStepsTodefeat = boardBook.get(longestSequenceToDefeat)[whiteOrBlack];
    boardBook.get(currentPos)[whiteOrBlack] = longestSequenceToDefeat ;
    return longestSequenceToDefeat;
    }

Set<Long> movesToCheck = getUntestedMoves(validMoves, whiteOrBlack);
Long longeststruggle;
int maxNumberOfMovesToDefeat =-1;
for(Long moveTocheck : movesToCheck){
    Long result = nextMove(moveToCheck, whiteOrBlack);
    if(result>0){ //just discovered a winning move
            boardBook.get(currentPos)[whiteOrBlack] = winningMove ;    
            return winningMove ;
        }else {
            int numOfMovesToDefeat = -1*boardBook.get(moveTocheck)[whiteOrBlack];
            if( numOfMovesToDefeat >maxNumberOfMovesToDefeat ){
                 maxNumberOfMovesToDefeat =numOfMovesToDefeat ; 
                 longeststruggle = moveTocheck;
                  }
         }
      }
boardBook.get(currentPos)[whiteOrBlack] = -1*maxNumberOfMovesToDefeat;
return  longeststruggle;
}

Answer 1

You may want to look at Chronicle. It's highly optimized key-value storage and it should fit for your purpose.

Or you can write storage by yourself, but you still will end up doing something like map and memory mapped file under the hood.