# Thread: Looking for appropriate container

1. It sounds like I basically evaluate all moves at the current depth (non-recursively), sort them in descending order and then recursively call to evaluate the highest point move, going downwards.

Thanks for the mathematical formula. I needed one of those to calculate approximately how many nodes there would be. Now let's see if I can some better statistics in place.

2. Originally Posted by Elysia
It sounds like I basically evaluate all moves at the current depth (non-recursively), sort them in descending order and then recursively call to evaluate the highest point move, going downwards.
Exactly, except you do this iteratively. First you search to depth 1, then to depth 2, then to depth 3, etc. As long as you feel like it. (In reality, the search is more stable if you search by complete ply, so depth 1, then depth 3, then depth 5, etc) As this happens, the cache is being filled with better and better estimates, leading to better and better move orderings, leading to bigger cutoffs, leading to deeper search in a given time.

It seems awful to perform a sort at each recursion, but it's actually a huge win. There are all kinds of fun optimizations possible. The basic thing, though, is that none of the individual pieces will give you that much on their own. It's the combination of iterative deepening, transposition table, alpha-beta, and a good heuristic all working synergistically.

It's important to CLEAR THE CACHE after you actually make a move. After a move is actually made, it's like a brand new day and you should not rely on estimates from the previous starting point.

3. Well, I'll try implementing a little data to see how many nodes (compared to total) is pruned, then change the algorithm and see what happens.

EDIT:
OK, so what is the approximate number of nodes in a game tree for a 5x5 board 5 in a row?
Is it 5 ^25?

4. Originally Posted by Elysia
OK, so what is the approximate number of nodes in a game tree for a 5x5 board 5 in a row?
Is it 5 ^25?
On the first move, there are 25 possibilities for a move, so the branching factor is 25. After that move, there are 24 possibilities left, so branching factor of 24... Etc. The total number of possible games is 25! assuming that all sequences of moves are possible. In reality, not all sequences are possible because typically somebody will win before the board is filled. But the key thing is that at move number N (zero-indexed), there are 25-N moves remaining on the board. If I understand the game correctly. Naively, I would guess that the total number of positions at the ultimate depth is O((D^2)!), where D is the board dimension (5 in your case), where the exact multiplier is irrelevant.

5. I just cannot seem to get the statistics right:

Progress: 100%
Cache hits: 5 366 420
Cache misses: 2 652 272
Cache hit/miss ratio: 2.02
Cache size: 2 652 272 entries
Total nodes pruned: 214 541 295 milliard (1025395% of total)
Total cache skipped nodes: 225 792 344 milliard (1079169% of total)
Total win skipped nodes: 6 488 milliard (31.0% of total)
Total nodes examined: 2 652 272
Total % skipped nodes: 2104595%
Total nodes: 20 922 milliard
Current memory usage: 78 MB
Running time so far: 10s
Took 11s to calculate computer move.

Total % skipped nodes 2 104 595%? That's not possible.
This was a 4x4 board.

I can buy the N! calculation. It seems to make sense.
Similarly, if we cut off at level N, then there must be (Maximum depth - N - 1)! nodes cut off, right?
Yet, this does not seem to work properly. I don't know why, unless the formulas are incorrect.

