lithander wrote: ↑Mon Mar 01, 2021 8:07 pm
Mike Sherwin wrote: ↑Mon Mar 01, 2021 3:54 amWhen I wrote RomiChess the eval was done before Qsearch was written. It ran slow. The node rate was great but it did not search very deep at all. As soon as I added Qsearch it was the deepest single thread searcher that I knew of at the time of its release. Even today it is not bad.
But when you finally added QSearch you probably had not only a pretty good evaluation function but also several sophsticated pruning methods in addition to just alpha beta, right?
I have nothing but MVV-LVA implemented at this point which doesn't profit of a good the evaluation. Or should it? Could it...? I guess you could score a move by the difference in the static evaluation it causes instead of the MVV-LVA value of the captured peaces. It's worth a try.
You example of how a changing PV hurts the pruning of the following iteration requires something like history heuristics or a hashtable or something comparable? Otherwise, how would the previous PV be relevant to the AB search?
By now I think that I was a little early to implement QSearch and that it really unleashes it's power in combination with a very good eval *and* pruning techniques that rely on a very good evaluation and getting rid of the horizon effect. And I don't have these, yet.
For Context:
The current development branch of my engine is basically having the same features as Rustic Alpha. For the upcoming release of version 0.3 I'm trying to implement all features suggested by Marcel and Sven in
this thread as essential for a minimal engine.
- Board representation
- Move generator
- Alpha/Beta search
- QSearch
- MVV-LVA move sorting
- Evaluation: Material count and PST
- Iterative deepening
- Time controls
The bold things are features that were not present in version 0.2 (1050 ELO on CCRL) and that I'm adding right now. I'm just trying to make sure there are no bugs hidden in there but for that assessment I need to form realistic expectations of what these features, correctly implemented, should do for me. I think I can expect 1500-1600 ELO? (My move generator is very simple and thus a little slow) But the depths RomiChess64P3n achieves on the startpositon are waaaaaay out of reach in my situation, I think. With the above listed features 7-8 plys in one secodn of computation is a more realistic goal, or what would you say?
Every Engine has its own peculiarities. Just the order in which moves are generated can affect all sorts of things. I don't know if you are aware but I have an engine at about the same point of development as yours and Marcel's called Bricabrac. Let's compare list.
- Board representation - yes
- Move generator - yes
- Alpha/Beta search -yes
- QSearch - yes
- MVV-LVA move sorting - yes
- Evaluation: Material count and PST - yes
- Iterative deepening - yes
- Time controls
- yes (just seconds per move so far)
Bric also has of yesterday Principle variation search using the pvs[ply][ply] and pvl[ply] triangular array. This allows the principle variation to be searched and displayed. That is the extent of Bric right now. Just added the zero window part of pvs search. Running test against TSCP1.81 is so far Bric +2, -1, =5. Some of those draws are 3 fold reps in which Bric had a winning position. Three fold rep is next on the todo list. Then Bric will be a minimal engine in my opinion.
So you are aiming for 7 to 8 ply. In how long? I'll do a 60 second search of the original position with Bric as it is now, brb. Okay back.
FEN: rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b KQkq d3 0 1
Bricabrac:
1 00:00 20 20 +0.36 g1f3
2 00:00 87 87 0.00 g1f3 g8f6
3 00:00 701 701 +0.35 g1f3 g8f6 d2d4
4 00:00 4k 4k 0.00 g1f3 g8f6 d2d4 d7d5
5 00:00 9k 9k +0.33 g1f3 g8f6 d2d4 d7d5 b1c3
6 00:00 16k 16k 0.00 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6
7 00:00 59k 59k +0.28 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6 c1e3
8 00:00 197k 19,684k 0.00 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6 c1e3 c8e6
9 00:00 3,094k 9,981k +0.29 e2e4 b8c6 g1f3 g8f6 b1c3 d7d5 e4d5 f6d5 d2d4
10 00:00 5,071k 10,142k +0.09 e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 f8d6
11 00:14 144,410k 9,959k +0.23 d2d4 d7d5 g1f3 b8c6 b1c3 g8f6 c1f4 c8e6 e2e3 f6e4 f1d3
12 00:19 204,401k 10,707k +0.02 d2d4 d7d5 g1f3 g8f6 b1c3 c8f5 c1e3 b8c6 f3e5 f6e4 c3e4 c6e5
13 00:35 365,906k 10,244k +0.25 d2d4 d7d5 g1f3 b8c6 b1c3 c8f5 c1f4 g8f6 e2e3 f6e4 c3e4 f5e4 f1d3
Ply 14 was started but did not finish in time. So bric finished ply 13 in 35 seconds. PVS adds a ply or maybe more. Maybe someone else can tell us how much. Anyway, your 7 to 8 ply expectation is very conservative. I do have one move ordering trick that I use in my engines that others do not use. And the idea has been extended in Bric but I don't know if the extension is any good. So to answer the question, I think that you can raise your expectations just a bit.
Bric's search function.
Code: Select all
s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
s32 mi, j, count = 0, goodness = 0;
u64 n;
Move* mov;
if (depth == 0) return Qsearch(t, m, alpha, beta);
if (clock() > end) return alpha;
pvl[ply] = ply;
n = GenMoves(t, m);
if (!n) return -ILLEGAL;
if (depth > 3) {
for (mi = 0; mi < n; mi++) {
mov = m + mi;
MakeMove(t, mov);
mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
TakeBack(t, mov);
goodness += (move->score >= beta);
}
}
if (fpv) {
for (mi = 0; mi < n; mi++) {
mov = m + mi;
if (mov->fs == pvs[0][ply].fs && mov->ts == pvs[0][ply].ts && mov->type == pvs[0][ply].type) {
mov->score = 1000000;
break;
}
}
}
for (mi = 0; mi < n; mi++) {
Sort(t, m, mi, n);
mov = m + mi;
MakeMove(t, mov);
if (goodness && mov->score >= beta) {
mov->score = -Search(t, m + n, -beta, -beta + 1, depth - 3);
if (mov->score < beta)
mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
}
else {
if (fpv) {
mov->score = -Search(t, m + n, -alpha - 1, -alpha, depth - 1);
if (m->score > alpha) mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
}
else {
mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
}
}
TakeBack(t, mov);
fpv = false;
if (mov->score == ILLEGAL) continue;
count++;
if (mov->score > alpha) {
if (mov->score >= beta) return beta;
alpha = mov->score;
pvs[ply][ply] = *mov;
for (j = ply + 1; j < pvl[ply + 1]; j++) pvs[ply][j] = pvs[ply + 1][j];
pvl[ply] = pvl[ply + 1];
}
}
if (!count) {
if (InCheck[wtm](t, king[wtm])) {
return -(MATE - ply);
}
else return STALEMATE;
}
return alpha;
}