Having trouble understanding advanced move ordering techniques

[pedrojdm2021]

Hello! i hope you all are doing great.

I'm currently trying to improve my engine search, one of the most important points that i have to work is to reduce the number of moves searched:
This is for depth 9 and "kiwipete" position:

Code: Select all

info depth 9 time 1873 nodes 1783749 score cp -64 pv e2a6 e6d5 e5g6 f7g6 c3b5 d5e4 b5c7 e8d8 f3g3 h3g2
bestmove e2a6

You can see that it took 1.8 seconds, and more than 1.7 million nodes to complete the search, for me that is too much, as i've seen engines that is searching less than 100.000 for the same position and the same depth

Looking at the code from other engines like Demolito, i see that they are using some advanced move ordering stuff, i undestand that move ordering is so important to have the shortest and optimal search.

I currently have a very basic move ordering:

1) PV Move
2) Captures via MVV/LVA
3) Killers (first killer and second killer)
4) History Heuristic

For search features i have:
- PVS (Principal variation search)
- Null move pruning
- Mate distance pruning
- Late move reductions
- Delta pruning in QS
- Futility Pruning

I see that these engines are using mostly follow up history, refutation history, and Counter-move heuristic

So i decide to begin with Counter move heuristic, as is the one that looks more simpler than the others, and the one that i've found most documentation.

The problem that i'm facing right now with CounterMove is that i don't understand it very clearly the idea.

I've found This post:
http://www.talkchess.com/forum3/viewtop ... =7&t=72531

But i don't get it completly. They are talking in the comments that counter move heuristic is based in the "Previous Move" , like for an oponent response, as i understand a "previous move" is the move that was played BEFORE the current move in the move loop inside the search loop, right?

If yes, how can i score the moves ? I mean in the score_moves() function should i get the previous move ( i - 1) and pass it as parameter to the get_move_score() function?

As for the others, what are exactly the similitudes between each of them?

if anyone could give some sample code, would be great.

i tried to compare and do the stuff as i understood at the moment:

Code: Select all

// beta cut-off
if (score >= _beta)
{
	// update killer moves
	if (!mflag.Is_Capture())
	{
			killer_moves[1][ply] = killer_moves[0][ply];
			killer_moves[0][ply] = current_move;
	}

	// update counter move history
	MoveFlag prev_flag = MoveUtility.Get_flag(prev_move);
	if (prev_move != 0 && !prev_flag.Is_Capture())
	{
		byte prev_from = MoveUtility.Get_square_from(prev_move);
		byte prev_to = MoveUtility.Get_square_to(prev_move);
		countermove_history[prev_from][prev_to] = prev_move;
	}

		transposition.Store(ply, board.hash, TTFlag.BETA, score, _depth);
		return _beta;
	}

and in my move Score function:

Code: Select all

private static int GuessMoveScore(ushort _move , ushort _prev_move)
{
	int score = 0;

	if (score_pv && pv_table[0][ply] == _move)
	{
		score_pv = false;
		score += 40000;
	}

	MoveFlag flag = MoveUtility.Get_flag(_move);
	byte sq_from = MoveUtility.Get_square_from(_move);
	byte sq_to = MoveUtility.Get_square_to(_move);
			
			

	if (flag.Is_Capture())
	{
		byte attacker = board.boardPieces[sq_from];
		byte victim = board.boardPieces[sq_to];
		//apply lookup to the MVV/LVA Table   
		score += mvv_lva[attacker][victim] + 30000;

		// int see_value = see(_move);
		// return see_value + 20000;
	}
	else
	{
		if (killer_moves[0][ply] == _move)
			score += 9000;
		else if (killer_moves[1][ply] == _move)
			score += 8000;
		else
			score += history_moves[board.sideToMove][sq_from][sq_to];
				
		byte prev_from = MoveUtility.Get_square_from(_prev_move);
		byte prev_to = MoveUtility.Get_square_to(_prev_move);
		if (_prev_move != 0 && countermove_history[prev_from ][prev_to ] == _move)
			score += 5000;
	}
	
	return score;
}

but it does not take any effect in the move ordering. The search numbers are the same.

I did another test in instead of prev. move, i used the current move, and the differences were minimal, so probably i'm doing something wrong, or everything wrong

Thank you for your time, i'll appreciate all the help

[brianr]

I also tried numerous move ordering and pruning techniques, some of which I understood, and some I candidly did not.
There is a surprisingly complex ecosystem in the search/eval for each engine, and they can be quite different.
What works in one engine may very well not work in another.
Accordingly, I would not be concerned with numbers from a single position, or even a collection of positions.
The question is how does it play?

FWIW, for Tinker the kiwipete position to depth 9 takes 464K nodes.
I do not use counter-move as I have not actively worked on Tinker since AlphaZero and LeelaChess (Lc0) arrived some years ago.

[Tearth]

Good SEE greatly improved move ordering quality in all my engines, so I recommend trying it instead of MVV/LVA - although if I recall correctly, some engines use a mix of both methods, but it's a matter of testing what will perform the best for you.

[op12no2]

For search features i have:
- PVS (Principal variation search)
- Null move pruning
- Mate distance pruning
- Late move reductions
- Delta pruning in QS
- Futility Pruning

To reduce nodes you could add: 'beta pruning', 'alpha pruning' and 'late move pruning'.

[pedrojdm2021]

Good SEE greatly improved move ordering quality in all my engines, so I recommend trying it instead of MVV/LVA - although if I recall correctly, some engines use a mix of both methods, but it's a matter of testing what will perform the best for you.

