how to continue

[lithander]

Sorting moves at the root node is different. During the search itself, you sort moves by kinda just guessing how good they are in the most basic way, usually just by MVVLVA. However that is just a very rough guess, you don't want to spend too much time on trying to figure out precisely how good a move somewhere down in the search tree is. However in the iterative deepening framework, we can do much better than that for the root moves. Those can be sorted much more precisely based on how well they performed during the previous iterations. This can be done in multitude of different ways. First, you would search the best move that was found during the previous iteration, as for the rest of the moves, I like to keep track of their current score (there's a little caveat to that), previous iteration score and how many nodes were explored for that particular root move (more nodes explored means that the move was harder to refute, meaning it's probably a decent move) and sort them based on these 3 statistics.

So far I've never tried sorting root moves any different than the other moves (best move of the previous iteration first, MVVLVA next, killers, remaining quiets based on history) and thinking about it now it makes sense that they deserve special treatment.

Sorting by node counts makes sense. But how do I sort by score? Intuitively I would say that when I'm starting to search the next depth all I know is that one move was the previously the best and the others were worse. But not how much worse because I never searched them with a full window but one constrained by the score of the best move. None of the others managed to raise alpha above that and returned alpha as their score. They all appear equally bad.

[tcusr]

i thought i was supposed to always sort the moves, not only at the root?

Sorting moves at the root node is different. During the search itself, you sort moves by kinda just guessing how good they are in the most basic way, usually just by MVVLVA. However that is just a very rough guess, you don't want to spend too much time on trying to figure out precisely how good a move somewhere down in the search tree is. However in the iterative deepening framework, we can do much better than that for the root moves. Those can be sorted much more precisely based on how well they performed during the previous iterations. This can be done in multitude of different ways. First, you would search the best move that was found during the previous iteration, as for the rest of the moves, I like to keep track of their current score (there's a little caveat to that), previous iteration score and how many nodes were explored for that particular root move (more nodes explored means that the move was harder to refute, meaning it's probably a decent move) and sort them based on these 3 statistics.

also, with this method, how do i get the line the engine searched? is this why PV is used?

There are many different ways of collecting the PV. The chess programming wiki presents several of them as well, depending on the features that you have implemented in your engine some might perform better than others. For example, the Transposition Table makes it trivial to some extent, however you run the risk of not being able to display the full PV because of overwrites, and getting into infinite loops when extracting the moves. I used to use that approach combined with an additional special smaller hash table, that backed-up just the PV nodes in case they were overwritten in the main TT. Recently i got rid of that though, after implementing multithreading it just became too bothersome to try to preserve the PV nodes in this way.

What i do now is very similar to the "PV-list on the stack" solution on the chess programming wiki. You simply create a new PvLine struct in every node you search, and pass it down the tree, letting the nodes below fill it for you with the PV line they find. In c++, if you are lazy, you can use std::vector for this, as usually PV won't be changing too much, the costs of using higher abstractions are negligible. In root node you pass in an empty vector, and when the search is finished for that particular root move, you will have the PV line stored in the vector.

Slightly modified code from the wiki ...

Code: Select all

int AlphaBeta(int depth, int alpha, int beta, std::vector<Move> &parent_line) {

    if (depth == 0) {
        return Evaluate();
    }
    
    std::vector<Move> this_line;
    GenerateLegalMoves();
    while (MovesLeft()) {

        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha, this_line);
        UnmakeMove();

        if (val >= beta) return beta;
        if (val > alpha) {
            alpha = val;
            parent_line = std::move(this_line); // copy the PV moves found deeper in the tree to our parent's PV line
            parent_line.insert(parent_line.begin(), ThisMove()); // insert our own PV move (the one that caused alpha to improve) at the beginning
        }
    }
    return alpha;
}

thank you very much for explaining, now i understand

[Mergi]

But not how much worse because I never searched them with a full window but one constrained by the score of the best move. None of the others managed to raise alpha above that and returned alpha as their score. They all appear equally bad.

The idea was to keep previous iterations PV moves near the top of the move list, using score. First, by always moving the PV move to the top of the list, we ensure that on the next iteration it is searched first. Even if that move gets beaten the next iteration, we still want to keep it near the top, perhaps as our 2nd best move. This is ensured by setting the scores for moves that fail to some same low value (negative infinity) and keeping whatever score was returned for the moves that beat alpha. Then if we use stable sorting algorithm, we can keep pushing PV move from each iteration to the top of move list, while still keeping the relative order of PV moves from previous iterations, as we have found them. If our PV changes a lot, this should help a little, especially when counting the nodes might not work all that well when multithreading is introduced (as there might be big cutoffs due to TT having scores found by different threads).

[tcusr]

update:
after minor problems in other parts of the program i implemented the alphabeta function but for some reason it seg faults. can someone tell me if anything looks off?

Code: Select all

