Code:
typedef unsigned int uint;
#define SCORE_LOOKUP_MAP_T std::map<typename ::Board<NDim1, NDim2>::FriendlyMapInstance_t, int>
#pragma warning(push)
#pragma warning(disable: 4512 4610 4510)
template<uint NDim1, uint NDim2>
struct SMinMaxSharedData
{
const Player& Computer;
const Player& Human;
const uint MaxDepth;
const uint MaxMemoryUsage;
const uint MaxCacheLevelDepth;
const uint WinPoints;
const uint AdjacentSquarePoints;
const uint BlockOpponentSquarePoints;
};
template<uint NDim1, uint NDim2, typename BoardData_t>
struct SMinMaxVolatileData
{
Board<NDim1, NDim2>& Board;
SCORE_LOOKUP_MAP_T& ScoreLookupMap;
Coordinates OutCoord;
BoardData_t BoardData;
};
#pragma warning(pop)
template<uint NDim1, uint NDim2>
void GetBestMove(const Board<NDim1, NDim2>& board, Player& Player1, Player& Player2, int PlayerToGetMove, Coordinates& coord, uint MaxDepth, uint MaxCacheItems, uint MaxCacheLevelDepth,
uint WinPoints, uint AdjacentSquarePoints, uint BlockOpponentSquarePoints
)
{
//static_assert(NDim1 <= 4 && NDim2 <= 4, "The board is too big. It would require a computer from outer space to calculate the AI for this board size. Select 4x4 or lower.");
typedef Board<NDim1, NDim2> board_t;
Player* Players[2];
switch (PlayerToGetMove)
{
case 1:
Players[0] = &Player1;
Players[1] = &Player2;
break;
case 2:
Players[0] = &Player2;
Players[1] = &Player1;
break;
default: assert(false);
}
#ifdef USE_STATIC_MAP
#define STATIC static
#else
#define STATIC
#endif
SCORE_LOOKUP_MAP_T ScoreLookupMap1;
SCORE_LOOKUP_MAP_T ScoreLookupMap2;
#undef STATIC
SMinMaxSharedData<NDim1, NDim2> SharedData = { *Players[0], *Players[1], MaxDepth, MaxCacheItems, MaxCacheLevelDepth, WinPoints, AdjacentSquarePoints,
BlockOpponentSquarePoints };
Board<NDim1, NDim2> Board1(board);
Board<NDim1, NDim2> Board2(board);
SMinMaxVolatileData<NDim1, NDim2, typename Board<NDim1, NDim2>::FriendlyMapInstance_t> VolatileData1 = { Board1, ScoreLookupMap1 };
SMinMaxVolatileData<NDim1, NDim2, typename Board<NDim1, NDim2>::FriendlyMapInstance_t> VolatileData2 = { Board2, ScoreLookupMap2 };
int Score1 = std::numeric_limits<int>::min(), Score2 = std::numeric_limits<int>::min();
bool Break = false;
unsigned int Range1End;
Range1End = NDim1 * NDim2 - 1;
boost::thread Thread1([&]() { Score1 = GetBestMove(SharedData, VolatileData1, *Players[0], 1, std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 0, Range1End, 0, 100); });
boost::thread MergingThread([&]()
{
do
{
Progress = VolatileData1.Progress + VolatileData2.Progress;
CacheHits = VolatileData1.CacheHits + VolatileData2.CacheHits;
CacheMisses = VolatileData1.CacheMisses + VolatileData2.CacheMisses;
CacheSize = VolatileData1.CacheSize + VolatileData2.CacheSize;
PruneHits = VolatileData1.PruneHits + VolatileData2.PruneHits;
TotalNodesExamined = VolatileData1.TotalNodesExamined + VolatileData2.TotalNodesExamined;
Sleep(500);
}
while (!Break);
});
Thread1.join();
Break = true;
MergingThread.join();
if (Score1 > Score2)
coord = VolatileData1.OutCoord;
else
coord = VolatileData2.OutCoord;
}
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
)
{
bool IsComputer = CurrentPlayer == SharedData.Computer;
bool IsHuman = CurrentPlayer == SharedData.Human;
assert( (IsComputer && !IsHuman) || (IsHuman && !IsComputer) );
if (Level == SharedData.MaxDepth || VolatileData.Board.IsDraw())
return 0;
if ( VolatileData.Board.CheckForWinner(CurrentPlayer) )
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);
for (CCoordinateSystem xy(Board_t::Width - 1, 0, Board_t::Height - 1, 0, StartPos); xy.GetPosition() <= EndPos; ++xy)
{
if (!VolatileData.Board.IsSquareEmpty( xy.GetCoordinates() ))
continue;
VolatileData.Board.SetSquare(xy.GetCoordinates(), CurrentPlayer);
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;
}
if (!InMap)
{
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;
else
Score += GetBestMove(SharedData, VolatileData, OppositePlayer, Level + 1, _Alpha, _Beta, 0, xy.GetMaxPoint());
if (Level <= SharedData.MaxCacheLevelDepth)
{
bool IsPlaceInCache = Stuff::Process::Memory::GetUsage() < SharedData.MaxMemoryUsage;
if (IsPlaceInCache)
{
VolatileData.Board.GetFriendlyMapInstance(VolatileData.BoardData);
VolatileData.ScoreLookupMap[VolatileData.BoardData] = Score;
}
}
}
VolatileData.Board.UndoLastMove();
if ((IsComputer && Score > BestScoreSoFar) || (IsHuman && Score < BestScoreSoFar))
{
BestScoreSoFar = Score;
BestMoveSoFar = xy.GetCoordinates();
}
if ( (IsHuman && _Beta <= _Alpha) || (IsComputer && _Alpha >= _Beta) )
{
goto ExitLoop;
}
}
ExitLoop:
assert(BestMoveSoFar != Coordinates(-1, -1));
VolatileData.OutCoord = BestMoveSoFar;
return BestScoreSoFar;
}
};
void GetFriendlyMapInstance(FriendlyMapInstance_t& Data)
{
Data ^= Data;
for (uint x = 0; x < Width; x++)
{
for (uint y = 0; y < Height; y++)
{
auto Player = m_Board[x][y].GetPlayer();
if (Player)
{
int PlayerNum = Player->GetPlayerNumber();
PlayerNum <<= ((x * Width + y) * 2);
Data |= PlayerNum;
}
}
}
}
typedef typename Stuff::Traits::LeastBits<Width * Height * 2>::type FriendlyMapInstance_t;
I have no idea what would help or not. But I will test. We'll see what is more effective.