Thank you very much for your reply, i have tried SEE, i took the algorithm from Demolito:
https://github.com/lucasart/Demolito/bl ... ion.c#L578

But that thing seems to be very expensive do you know any method to deduce SEE in a cheaper way?

i actually reaching about 1 million nodes per second, but if i add SEE in can slow down my speed in about 200.000 nodes per second or somethimes even more.

[pedrojdm2021]

I also tried numerous move ordering and pruning techniques, some of which I understood, and some I candidly did not.
There is a surprisingly complex ecosystem in the search/eval for each engine, and they can be quite different.
What works in one engine may very well not work in another.
Accordingly, I would not be concerned with numbers from a single position, or even a collection of positions.
The question is how does it play?

FWIW, for Tinker the kiwipete position to depth 9 takes 464K nodes.
I do not use counter-move as I have not actively worked on Tinker since AlphaZero and LeelaChess (Lc0) arrived some years ago.

around 500k nodes is at least the target that i want to reach, the bad thing is that as i am not a pro, and i'm still kinda beginner of this world of chess programming, i don't really know that i'm missing maybe some important features

next i'm going to add Razoring and maybe another pruning techniques to see if i start improving my numbers.

About the move ordering, yes, that thing seems to be very tricky sometimes helps, sometimes not.

about the play strenght it plays okish for now:

My Engine is White, VICE 1.1 is black.
[pgn]
[Event "Computer chess game"]
[Site "DESKTOP-LTHGU0S"]
[Date "2022.02.12"]
[Round "?"]
[White "ChessPedro"]
[Black "Vice1.1"]
[Result "1-0"]
[BlackElo "2000"]
[ECO "D02"]
[Opening "Queen's Pawn"]
[Time "13:35:03"]
[Variation "London"]
[WhiteElo "2000"]
[Termination "normal"]
[PlyCount "135"]
[WhiteType "program"]
[BlackType "program"]

1. Nf3 {(Ng1-f3 d7-d5 e2-e3 Nb8-c6 d2-d4 e7-e6 Bf1-d3 Bf8-b4+) +0.15/8 0}
d5 {(d7d5 d2d4 c8f5 c1d2 g8f6 e2e3 b8c6 f1d3) -0.15/8 0} 2. d4 {(d2-d4
Bc8-f5 Bc1-f4 Nb8-c6 e2-e3 e7-e6 Bf1-d3 Bf8-b4+) +0.09/8 0} Nf6 {(g8f6 e2e3
c8g4 f1d3 b8c6 h2h3 g4e6 e1g1) -0.15/8 1} 3. Bf4 {(Bc1-f4 Bc8-f5 e2-e3
e7-e6 Nb1-c3 Bf8-d6 Bf1-d3 Bd6xf4) +0.16/8 0} e6 {(e7e6 e2e3 f8b4 c2c3 b4d6
f1d3 e8g8 e1g1) -0.05/8 1} 4. e3 {(e2-e3 Bf8-d6 Bf4xd6 c7xd6 Bf1-d3 Nb8-c6
Nb1-c3 e6-e5) +0.39/8 0} Bb4+ {(f8b4 c2c3 b4d6 f4d6 c7d6 f1b5 c8d7 b1a3)
-0.05/8 2} 5. c3 {(c2-c3 Bb4-d6 Bf4xd6 Qd8xd6 Bf1-d3 Nb8-c6 Nb1-d2 Bc8-d7
Ra1-c1) +0.61/8 0} Be7 {(b4e7 f3e5 e8g8 f1d3 e7d6 e1g1 b8d7 b1d2) -0.13/8
0} 6. Bd3 {(Bf1-d3 Nb8-c6 Nb1-d2 O-O O-O Bc8-d7 Ra1-c1 Ra8-c8) +0.64/8 0}
Nh5 {(f6h5 f4e5 b8c6 e1g1 f7f6 e5g3) -0.05/8 0} 7. Be5 {(Bf4-e5 Nb8-c6 O-O
O-O Nb1-d2 Nc6xe5 Nf3xe5 Nh5-f6) +0.56/8 0} Nc6 {(b8c6 f3d2 h5f6 e5f6 e7f6
d1c2 h7h6 e1g1) 0.00/8 1} 8. O-O {(O-O O-O Nb1-d2 Bc8-d7 Ra1-c1 Nc6xe5
Nf3xe5 Nh5-f6) +0.44/8 0} O-O {(e8g8 f3d2 g7g6 c3c4 f7f6 e5g3 c6b4 d2f3)
+0.10/8 0} 9. Nbd2 {(Nb1-d2 Nc6xe5 d4xe5 g7-g6 Qd1-b3 Ra8-b8 Ra1-d1 Bc8-d7)
+0.57/8 0} f6 {(f7f6 e5g3 h5g3 f2g3 c8d7 d1b3 c6a5 b3c2) +0.15/8 0} 10. Bg3
{(Be5-g3 f6-f5 Qd1-c2 Nh5xg3 h2xg3 Bc8-d7 Ra1-d1 Ra8-c8) +0.67/8 0} Nxg3
{(h5g3 f2g3 e6e5 d3b5 e5e4 f3h4 c8d7 h4f5) +0.30/8 0} 11. hxg3 {(h2xg3
e6-e5 d4xe5 Nc6xe5 Nf3xe5 f6xe5 Qd1-h5 e5-e4) +0.26/8 0} e5 {(e6e5 e3e4
c8e6 d1c2 e5d4 c3d4 d5e4 d3e4) +0.32/8 0} 12. e4 {(e3-e4 Bc8-e6 Rf1-e1
e5xd4 c3xd4 d5xe4 Re1xe4 Nc6-b4) +0.44/8 0} exd4 {(e5d4 e4d5 c6e5 d1b3 d8d6
c3d4 e5d3 b3d3) +0.18/8 0} 13. exd5 {(e4xd5 d4xc3 b2xc3 Rf8-f7 Bd3-c4
Nc6-e5 Rf1-e1 Bc8-g4) +0.59/8 0} dxc3 {(d4c3 d5c6 d8d3 d1b3 g8h8 a1e1 e7c5
c6b7) +0.15/8 0} 14. bxc3 {(b2xc3 Nc6-e5 Nf3xe5 f6xe5 Qd1-b3 Be7-c5 Nd2-e4
Bc5-b6) +0.72/8 0} Ne5 {(c6e5 f3e5 f6e5 d1b1 g8h8 c3c4 c7c6 d5c6) +0.20/8
0} 15. Nxe5 {(Nf3xe5 f6xe5 Qd1-b3 Qd8-d6 Ra1-e1 Rf8-f7 Nd2-f3 Be7-f6)
+1.02/8 0} fxe5 {(f6e5 d1b3 e7d6 b3b1 h7h6 d2e4 f8f7 e4d6) +0.17/8 0} 16.
Qc2 {(Qd1-c2 Kg8-h8 c3-c4 Be7-f6 Bd3xh7 e5-e4 Bh7xe4 Bf6xa1) +0.97/8 1} h6
{(h7h6 c3c4 e7f6) +0.13/8 0} 17. Rae1 {(Ra1-e1 Be7-f6 Qc2-b3 a7-a5 Nd2-e4
a5-a4 Ne4xf6+ Qd8xf6 Qb3-d1) +1.04/8 0} Bf6 {(e7f6 c3c4 c7c6 d5c6 b7c6 d2e4
c8e6 e4f6) -0.02/8 1} 18. Qb3 {(Qc2-b3 Kg8-h8 Nd2-f3 Qd8-d6 c3-c4 c7-c6
Bd3-g6 Kh8-g8) +1.02/8 0} Rb8 {(a8b8 d2e4 c8f5 g3g4 f5g6 e4f6 d8f6 d3g6)
-0.03/8 0} 19. Bg6 {(Bd3-g6 Kg8-h8 Nd2-f3 Qd8-d6 c3-c4 c7-c6 a2-a4 Bc8-g4)
+0.92/8 0} Kh8 {(g8h8 d2e4 f6e7 c3c4 c8d7) +0.05/8 0} 20. c4 {(c3-c4 Bc8-g4
Nd2-f3 Qd8-d6 c4-c5 Qd6-e7 Qb3-c4 Bg4xf3) +0.93/8 0} Bg4 {(c8g4 e1e4 d8c8
d2f3 g4f3 b3f3 f6g5 f3b3) +0.07/8 0} 21. Ne4 {(Nd2-e4 b7-b6 a2-a4 Kh8-g8
Qb3-c3 Rb8-c8 Ne4xf6+ Qd8xf6 Qc3-c2) +0.87/8 1} Be7 {(f6e7 f2f3 g4d7 b3b2
b7b5 c4c5 e7f6 e4f6) +0.05/8 0} 22. c5 {(c4-c5 a7-a5 a2-a4 Bg4-f5 Bg6xf5
Rf8xf5 Qb3-d3 Rf5-f7) +0.95/8 0} a6 {(a7a6) +0.05/8 1} 23. f3 {(f2-f3
Bg4-f5 Bg6xf5 Rf8xf5 d5-d6 Be7xd6 c5xd6 c7xd6) +1.30/8 0} Bd7 {(g4d7 d5d6
e7f6 g6f7 d7b5 f7c4 b5d7 e4f6) -0.15/8 0} 24. d6 {(d5-d6 Be7-f6 Bg6-f7
Bd7-a4 Qb3-e6 Ba4-d7 Qe6-c4 Bd7-b5) +1.19/8 0} Bf6 {(e7f6 e1d1 d7c6 g6f7
c6b5 f7c4 b5c6 e4f6) -0.10/8 0} 25. Rd1 {(Re1-d1 Bd7-c6 Rf1-e1 b7-b6 Ne4xf6
Rf8xf6 c5xb6 c7xd6) +1.21/8 1} Bb5 {(d7b5 f1e1 b7b6 d6d7 b6c5 e4c5 b5e2
b3b8) -0.10/8 0} 26. Rfe1 {(Rf1-e1 Bb5-c6 Bg6-f5 b7-b6 Ne4xf6 Rf8xf6 c5xb6
c7xd6) +1.33/8 0} b6 {(b7b6 d6d7 b6c5 e4c5 b5e2 b3b8 d8b8 e1e2) -0.10/8 0}
27. a4 {(a2-a4 Bb5-c6 Qb3-c2 b6xc5 Qc2xc5 Qd8-d7 Ne4xf6 Rf8xf6) +1.18/8 0}
Bc6 {(b5c6 d1b1 c7d6 c5b6 f6e7 e1c1 d8c8 b3c4) -0.10/8 0} 28. Qc2 {(Qb3-c2
b6xc5 Qc2xc5 Qd8-d7 Ne4xf6 Rf8xf6 Qc5-a7 Rb8-b7) +1.01/8 0} Bxe4 {(c6e4
g6e4 b6c5 c2c5 c7d6 c5d6 d8d6 d1d6) -0.10/8 0} 29. Bxe4 {(Bg6xe4 b6xc5
Qc2xc5 c7xd6 Qc5xd6 Qd8xd6 Rd1xd6 a6-a5) +0.86/8 0} bxc5 {(b6c5 d6d7 d8e7
e4f5 b8d8 f3f4 h8g8 a4a5) -0.08/8 0} 30. Qxc5 {(Qc2xc5 c7xd6 Qc5xd6 Qd8-a5
Qd6-c6 Rf8-d8 Qc6-c2 Qa5-b6+) +0.67/8 0} cxd6 {(c7d6 c5d6 d8a5 e4b7 a5a4
d6a6 a4a6 b7a6) +0.05/8 0} 31. Qxd6 {(Qc5xd6 Qd8-a5 Be4-c6 Rf8-d8 Qd6-e6
Qa5-b6+ Kg1-f1 Rd8-d4 Rd1xd4) +0.49/8 0} Qa5 {(d8a5 d1b1 b8d8 d6b4 a5c7
b1d1 c7a7 g1h1) +0.05/8 0} 32. Bc6 {(Be4-c6 Rf8-d8 Qd6-e6 Qa5-b6+ Kg1-f1
Rd8-d4 Rd1xd4 e5xd4 Kf1-f2) +0.52/8 0} Rfd8 {(f8d8 d6e6 a5b6 g1f1 d8d4)
+0.30/8 0} 33. Qe6 {(Qd6-e6 Rd8-d2 Kg1-f1 Rb8-d8 Rd1xd2 Qa5xd2 Bc6-e4
a6-a5) +0.35/8 0} Rd2 {(d8d2 g1f1 d2b2 f1g1 a5c5 g1h1 c5f2 e6h3) +0.35/8 1}
34. Kf1 {(Kg1-f1 Rb8-d8 Rd1xd2 Qa5xd2 Bc6-e4 a6-a5 Qe6-f7 Rd8-d4) +0.39/8
0} Rdb2 {(d2b2 f3f4 a5c5 e1e2 b2e2) +0.35/8 0} 35. Re2 {(Re1-e2 Rb2-b1
Rd1-e1 Rb1xe1+ Re2xe1 Qa5-d2 Bc6-e4 Rb8-b2 Qe6-e8+) +0.31/8 0} Rxe2 {(b2e2
f1e2 a5c5 e2f1 c5c2 e6d5 b8b2 f3f4) +0.30/8 0} 36. Kxe2 {(Kf1xe2 Qa5-c5
Ke2-f1 Qc5-c2 Rd1-e1 Rb8-b2 Qe6-e8+ Kh8-h7 Bc6-e4+) +0.25/8 0} Qc5 {(a5c5
e2f1 c5c2 e6d6 b8d8 c6d7 f6e7 d6d5) +0.25/8 0} 37. Kf1 {(Ke2-f1 Qc5-c2
Rd1-e1 Qc2-d3+ Kf1-g1 Qd3-d2 Re1-f1 Qd2-e3+ Rf1-f2 Rb8-b1+) +0.05/8 0} Qc2
{(c5c2 e6d6 b8c8 c6d7 c8d8 f1g1 f6e7 d6d3) +0.15/8 0} 38. Re1 {(Rd1-e1
Qc2-d3+ Kf1-g1 Qd3-d2 Re1-f1 Qd2-e3+ Kg1-h2 Rb8-d8 Bc6-e4 a6-a5) +0.12/8 0}
Qd3+ {(c2d3 f1g1 d3d2 g1f1 d2c2 g3g4 b8d8 e1e2) +0.32/8 0} 39. Kg1 {(Kf1-g1
Qd3-d2 Re1-f1 Qd2-g5 Bc6-d5 a6-a5 Kg1-h2 Qg5-h5+ Qe6-h3 Qh5xh3+) +0.09/8 0}
Rd8 {(b8d8 c6b7 d3d4 g1f1 d4a4 e6a6 a4b4 b7e4) +0.30/8 1} 40. Kh2 {(Kg1-h2
Qd3-d6 Qe6xd6 Rd8xd6 Re1-c1 Rd6-d2 Bc6-e4 Kh8-g8) +0.17/8 0} Qd2 {(d3d2
e1b1 a6a5 h2g1 d2c2 b1e1 c2c5) +0.37/8 0} 41. Rb1 {(Re1-b1 Qd2-f2 Bc6-e4
a6-a5 Rb1-b7 Qf2-e3 Rb7-c7 Rd8-d2) +0.47/8 0} Qc2 {(d2c2 b1b6 a6a5) +0.25/8
0} 42. Rb7 {(Rb1-b7 Qc2-f2 Rb7-c7 Qf2-e1 Bc6-e4 a6-a5 Be4-d5 Bf6-g5)
+0.67/8 0} a5 {(a6a5 b7d7 d8f8 f3f4 e5f4 g3f4 f8c8 c6b5) +0.10/8 1} 43. Rd7
{(Rb7-d7 Rd8-b8 Bc6-b5 Qc2-f2 Qe6-f7 Rb8-d8 Rd7xd8+ Bf6xd8 Bb5-d3) +0.68/8
0} Rf8 {(d8f8 c6b5 c2b1 e6d6 f8a8 d6d1 b1g6 f3f4) 0.00/8 0} 44. Rc7
{(Rd7-c7 Qc2-c5 Rc7-c8 Qc5-b4 Rc8xf8+ Qb4xf8 Bc6-e4 Qf8-c5 Qe6-e8+) +0.73/8
0} Qc1 {(c2c1 c7c8 c1c5 c8f8 c5f8 c6d5 f8b8 h2g1) +0.02/8 0} 45. Rc8
{(Rc7-c8 Qc1-c5 Rc8xf8+ Qc5xf8 Bc6-d5 g7-g6 Bd5-e4 Kh8-g7 Kh2-g1) +0.94/8
0} Qc5 {(c1c5 c8f8 c5f8 c6e4 f8b8 e6d5 b8b6 d5a8) 0.00/8 0} 46. Re8
{(Qe6-d7 Qc5-e7 Rc8xf8+ Qe7xf8 Bc6-e4 Qf8-g8 Qd7-c7 Qg8-d8) +0.88/7 0} Kh7
{(h8h7 e6c8 f6e7 c6e4 g7g6 c8c5 e7c5 e8e5) -1.15/8 0} 47. Be4+ {(Bc6-e4+
g7-g6 Qe6-d7+ Kh7-h8 Be4xg6 Bf6-g7 Bg6-e4 Rf8xe8 Qd7xe8+) +2.00/7 0} g6
{(g7g6 e6d7 h7h8 d7f7 f6g7 e8f8 c5f8 f7g6) -1.65/8 0} 48. Qd7+ {(Qe6-d7+
Kh7-h8 Be4xg6 Bf6-g7 Re8-e7 Rf8-g8 Qd7-e6 Rg8-d8 Bg6-e4) +2.27/8 0} Kh8
{(h7h8 d7f7 f6g7 e8f8 c5f8 f7g6 h8g8 g6h7) -1.45/8 0} 49. Qf7 {(Qd7-f7
Bf6-g7 Qf7xg6 Kh8-g8 Qg6-e6+ Kg8-h8 Re8-e7 Qc5-f2 Re7-d7) +2.29/8 0} Bg7
{(f6g7 f7g6 h8g8 f3f4 e5f4 g6h7 g8f7 e4g6) -1.65/8 0} 50. Qxg6 {(Qf7xg6
Kh8-g8 f3-f4 e5xf4 g3xf4 Qc5-f2 Qg6-e6+ Kg8-h8 Re8xf8+) +2.44/8 0} Kg8
{(h8g8 e8f8 c5f8 g6b6 f8b4 b6e6 g8h8 e6e8) -1.85/8 0} 51. f4 {(f3-f4 e5xf4
g3xf4 Qc5-d4 Qg6-e6+ Kg8-h8 Re8xf8+ Bg7xf8 Qe6-e8 Kh8-g7) +2.50/8 0} exf4
{(e5f4 g3f4 f8e8 g6e8 g7f8 e8e6 g8h8 e6e5) -1.60/8 0} 52. gxf4 {(g3xf4
Qc5-d4 f4-f5 Rf8xe8 Qg6xe8+ Bg7-f8 Qe8-e6+ Kg8-g7 Qe6-g6+ Kg7-h8 Be4-c6)
+2.54/8 0} Rxe8 {(f8e8 g6e8 c5f8 e4d5 g8h7 e8f8 g7f8 h2g3) -1.80/8 0} 53.
Qxe8+ {(Qg6xe8+ Qc5-f8 Qe8-e6+ Kg8-h8 Kh2-g3 h6-h5 Be4-c6 Qf8-a3+ Kg3-h4
Qa3-c1 Kh4-g5) +2.32/8 0} Qf8 {(c5f8 e4d5 g8h7 e8f8 g7f8 h2g3 h7g6 g3f3)
-1.75/8 0} 54. Qe6+ {(Qe8-e6+ Kg8-h8 f4-f5 Bg7-d4 g2-g3 Qf8-f6 Qe6-e8+
Kh8-g7 Qe8-g6+ Kg7-h8 Be4-d5) +2.31/8 0} Kh8 {(g8h8 e4f5 f8b8 e6c8 b8c8
f5c8 g7d4 h2g3) -1.50/8 0} 55. f5 {(f4-f5 Bg7-d4 Be4-d5 Kh8-h7 g2-g3 Kh7-h8
Kh2-g2 Qf8-f6) +2.57/8 0} Qd8 {(f8d8 h2h3 d8f8 e4c6 f8b4 e6e8 g7f8 f5f6)
-1.45/8 0} 56. Kh3 {(Kh2-h3 Qd8-f8 Be4-d5 Bg7-d4 g2-g3 Qf8-g7 Qe6-e8+
Kh8-h7 Kh3-g2) +2.71/8 0} Qf8 {(d8f8 e6a6 f8a3 g2g3 a3b4 a6b7 b4c5 b7b8)
-1.50/8 0} 57. g3 {(g2-g3 Bg7-d4 Be4-d5 Kh8-h7 Qe6-g6+ Kh7-h8 Kh3-g4 Qf8-f6
Qg6xf6+) +2.63/8 0} Bf6 {(g7f6 h3g2 f8d8 e6d5 d8c7 d5a8 f6d8 g2h1) -1.55/8
0} 58. Bd5 {(Be4-d5 Qf8-g7 g3-g4 Bf6-c3 Qe6-g6 Bc3-e5 Kh3-g2 Qg7-f6)
+2.47/8 0} Kh7 {(h8h7 h3h2 h7h8 h2g1 f6g7 g1h1 g7d4 d5e4) -1.47/8 0} 59.
Qb6 {(Qe6-b6 Qf8-d8 Qb6xd8 Bf6xd8 Kh3-g4 Bd8-e7 Kg4-f4 Be7-c5) +2.39/8 0}
Bd8 {(f6d8 b6g6 h7h8 g6f7 f8f7 d5f7 h8g7 f7d5) -1.45/8 0} 60. Qg6+
{(Qb6-g6+ Kh7-h8 Kh3-g4 Bd8-g5 Qg6-b6 Qf8-b4+ Qb6xb4 a5xb4 a4-a5 Kh8-g7)
+2.81/8 0} Kh8 {(h7h8 d5e4 d8f6 h3g2 f8g7 g6g7 h8g7 e4d5) -1.65/8 0} 61.
Kg4 {(Kh3-g4 Bd8-f6 Kg4-h5 Bf6-g5 Qg6-e6 Kh8-h7 Kh5-g4 Qf8-c5) +2.69/8 0}
Bg5 {(d8g5 d5c6 f8c5 g4h3 c5f2 g6e8 h8h7 c6e4) -1.32/8 0} 62. Kh5 {(Kg4-h5
Qf8-c8 Qg6-e6 Qc8xe6 f5xe6 Kh8-g7 Bd5-e4 Bg5-f6) +2.83/8 0} Qc8 {(f8c8 d5c6
c8b8 g6e8 b8e8 c6e8 h8g7 h5g4) -1.35/8 0} 63. g4 {(g3-g4 Qc8-f8 f5-f6
Bg5xf6 Qg6xh6+ Qf8xh6+ Kh5xh6 Bf6-a1 g4-g5 Ba1-d4) +2.85/8 0} Qb8 {(c8b8
g6c6 b8f8 c6c3 h8h7 c3e5 f8d8 e5d4) -1.15/8 0} 64. Qf7 {(Qg6-f7 Bg5-f4
Qf7-f6+ Kh8-h7 Qf6-e7+ Kh7-h8 f5-f6 Bf4-d6 Qe7-f7) +3.45/7 0} Bf4 {(g5f4
f7f6 h8h7 f6e7 h7h8 f5f6 b8e5 e7e5) -2.35/8 0} 65. Kg6 {(Qf7-f6+ Kh8-h7
Qf6-e7+ Kh7-h8 f5-f6 Qb8-e5+ Qe7xe5 Bf4xe5 f6-f7 Kh8-h7) +3.98/7 0} Qb6+
{(b8b6 d5e6 b6e6 f5e6 f4e3 f7g7) -M3/8 0} 66. Be6 {(Bd5-e6 Qb6xe6+ f5xe6)
+M500/8 0} Qxe6+ {(b6e6 f5e6 f4e3 f7g7) -M2/8 0} 67. fxe6 {(f5xe6) +M500/8
0} Be3 {(f4e3 f7g7) -M1/8 0} 68. Qh7# {(Qf7-h7+) +M500/8 0} 1-0
[/pgn]

I have to mention, my evaluation is not very advanced yet, i'm only doing PeSTo tables and tapered evaluation mostly, combined with basic mobility and very basic king safety.

[pedrojdm2021]

For search features i have:
- PVS (Principal variation search)
- Null move pruning
- Mate distance pruning
- Late move reductions
- Delta pruning in QS
- Futility Pruning

To reduce nodes you could add: 'beta pruning', 'alpha pruning' and 'late move pruning'.

Thanks, i'm going to do a research for these features

[Mike Sherwin]

Hello! i hope you all are doing great.

I'm currently trying to improve my engine search, one of the most important points that i have to work is to reduce the number of moves searched:
This is for depth 9 and "kiwipete" position:

Code: Select all

info depth 9 time 1873 nodes 1783749 score cp -64 pv e2a6 e6d5 e5g6 f7g6 c3b5 d5e4 b5c7 e8d8 f3g3 h3g2
bestmove e2a6

You can see that it took 1.8 seconds, and more than 1.7 million nodes to complete the search, for me that is too much, as i've seen engines that is searching less than 100.000 for the same position and the same depth

Looking at the code from other engines like Demolito, i see that they are using some advanced move ordering stuff, i undestand that move ordering is so important to have the shortest and optimal search.

I currently have a very basic move ordering:

