Thread: Looking for appropriate container

  1. #16
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #17
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Elysia View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #18
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #19
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Elysia View Post
    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.
    Last edited by brewbuck; 07-21-2010 at 11:26 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #20
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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;
        }
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. iterator to unspecified container?
    By StainedBlue in forum C++ Programming
    Replies: 16
    Last Post: 06-04-2010, 05:02 AM
  2. sorting container
    By l2u in forum C++ Programming
    Replies: 6
    Last Post: 09-01-2007, 01:12 PM
  3. stl container to store more than 1 type
    By sujeet1 in forum C++ Programming
    Replies: 7
    Last Post: 05-09-2007, 04:10 AM
  4. Replies: 1
    Last Post: 01-23-2006, 07:12 PM
  5. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM