0

好的，伙计们：内存优化绝对不是我的事，因为我目前正在从事一个大型、cpu 和内存密集型项目，我想我需要你的帮助。

该项目是一个国际象棋引擎，实际问题（我猜）在于以下两种方法之一（上面的代码不是100％准确，但或多或​​少）：

树搜索 ( MiniMax ) - 实际代码是带有不同添加的 Alpha-Beta，但这个非常基本的示例更具说明性：

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;
}

移动生成 （如果您从未玩过国际象棋编程和位板，以下内容可能看起来几乎毫无意义；但您仍然会在内存处理方面有所了解 - 嗯，希望......）：

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;
}

移动类

//=======================================================
// 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);
}

显然，第一个函数被递归并调用了数百万次，有一些预期的负载。问题是一旦搜索到第 4 层、第 5 层或其他东西，该应用程序已经占用了 2GB 空间。问题是，一旦完成（搜索），内存仍未释放- 所以我想这表明存在问题。

那么，有什么想法吗？

请让我知道，以防您需要了解有关实施的任何其他信息。

提示：

  • FOREACH只是向量迭代器的宏
  • for 向量附加来自+=Boost
  • 粗体中的所有内容都是一个宏，但就内存开销而言，它们都没有做任何密集的事情（所以我决定省略它们）
  • 没有实现任何析构函数
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，您可以执行以下操作，而不是执行 a ：

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

这会调用复制构造函数。如果您想避免额外的副本，请为Move上述“setter”函数创建一个空构造函数：

    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;
}

这样，您将只分配一次内存，并在完成后清理它。

如果您同意：在 C++ 中使用数组或 std::vectors，性能差距是什么？它说要避免动态数组，然后：

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

没有实现任何析构函数

为什么你认为应该释放内存。您正在调用 new 很多次，但您永远不会删除Move您创建的 s 。

另外，向我们展示Move类的定义

于 2013-01-22T04:24:26.950 回答