1) PV Move
2) Captures via MVV/LVA
3) Killers (first killer and second killer)
4) History Heuristic

For search features i have:
- PVS (Principal variation search)
- Null move pruning
- Mate distance pruning
- Late move reductions
- Delta pruning in QS
- Futility Pruning

I see that these engines are using mostly follow up history, refutation history, and Counter-move heuristic

So i decide to begin with Counter move heuristic, as is the one that looks more simpler than the others, and the one that i've found most documentation.

The problem that i'm facing right now with CounterMove is that i don't understand it very clearly the idea.

I've found This post:
http://www.talkchess.com/forum3/viewtop ... =7&t=72531

But i don't get it completly. They are talking in the comments that counter move heuristic is based in the "Previous Move" , like for an oponent response, as i understand a "previous move" is the move that was played BEFORE the current move in the move loop inside the search loop, right?

If yes, how can i score the moves ? I mean in the score_moves() function should i get the previous move ( i - 1) and pass it as parameter to the get_move_score() function?

As for the others, what are exactly the similitudes between each of them?

if anyone could give some sample code, would be great.

i tried to compare and do the stuff as i understood at the moment:

Code: Select all

// beta cut-off
if (score >= _beta)
{
	// update killer moves
	if (!mflag.Is_Capture())
	{
			killer_moves[1][ply] = killer_moves[0][ply];
			killer_moves[0][ply] = current_move;
	}

	// update counter move history
	MoveFlag prev_flag = MoveUtility.Get_flag(prev_move);
	if (prev_move != 0 && !prev_flag.Is_Capture())
	{
		byte prev_from = MoveUtility.Get_square_from(prev_move);
		byte prev_to = MoveUtility.Get_square_to(prev_move);
		countermove_history[prev_from][prev_to] = prev_move;
	}

		transposition.Store(ply, board.hash, TTFlag.BETA, score, _depth);
		return _beta;
	}