template<int C>
int alphabeta(Board& board, int depth, int alpha, int beta)
{
	if (depth == 0)
		return -eval<C>(board);

	Move list[250];
	Move *end = generate_noisy<C>(board, list);
	end = generate_quiet<C>(board, end);

	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (board.move_was_legal()) { // just checks if the other king is in check since make_move change the side to move
			int eval = -alphabeta<C ^ 1>(board, depth - 1, -beta, -alpha);

			if (eval >= beta)
				return beta;

			if (eval > alpha)
				alpha = eval;
		}

		board.undo_move<C>(*m);
	}

	return alpha;
}

this is my perft function for reference, which works perfectly with all the positions i tried

Code: Select all

template<int C>
int perft(Board& board, int depth)
{
	if (depth == 0)
		return 1;

	uint64_t nodes = 0;
	Move list[250];
	Move *end = generate_noisy<C>(board, list);
	end = generate_quiet<C>(board, end);

	for (Move *m = list; m != end; ++m) {
		board.make_move<C>(*m);

		if (board.move_was_legal())
			nodes += perft<C^1>(board, depth-1);

		board.undo_move<C>(*m);
	}
	return nodes;
}

[R. Tomasi]

Looks legit to me at first glance. Can't you catch the seg-fault by running it with a debugger?

[Ras]

for some reason it seg faults.

You need to learn how to debug segfaults. Here's a nice tutorial using command line GDB: http://www.unknownroad.com/rtfm/gdbtut/gdbsegfault.html

[tcusr]

i just noticed i return from the function without unmaking the move if eval >= beta, sorry for the inconvience

[tcusr]

for some reason it seg faults.

You need to learn how to debug segfaults. Here's a nice tutorial using command line GDB: http://www.unknownroad.com/rtfm/gdbtut/gdbsegfault.html

thank you for the link, i usually just do r and bt but in this case it traced back to an unrelated part of the program so i didn't what to do

[tcusr]

i rewrote the search function and now the engine seems to be working correctly consistently, it solves lichess puzzles if i give enough depth to see the combination (i'm only evaluating material for now).
now i'm going to add:
1) move ordering (i'll start with MVV/LVA because it is the simplest)
2) PSQT tables to improve strength
3) quiescence search

i have one question, is MVV ordering basically running a sort function on all the captures using the value of the piece on the "to" square to compare? and LVA just sorting in descending order using the value of the piece on the "from" square? this is the case for me because i use this enum

Code: Select all

enum {
	KING = 1,
	PAWN,
	KNIGHT,
	BISHOP,
	ROOK,
	QUEEN
};

[algerbrex]

i rewrote the search function and now the engine seems to be working correctly consistently, it solves lichess puzzles if i give enough depth to see the combination (i'm only evaluating material for now).
now i'm going to add:
1) move ordering (i'll start with MVV/LVA because it is the simplest)
2) PSQT tables to improve strength
3) quiescence search

i have one question, is MVV ordering basically running a sort function on all the captures using the value of the piece on the "to" square to compare? and LVA just sorting in descending order using the value of the piece on the "from" square? this is the case for me because i use this enum

Code: Select all

enum {
	KING = 1,
	PAWN,
	KNIGHT,
	BISHOP,
	ROOK,
	QUEEN
};

Not quite. The way I've usually seen MVV/LVA implemented is using a two-dimensional array. Here's how Blunder does MVV-LVA move ordering:

Code: Select all

// An array that maps move scores to attacker and victim piece types
// for MVV-LVA move ordering: https://www.chessprogramming.org/MVV-LVA.
var MvvLva [7][6]int16 = [7][6]int16{
	{16, 15, 14, 13, 12, 11}, // victim Pawn
	{26, 25, 24, 23, 22, 21}, // victim Knight
	{36, 35, 34, 33, 32, 31}, // victim Bishop
	{46, 45, 44, 43, 42, 41}, // vitcim Rook
	{56, 55, 54, 53, 52, 51}, // victim Queen

	{0, 0, 0, 0, 0, 0}, // victim King
	{0, 0, 0, 0, 0, 0}, // No piece
}

...

// Score the moves given
func (search *Search) scoreMoves(moves *MoveList, ttBestMove Move, ply uint8) {
	for index := 0; index < int(moves.Count); index++ {
		move := &moves.Moves[index]
		captured := &search.Pos.Squares[move.ToSq()]
		moved := &search.Pos.Squares[move.FromSq()]
		move.AddScore(MvvLva[captured.Type][moved.Type])
	}
}

...

// Order the moves given by finding the best move and putting it
// at the index given.
func orderMoves(index int, moves *MoveList) {
	bestIndex := index
	bestScore := moves.Moves[bestIndex].Score()

	for index := bestIndex; index < int(moves.Count); index++ {
		if moves.Moves[index].Score() > bestScore {
			bestIndex = index
			bestScore = (*moves).Moves[index].Score()
		}
	}

	tempMove := moves.Moves[index]
	moves.Moves[index] = moves.Moves[bestIndex]
	moves.Moves[bestIndex] = tempMove
}

And here's how "scoreMoves" and "orderMoves" are called in negamax:

Code: Select all

// Score the moves
search.scoreMoves(&moves, ttBestMove, ply)

for index := 0; index < int(moves.Count); index++ {
	// Order the moves to get the best moves first.
	orderMoves(index, &moves)
	move := moves.Moves[index]

         ...
}