Code:
```    template<int NDim1, int NDim2, typename BoardData_t>
int GetBestMove(SMinMaxSharedData<NDim1, NDim2>& SharedData, SMinMaxVolatileData<NDim1, NDim2, BoardData_t>& VolatileData, const Player& CurrentPlayer,
uint Level, int Alpha, int Beta, unsigned int StartPos, unsigned int EndPos
#ifdef DEBUG_OUTPUT
, SDebugData& DebugData, double CurrentProgress, double PercentageWorth
#endif
)
{

#        ifdef _DEBUG
std::string DebugBoard;
#        endif

#        ifdef _DEBUG
{
std::stringstream stream;
stream << VolatileData.Board;
DebugBoard = stream.str();
}
#        endif

bool IsComputer = CurrentPlayer == SharedData.Computer;
bool IsHuman = CurrentPlayer == SharedData.Human;
assert( (IsComputer && !IsHuman) || (IsHuman && !IsComputer) );

if (Level == SharedData.MaxDepth || VolatileData.Board.IsDraw())
{
assert(Level == NDim1 * NDim2);
return 0;
}

if ( VolatileData.Board.CheckForWinner(CurrentPlayer) )
{
#            ifdef DEBUG_OUTPUT
DebugData.WinSkippedNodes += Faculty(NDim1 * NDim2 - Level - 1);
#            endif
return IsComputer ? 1000 : -1000;
}

typedef const Board<NDim1, NDim2> Board_t;
int BestScoreSoFar = IsComputer ? std::numeric_limits<int>::min() : std::numeric_limits<int>::max();
const int& _Alpha = IsComputer ? BestScoreSoFar : Alpha;
const int& _Beta = IsComputer ? Beta : BestScoreSoFar;
Coordinates BestMoveSoFar(-1, -1);
#        ifdef DEBUG_OUTPUT
double TotalSize = Board_t::Width * Board_t::Height; \
double LoopPrcUnit = PercentageWorth / TotalSize;
#        endif

for (CCoordinateSystem xy(Board_t::Width - 1, 0, Board_t::Height - 1, 0, StartPos); xy.GetPosition() <= EndPos; ++xy)
{
#            ifdef DEBUG_OUTPUT
double NumIterations = NDim1 * xy.GetCoordinates().GetX() + xy.GetCoordinates().GetY();
DebugData.Progress = CurrentProgress + NumIterations * LoopPrcUnit;
DebugData.ExaminedNodes++;
#            endif

if (!VolatileData.Board.IsSquareEmpty( xy.GetCoordinates() ))
continue;

VolatileData.Board.SetSquare(xy.GetCoordinates(), CurrentPlayer);
#            ifdef _DEBUG
{
std::stringstream stream;
stream << VolatileData.Board;
DebugBoard = stream.str();
}
#            endif

int Score = 0;
bool InMap = false;
VolatileData.Board.GetFriendlyMapInstance(VolatileData.BoardData);

auto it = VolatileData.ScoreLookupMap.find(VolatileData.BoardData);
InMap = (it != VolatileData.ScoreLookupMap.end());

if (InMap)
{
Score = it->second;
#                ifdef DEBUG_OUTPUT
DebugData.CacheHits++;
DebugData.CacheSkippedNodes += Faculty(NDim1 * NDim2 - Level - 1);
#                endif
}

if (!InMap)
{
#                ifdef DEBUG_OUTPUT
DebugData.CacheMisses++;
#                endif

Score = detail::FindNumSurroundingData(VolatileData.Board, CurrentPlayer, xy.GetCoordinates()) * (IsComputer ? 1 : -1);
const Player& OppositePlayer = IsComputer ? SharedData.Human : SharedData.Computer;

if ( VolatileData.Board.CheckForWinner(CurrentPlayer) )
{
Score += IsComputer ? 1000 : -1000;
#                    ifdef DEBUG_OUTPUT
DebugData.WinSkippedNodes += Faculty(NDim1 * NDim2 - Level - 1);
#                    endif
}
else
#                    ifdef DEBUG_OUTPUT
Score += GetBestMove(SharedData, VolatileData, OppositePlayer, Level + 1, _Alpha, _Beta, 0, xy.GetMaxPoint(), DebugData, DebugData.Progress, LoopPrcUnit / TotalSize);
#                    else
Score += GetBestMove(SharedData, VolatileData, OppositePlayer, Level + 1, _Alpha, _Beta, 0, xy.GetMaxPoint());
#                    endif

if (Level <= SharedData.MaxCacheLevelDepth)
{
bool IsPlaceInCache = Stuff::Process::Memory::GetUsage() < SharedData.MaxMemoryUsage;
if (IsPlaceInCache)
{
VolatileData.Board.GetFriendlyMapInstance(VolatileData.BoardData);
VolatileData.ScoreLookupMap[VolatileData.BoardData] = Score;
#                        ifdef DEBUG_OUTPUT
DebugData.CacheSize++;
#                        endif

}
}
}

VolatileData.Board.UndoLastMove();

if ((IsComputer && Score > BestScoreSoFar) || (IsHuman && Score < BestScoreSoFar))
{
BestScoreSoFar = Score;
BestMoveSoFar = xy.GetCoordinates();
}

if ( (IsHuman && _Beta <= _Alpha) || (IsComputer && _Alpha >= _Beta) )
{
#                ifdef DEBUG_OUTPUT
DebugData.PrunedNodes += Faculty(NDim1 * NDim2 - Level - 1);
#                endif

goto ExitLoop;
}
}

ExitLoop:
assert(BestMoveSoFar != Coordinates(-1, -1));
VolatileData.OutCoord = BestMoveSoFar;

return BestScoreSoFar;
}```