and in my move Score function:

Code: Select all

private static int GuessMoveScore(ushort _move , ushort _prev_move)
{
	int score = 0;

	if (score_pv && pv_table[0][ply] == _move)
	{
		score_pv = false;
		score += 40000;
	}

	MoveFlag flag = MoveUtility.Get_flag(_move);
	byte sq_from = MoveUtility.Get_square_from(_move);
	byte sq_to = MoveUtility.Get_square_to(_move);
			
			

	if (flag.Is_Capture())
	{
		byte attacker = board.boardPieces[sq_from];
		byte victim = board.boardPieces[sq_to];
		//apply lookup to the MVV/LVA Table   
		score += mvv_lva[attacker][victim] + 30000;

		// int see_value = see(_move);
		// return see_value + 20000;
	}
	else
	{
		if (killer_moves[0][ply] == _move)
			score += 9000;
		else if (killer_moves[1][ply] == _move)
			score += 8000;
		else
			score += history_moves[board.sideToMove][sq_from][sq_to];
				
		byte prev_from = MoveUtility.Get_square_from(_prev_move);
		byte prev_to = MoveUtility.Get_square_to(_prev_move);
		if (_prev_move != 0 && countermove_history[prev_from ][prev_to ] == _move)
			score += 5000;
	}
	
	return score;
}

