How to efficiently store a large Java map?

Question

I brutally force one game, and I need to store data for all positions and results. Probably the data will be hundreds of Gb in size. I considered SQL, but I am afraid that searching in a tight loop may lead to performance degradation. The program will sort through possible positions and return the winning move, if known, return the longest losing sequence if all the moves are known to lose and check the 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 crudely forcing all viable moves in Java. The upper limit of positions is about 100 billion. Most of them are not believable (i.e. more pieces than were present at the beginning of the game). About 10 billion is a reasonable estimate. Each Map<Long, Long[]> position displays the Long positionID in Long whiteToMove and Long blackToMove . A positive value indicates that the position is winning, and a move should be selected that leads to the position stored in the value. A negative value of -n means that the position is lost by no more than n .

The search itself will have this recursion:

 //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 can watch the Chronicle . This is a highly optimized key storage and should be appropriate for your purpose.

Or you can write the repository yourself, but you will still be doing something like a map and map file under the hood.