0

OK, guys : memory optimization is definitely not my thing and since I'm currently working on a big, and cpu and memory-intensive project, I think I need your help.

The project is a Chess Engine and the actual problem lies (I guess) in one of the 2 following methods (the code above is not 100% exact but it's more-or-less that) :

Tree Search (MiniMax) - the actual code is an Alpha-Beta with different additions, but this quite basic example is more illustrative :

int Board::miniMax_(int ply)
{
    if (ply == this->searchDepth) return this->eval();

    int best = MINUS_INF;

    vector<Move*> moves = this->possibleMoves();

    FOREACH(Move*, move, moves)
    {
        HASHMAKE((*move),this);
        int val = -this->miniMax_(ply+1);
        UNHASHMAKE((*move),this);

        if (val>best) { 
            if (ply==0) this->bestMove = (*move);
            best = val; 
        }

    }
    return best;
}

Move Generation (if you haven't ever played with Chess programming and bitboards, the following might simply look almost non-sensical; but you'll still get the idea in terms of memory handling - well, hopefully...):

vector<Move*> Board::possibleMoves()
{
    U64 ownPieces = this->piecesForColor(this->playing);
    U64 occupied = ~(this->pieces[empty]);

    vector<Move*> moves;

    //-----------------------------------------
    // "Normal" Piece Moves
    //-----------------------------------------

    const int from = (1+(this->playing))*3;
    const int to = (1+(this->playing))*3+6;

    for (int pieceType=from; pieceType<to; pieceType++)
    {
        U64 piece = this->pieces[pieceType];

        for (; piece != 0; piece &= (piece - 1))
        {
            UINT pos = log2(piece & ~(piece-1));

            U64 move;
            switch (pieceType)
            {
                case bPawns:    move = BPAWN_(pos,ownPieces,occupied); break;
                case wPawns:    move = WPAWN_(pos,ownPieces,occupied); break;
                case bRooks:
                case wRooks:    move = ROOK_(pos,ownPieces,occupied); break;
                case bKnights:
                case wKnights:  move = KNIGHT_(pos,ownPieces,occupied); break;
                case bBishops:
                case wBishops:  move = BISHOP_(pos,ownPieces,occupied); break;
                case bQueen:
                case wQueen:    move = QUEEN_(pos,ownPieces,occupied); break;
                case bKing:
                case wKing:     move = KING_(pos,ownPieces,occupied); break;
                default:break;
            }

            for (; move !=0; move &= (move-1))
            {
                moves += new Move(pos, log2(move&~(move-1)),this);
            }
        }
    }

    return moves;
}

The Move class

//=======================================================
// Prototype
//=======================================================

class Move
{
    public:
        Move (string m, Board* b) : from(ALG2FROM(m)), to(ALG2TO(m)), pieceFrom(b->atPosition[from]), pieceTo(b->atPosition[to]) {}
        Move (int f, int t, Board* b) : from(f), to(t), pieceFrom(b->atPosition[from]), pieceTo(b->atPosition[to]) {}
        Move (int val) : value(val) {}

        inline string notation();
        inline string out();
        //----------------------
        int from, to;
        int pieceFrom, pieceTo;
        int value;
};

//=======================================================
// Inline Functions
//=======================================================

inline string Move::notation()
{
    return SSTR(SPOS(this->from) << SPOS(this->to));
}

inline string Move::out()
{
    return SSTR(this->notation() << " :: " << this->value);
}

Obviously, the first function being recursive AND called some millions of times, there is some expected load. The thing is once the search goes up to the 4th,5th ply or something, the app already takes up like 2GB. And the thing is that once it's complete (the search), the memory is still not freed - so I suppose this is indicating a problem.

So, any ideas?

Please, just let me know in case you need to know anything else about the implementation.

Hints :

  • FOREACH is just a macro for a vector iterator
  • the += for vector appending comes from Boost
  • everything in bold is a macro, but in terms of memory overhead, none of them is doing anything intensive (so I decided to omit them)
  • no destructors implemented whatsoever
4

3 に答える 3

3

ここ：

vector<Move*> moves = this->possibleMoves();

ポインターのベクトルは、ポインターを解放しません。代わりにのベクトルを試すことができstd::unique_ptr<Move>ます。

移動を個別に割り当てない場合は、パフォーマンスが向上します。メモリプールを使用します。その点で、ベクトルはまったく必要ないかもしれません。

ポリモーフィッククラスでない限りMove、割り当てないことをお勧めします。代わりに、関数の束を作成し、次のようにSet関数Moveを宣言しますpossibleMoves。

void Board::possibleMoves( vector<Move> & moves )

そして明らかにそれをこのように呼びます：

vector<Move> moves;
possibleMoves( moves );

つまり、これは、移動を追加するときに、を実行する代わりに、次のnewようなことを実行できることを意味します。

    moves.push_back( Move(pos, log2(move&~(move-1)),this) );

これにより、コピーコンストラクターが呼び出されます。余分なコピーを避けたい場合は、の空のコンストラクターをMove作成し、前述の「セッター」関数を作成します。

    moves.resize( moves.size()+1 );
    Move & m = moves.back();
    m.Set( pos, log2(move&~(move-1)),this );

それがもっと速くなるかどうかは100％わかりません。とにかく、別のこと...通常のボードでは、ほとんどの場合、可能な移動が50未満であると予想される場合は、次の最初にこれを行うことでパフォーマンスを向上させることができますpossibleMoves。

moves.reserve(50)

つまり、ベクトルのサイズを変更する必要がほとんどないため、push_back操作が高速になります。

于 2013-01-22T04:25:06.310 に答える
2

この場合、std::vectorが最適なコンテナかどうかはわかりません。

可能な移動の数は有限であり、それを計算できるはずです。私はあなたがそれをどのように行うかを推測するつもりはありませんが、あなたがそれを行うことができると仮定すると（または単にconstの大きな数を使用する）...代わりに配列を使用する価値があるかもしれません：

Move *moves = new Move[maxMoves];
FillPossibleMoves(moves, maxMoves)
// do stuff
delete [] moves;

次に、可能な移動関数を次のように更新できます。

int Board::FillPossibleMoves(Move *moves, int maxMoves)
{
    int i = 0;
    ...
    moves[i].Something = Whatever;
    i++;
    ...
    return i;
}

そうすれば、メモリを1回だけ割り当て、使い終わったらクリーンアップすることができます。

同意する場合：C++で配列またはstd:: vectorを使用する場合、パフォーマンスのギャップはどのくらいですか？これは、動的配列を避けるように言っています。

std::vector<Move> moves(maxMoves);
// if you use a const, then you can keep declaration above as a member
// and call moves.clear() here instead
int movesAdded = board->FillPossibleMoves(moves);
// do stuff


int Board::FillPossibleMoves(std::vector<Move> &moves)
{
    int i = 0;
    ...
    moves[i].Something = Whatever;
    i++;
    ...
    return i;
}
于 2013-01-22T04:44:09.783 に答える
0

デストラクタは一切実装されていません

なぜあなたは記憶が解放されるべきだと思いますか。あなたは何度も新しいものを呼んでいますが、あなたがMove作成したを削除することは決してありません。

また、Moveクラスの定義を教えてください

于 2013-01-22T04:24:26.950 に答える