but it does not take any effect in the move ordering. The search numbers are the same.

I did another test in instead of prev. move, i used the current move, and the differences were minimal, so probably i'm doing something wrong, or everything wrong

Thank you for your time, i'll appreciate all the help

I have trouble also with this. When my engine RomiChess first came out, june 2005, it was the deepest searching engine that I was aware of. Now OliThink searches deeper faster. And of course SF depth is incredible. But why? I have not been able to figure it out.

FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

RomiChess64P3n:
1 00:00 3k 3k +2.01 e2a6
2 00:00 4k 4k +2.21 e2a6
3 00:00 5k 5k +1.79 e2a6 b4c3 d2c3
4 00:00 9k 9k +1.79 e2a6 b4c3 d2c3
5 00:00 18k 18k +1.79 e2a6 b4c3 d2c3 h3g2 f3g2
6 00:00 59k 5,944k +1.31 e2a6 b4c3 d2c3 e6d5 e4d5
7 00:00 136k 6,775k +1.16 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2
8 00:00 253k 8,419k +1.16 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 d5e4
9 00:00 541k 7,721k +0.87 e2a6 e6d5 c3d5 b6d5 a6b7 h3g2 f3g2 a8b8 b7d5
10 00:00 1,055k 8,788k +0.87 e2a6 e6d5 c3d5 b6d5 a6b7 h3g2 f3g2 a8b8 b7d5
11 00:00 1,883k 8,557k +0.74 e2a6 e6d5 c3d5 b6d5 a6b7 h3g2 f3g2 a8b8 b7d5 f6d5 e5c4
12 00:00 3,541k 8,637k +0.75 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 a6b7 f6e4 c3g7
13 00:00 7,730k 8,494k +0.25 e2a6
14 00:01 10,943k 8,354k +0.49 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 a6b7 a8e8 c3f6 g7f6 g4f6
15 00:02 19,265k 8,487k +0.22 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 g4f6 g7f6 c3f6 e7f6 a1b1 d5e4 g2e4 g8h7
16 00:04 37,241k 8,426k -0.02 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 g4f6 g7f6 c3f6 e7f6 a1b1 f6e5 a6b7 a8e8 f2f3
17 00:10 90,152k 8,324k -0.27 d5e6 e7e6

[pedrojdm2021]

Hello! i hope you all are doing great.

I'm currently trying to improve my engine search, one of the most important points that i have to work is to reduce the number of moves searched:
This is for depth 9 and "kiwipete" position:

Code: Select all

info depth 9 time 1873 nodes 1783749 score cp -64 pv e2a6 e6d5 e5g6 f7g6 c3b5 d5e4 b5c7 e8d8 f3g3 h3g2
bestmove e2a6

You can see that it took 1.8 seconds, and more than 1.7 million nodes to complete the search, for me that is too much, as i've seen engines that is searching less than 100.000 for the same position and the same depth

Looking at the code from other engines like Demolito, i see that they are using some advanced move ordering stuff, i undestand that move ordering is so important to have the shortest and optimal search.

I currently have a very basic move ordering:

1) PV Move
2) Captures via MVV/LVA
3) Killers (first killer and second killer)
4) History Heuristic

For search features i have:
- PVS (Principal variation search)
- Null move pruning
- Mate distance pruning
- Late move reductions
- Delta pruning in QS
- Futility Pruning

I see that these engines are using mostly follow up history, refutation history, and Counter-move heuristic

So i decide to begin with Counter move heuristic, as is the one that looks more simpler than the others, and the one that i've found most documentation.

The problem that i'm facing right now with CounterMove is that i don't understand it very clearly the idea.

I've found This post:
http://www.talkchess.com/forum3/viewtop ... =7&t=72531

But i don't get it completly. They are talking in the comments that counter move heuristic is based in the "Previous Move" , like for an oponent response, as i understand a "previous move" is the move that was played BEFORE the current move in the move loop inside the search loop, right?