6. For anyone who still cares...
I found some time to work on this today, and I believe I finally got the numbers to work. It's not N! as one might think. It's more complex than that. I don't have a mathematical formula, but I do have an algorithm that works.

Bur besides that, I also tried ordering the moves in order to get maximum alpha-beta pruning. Unfortunately, empirical evidence shows that is worse off than not ordering them!
Without move ordering, I get 6 928 pruned nodes on a 3x3 board.
And with ordering, I only get 1 940 pruned nodes.

For anyone who's willing to take a look into this, here is what I've gotten so far:
Code:
```    template<int NDim1, int NDim2, typename BoardData_t>
int GetBestMove(SMinMaxSharedData<NDim1, NDim2>& SharedData, SMinMaxVolatileData<NDim1, NDim2, BoardData_t>& VolatileData, const Player& CurrentPlayer,
uint Level, int Alpha, int Beta/*, unsigned int StartPos, unsigned int EndPos*/
#ifdef DEBUG_OUTPUT
, SDebugData& DebugData, double CurrentProgress, double PercentageWorth
#endif
)
{
X_t x(0);
Y_t y(0);
int BestScoreSoFar;
typedef const Board<NDim1, NDim2> Board_t;
SAlgoData<NDim1, NDim2, BoardData_t> Data = Initialize<NDim1, NDim2, BoardData_t>(CurrentPlayer, VolatileData, SharedData, Level, Alpha, Beta, PercentageWorth, DebugData, x, y, BestScoreSoFar);

typedef std::pair<int, Coordinates> Score_t;
struct greater
{
bool operator () (const Score_t& score1, const Score_t& score2) { return score1.first > score2.first; }
};
typedef std::multiset<Score_t, greater> Set_t;
Set_t Scores;

UpdateDebugBoard(Data);

if ( HandleDraw(Data) )
return 0;
if ( HandleMaxDepth(Data) )
return 0;
if ( HandlePlayerHasWon(Data) )
return GetPlayerWinPts(Data);

for (x = X_t(0); x < Board_t::Width; x++)
{
for (y = Y_t(0); y < Board_t::Height; y++)
{
if (!VolatileData.Board.IsSquareEmpty( Coordinates(x, y) ))
continue;
Scores.insert(
std::make_pair
(
detail::FindNumSurroundingData(Data.VolatileData.Board, Data.CurrentPlayer, Coordinates(x, y)) * (Data.IsComputer ? 1 : -1),
Coordinates(x, y)
) );
}
}

auto score_it = Scores.begin();
for (unsigned int i = 0; score_it != Scores.end(); ++score_it, i++)
{
#ifdef DEBUG_OUTPUT
double NumIterations = (double)i;
DebugData.Progress = CurrentProgress + NumIterations * Data.LoopPrcUnit;
UpdateDebugBoard(Data);

Data.DebugData.ExaminedNodes++;
#endif

VolatileData.Board.SetSquare(score_it->second, CurrentPlayer);
UpdateDebugBoard(Data);
Data.MovesLeft--;
Data.FreeSquares--;

int Score = score_it->first;
typename SCORE_LOOKUP_MAP_T::const_iterator it;
bool InMap = HandleIsInMap(Data, it);
Score += GetScore(Data, InMap, it);
SaveScoreInMap(Data, InMap, Score);

VolatileData.Board.UndoLastMove();
Data.FreeSquares++;

SaveBestScoreSoFar(Data, Score, score_it->second);
if (HandlePruning(Data))
break;
}

VolatileData.OutCoord = Data.BestMoveSoFar;
#ifdef SHOW_PREDICTED_MOVES
VolatileData.PredictedMoves[Level - 1] = BestMoveSoFar;
#endif
return Data.BestScoreSoFar;
}```
Perhaps I need to improve the algorithm for calculating how many points it gets?