History/Killer heuristics made bot weaker

[Joeger-Bahar]

I added history heuristics and killer move tracking to my bot, and now it performs worse against a previous version at 0.5s per move. I decay by 1/2 every search, I only use "quiet" moves, and they're ordered after MVV.

Is this normal in bullet games or should I post code to help debug.

[Aleks Peshkov]

0.5s per move is not bullet for modern engines. It is long time control in fact. 1s + 0.01s is bullet. 10s + 0.1s is average for tests.

[Joeger-Bahar]

Is it common for history heuristics to make the engine worse in low ply searches (3-4)

[abulmo2]

I added history heuristics and killer move tracking to my bot, and now it performs worse against a previous version at 0.5s per move. I decay by 1/2 every search, I only use "quiet" moves, and they're ordered after MVV.

Is this normal in bullet games or should I post code to help debug.

With my engine Dumb, which is pretty simple, I have got a +22 Elo increase with killer moves & a +94 Elo increase with history heuristics, measured at 10+0.1s per game (I do not use fixed time per move) in self-play games. I suppose your implementation is not correct somewhere.

[rickpo]

How were you sorting non-MVV moves before you added history/killers? Were they just in movegen order? If that's the case, then I can't imagine history/killers making things worse. And both history and killers should be very fast to track and use, so the overhead shouldn't be a big factor.

I suspect you have a bug somewhere.

[emadsen]

I added history heuristics and killer move tracking to my bot, and now it performs worse against a previous version at 0.5s per move. I decay by 1/2 every search, I only use "quiet" moves, and they're ordered after MVV.

Killer moves should improve playing strength by 60 Elo or so. But it varies based on what features already are present in your engine.

Decaying history by 1/2 every search throws away too much information, I believe. My engines reduces the history heuristic by 248 / 256 each search iteration (97%). Perhaps you do mean each search and we're saying the same thing? So after a depth 22 search my statement == your statement? Because (248 / 256) Pow 22 == 1/2.

In my experience, history heuristic isn't worth much at all without LMR. The point of the history heuristic is to order moves for aggressive late move reductions.

[Uri Blass]

0.5s per move is not bullet for modern engines. It is long time control in fact. 1s + 0.01s is bullet. 10s + 0.1s is average for tests.

Bullet is not defined by the type of the engine but only by time control.

0.5 second per move is certainly bullet regardless of the software or hardware.
It will continue to be bullet even if hardware becomes 100 times faster.

[Joerg Oster]

0.5s per move is not bullet for modern engines. It is long time control in fact. 1s + 0.01s is bullet. 10s + 0.1s is average for tests.

Bullet is not defined by the type of the engine but only by time control.

0.5 second per move is certainly bullet regardless of the software or hardware.
It will continue to be bullet even if hardware becomes 100 times faster.

On this I tend to agree with you.

[Joeger-Bahar]

Here is the relevant code. I use negamax, NUM_PIECES is 6, and depth goes from greatest at the top node to least at the leaf nodes.

I use iterative deepening, and call OrderMoves after each move generation (pseudo-legal)

Code: Select all

// [color][pieces][start square][end square]
int historyHeuristic[2][NUM_PIECES][64][64] = { 0 };
Move killerMoves[MAX_PLY][2];

Assigning heuristics and killer moves

Code: Select all

alpha = std::max(alpha, eval);
if (alpha >= beta) // Beta cutoff
{
	if (!move.IsCapture(engine->GetBoard()) && (Pieces)move.promotion == 	Pieces::NONE && !opponentInCheck) // Beta cutoff = good
	{
		if (killerMoves[ply][0] != move)
		{
			killerMoves[ply][1] = killerMoves[ply][0];
			killerMoves[ply][0] = move;
		}

		int from = move.startSquare;
		int to = move.endSquare;
		Piece movingPiece = engine->GetBoard()[from].GetPiece();
		int pieceType = (int)movingPiece.GetType();

		historyHeuristic[(int)movingPiece.GetColor()][pieceType][from][to] += depth * depth;
	}
	break;
}

Ordering moves

Code: Select all

// Move ordering scores
const int captureBonus = 1000000;
const int killerBonus = 500000;

int Bot::ScoreMove(const Move move, int ply, bool onlyMVVLVA)
{
	Piece moved = engine->GetBoard()[move.startSquare].GetPiece();
	Piece captured = engine->GetBoard()[move.endSquare].GetPiece();

	// MVV-LVA: Most Valuable Victim - Least Valuable Attacker
	if (captured.GetType() != Pieces::NONE)
		return captureBonus + PieceValue(captured) * 16 - PieceValue(moved);

	if (onlyMVVLVA) return 0;
	if (move == killerMoves[ply][0]) return killerBonus;
	else if (move == killerMoves[ply][1]) return killerBonus - 100;

	return historyHeuristic[(int)moved.GetColor()][(int)moved.GetType()][move.startSquare][move.endSquare];
}

// Orders moves in-place, best first
void Bot::OrderMoves(std::vector<Move>& moves, int ply, bool onlyMVVLVA, Move firstMove)
{
	std::sort(moves.begin(), moves.end(),
		[&](const Move& a, const Move& b) {
			return ScoreMove(a, ply, onlyMVVLVA) > ScoreMove(b, ply, onlyMVVLVA);
		});

	if (!firstMove.IsNull())
	{
		// Insert previous iter best move at front
		moves.insert(moves.begin(), firstMove);

		// Remove move if it was already in
		auto it = std::find(moves.begin() + 1, moves.end(), firstMove);
		if (it != moves.end()) {
			moves.erase(it);
		}
	}
}