If yes, how can i score the moves ? I mean in the score_moves() function should i get the previous move ( i - 1) and pass it as parameter to the get_move_score() function?

As for the others, what are exactly the similitudes between each of them?

if anyone could give some sample code, would be great.

i tried to compare and do the stuff as i understood at the moment:

Code: Select all

// beta cut-off
if (score >= _beta)
{
	// update killer moves
	if (!mflag.Is_Capture())
	{
			killer_moves[1][ply] = killer_moves[0][ply];
			killer_moves[0][ply] = current_move;
	}

	// update counter move history
	MoveFlag prev_flag = MoveUtility.Get_flag(prev_move);
	if (prev_move != 0 && !prev_flag.Is_Capture())
	{
		byte prev_from = MoveUtility.Get_square_from(prev_move);
		byte prev_to = MoveUtility.Get_square_to(prev_move);
		countermove_history[prev_from][prev_to] = prev_move;
	}

		transposition.Store(ply, board.hash, TTFlag.BETA, score, _depth);
		return _beta;
	}

and in my move Score function:

Code: Select all

private static int GuessMoveScore(ushort _move , ushort _prev_move)
{
	int score = 0;

	if (score_pv && pv_table[0][ply] == _move)
	{
		score_pv = false;
		score += 40000;
	}

	MoveFlag flag = MoveUtility.Get_flag(_move);
	byte sq_from = MoveUtility.Get_square_from(_move);
	byte sq_to = MoveUtility.Get_square_to(_move);
			
			

	if (flag.Is_Capture())
	{
		byte attacker = board.boardPieces[sq_from];
		byte victim = board.boardPieces[sq_to];
		//apply lookup to the MVV/LVA Table   
		score += mvv_lva[attacker][victim] + 30000;

		// int see_value = see(_move);
		// return see_value + 20000;
	}
	else
	{
		if (killer_moves[0][ply] == _move)
			score += 9000;
		else if (killer_moves[1][ply] == _move)
			score += 8000;
		else
			score += history_moves[board.sideToMove][sq_from][sq_to];
				
		byte prev_from = MoveUtility.Get_square_from(_prev_move);
		byte prev_to = MoveUtility.Get_square_to(_prev_move);
		if (_prev_move != 0 && countermove_history[prev_from ][prev_to ] == _move)
			score += 5000;
	}
	
	return score;
}

but it does not take any effect in the move ordering. The search numbers are the same.

I did another test in instead of prev. move, i used the current move, and the differences were minimal, so probably i'm doing something wrong, or everything wrong

Thank you for your time, i'll appreciate all the help

I have trouble also with this. When my engine RomiChess first came out, june 2005, it was the deepest searching engine that I was aware of. Now OliThink searches deeper faster. And of course SF depth is incredible. But why? I have not been able to figure it out.

FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

RomiChess64P3n:
1 00:00 3k 3k +2.01 e2a6
2 00:00 4k 4k +2.21 e2a6
3 00:00 5k 5k +1.79 e2a6 b4c3 d2c3
4 00:00 9k 9k +1.79 e2a6 b4c3 d2c3
5 00:00 18k 18k +1.79 e2a6 b4c3 d2c3 h3g2 f3g2
6 00:00 59k 5,944k +1.31 e2a6 b4c3 d2c3 e6d5 e4d5
7 00:00 136k 6,775k +1.16 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2
8 00:00 253k 8,419k +1.16 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 d5e4
9 00:00 541k 7,721k +0.87 e2a6 e6d5 c3d5 b6d5 a6b7 h3g2 f3g2 a8b8 b7d5
10 00:00 1,055k 8,788k +0.87 e2a6 e6d5 c3d5 b6d5 a6b7 h3g2 f3g2 a8b8 b7d5
11 00:00 1,883k 8,557k +0.74 e2a6 e6d5 c3d5 b6d5 a6b7 h3g2 f3g2 a8b8 b7d5 f6d5 e5c4
12 00:00 3,541k 8,637k +0.75 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 a6b7 f6e4 c3g7
13 00:00 7,730k 8,494k +0.25 e2a6
14 00:01 10,943k 8,354k +0.49 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 a6b7 a8e8 c3f6 g7f6 g4f6
15 00:02 19,265k 8,487k +0.22 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 g4f6 g7f6 c3f6 e7f6 a1b1 d5e4 g2e4 g8h7
16 00:04 37,241k 8,426k -0.02 e2a6 b4c3 d2c3 e6d5 e5g4 h3g2 f3g2 e8g8 g4f6 g7f6 c3f6 e7f6 a1b1 f6e5 a6b7 a8e8 f2f3
17 00:10 90,152k 8,324k -0.27 d5e6 e7e6

Check if you have at least principal variation search, null move pruning and Late Move Reductions, i think these are a must.

Also, delta pruning in quiescense search helped me to prune considerable ammount of nodes.

But as i've said, i need more optimizations, my target is to have a engine that searches about 300-500k nodes for depth 9 - 10, why? because i'm making a chess game for mobile devices in C# and Unity. that's the main reason.

[Mergi]

Depth and node count is a lie. I wouldn't worry about trying to implement new features, as you seem to have plenty enough already. Now it's all about optimizing those that you already have and pruning as aggresivelly as possible. This is especially true when it comes to things like late move reductions - there's a huge potential to cut a lot of nodes besides just the classic -1 depth, if you are brave enough.

It also seems like your depth 9 output gives 10 PV moves. You seem to be possibly doing some extra work.