Scan

[BertTuyt]

So at depth=0, what do you do here? Return eval() or try 27-21 and 27-22?

For Damage this is a Database Win

Bert

[Fabien Letouzey]

So at depth=0, what do you do here? Return eval() or try 27-21 and 27-22?

I return eval() if it fails high, otherwise try the two moves.

[BertTuyt]

To my knowledge this is exactly what Michel is doing, so it's certainly possible. I didn't carefully think about it because I assumed that:
1) bitboards would only easily allow base-4 indices instead of base 3. For 8 squares already this would waste 90% of the index space, not to mention larger patterns.
2) bitboards would "prefer" regularly-spaced, identically-shaped patterns. While this is what I have now, I preferred not to commit to such a design at an early stage.

Of course that was just intuition. I might be wrong on both counts.

I'm not sure I see the real problem.
Basically I was also thinking about a method in line what Michel proposed.
In the meantime I have tried to modify the Scan code slightly so the index function doesn't need the bd.trit, and I checked if the 2 approaches yield the same answer (and so far they seem to be alike)

So first i define some constants to make the program more readable. For a snapshot see below.

Code: Select all

// Board Squares
#define SFLD1		6
#define SFLD2		7
#define SFLD3		8
#define SFLD4		9
#define SFLD5		10
#define SFLD6		11
#define SFLD7		12
#define SFLD8		13
#define SFLD9		14
#define SFLD10		15
#define SFLD11		17
...................................
#define SFLD50		59

Then I slightly changed the eval_float()

Code: Select all

 value1 += Weight[4 + 0 * 6561 + i9(bd, SFLD1, SFLD2, SFLD6, SFLD7, SFLD11, SFLD12, SFLD16, SFLD17)];
   value1 += Weight[4 + 1 * 6561 + i9(bd, SFLD2, SFLD3, SFLD7, SFLD8, SFLD12, SFLD13, SFLD17, SFLD18)];
   value1 += Weight[4 + 2 * 6561 + i9(bd, SFLD3, SFLD4, SFLD8, SFLD9, SFLD13, SFLD14, SFLD18, SFLD19)];
   value1 += Weight[4 + 3 * 6561 + i9(bd, SFLD4, SFLD5, SFLD9, SFLD10, SFLD14, SFLD15, SFLD19, SFLD20)];
   value1 += Weight[4 + 4 * 6561 + i9(bd, SFLD11, SFLD12, SFLD16, SFLD17, SFLD21, SFLD22, SFLD26, SFLD27)];
   value1 += Weight[4 + 5 * 6561 + i9(bd, SFLD12, SFLD13, SFLD17, SFLD18, SFLD22, SFLD23, SFLD27, SFLD28)];
   value1 += Weight[4 + 6 * 6561 + i9(bd, SFLD13, SFLD14, SFLD18, SFLD19, SFLD23, SFLD24, SFLD28, SFLD29)];
   value1 += Weight[4 + 7 * 6561 + i9(bd, SFLD14, SFLD15, SFLD19, SFLD20, SFLD24, SFLD25, SFLD29, SFLD30)];
   value1 += Weight[4 + 8 * 6561 + i9(bd, SFLD21, SFLD22, SFLD26, SFLD27, SFLD31, SFLD32, SFLD36, SFLD37)];
   value1 += Weight[4 + 9 * 6561 + i9(bd, SFLD22, SFLD23, SFLD27, SFLD28, SFLD32, SFLD33, SFLD37, SFLD38)];
   value1 += Weight[4 + 10 * 6561 + i9(bd, SFLD23, SFLD24, SFLD28, SFLD29, SFLD33, SFLD34, SFLD38, SFLD39)];
   value1 += Weight[4 + 11 * 6561 + i9(bd, SFLD24, SFLD25, SFLD29, SFLD30, SFLD34, SFLD35, SFLD39, SFLD40)];
   value1 += Weight[4 + 12 * 6561 + i9(bd, SFLD31, SFLD32, SFLD36, SFLD37, SFLD41, SFLD42, SFLD46, SFLD47)];
   value1 += Weight[4 + 13 * 6561 + i9(bd, SFLD32, SFLD33, SFLD37, SFLD38, SFLD42, SFLD43, SFLD47, SFLD48)];
   value1 += Weight[4 + 14 * 6561 + i9(bd, SFLD33, SFLD34, SFLD38, SFLD39, SFLD43, SFLD44, SFLD48, SFLD49)];
   value1 += Weight[4 + 15 * 6561 + i9(bd, SFLD34, SFLD35, SFLD39, SFLD40, SFLD44, SFLD45, SFLD49, SFLD50)];

Introduced a new i9 index routine.

Code: Select all

static int i9(const Board & bd, int s0, int s1, int s2, int s3, int s4, int s5, int s6, int s7) {

	bit_t blackman = bd.bit(BM_INDEX), empty = Bit_Squares ^ ( bd.bit(WM_INDEX) | blackman);

	return ((((((((
		bdtrit(s0, blackman, empty)) * 3 +
		bdtrit(s1, blackman, empty)) * 3 +
		bdtrit(s2, blackman, empty)) * 3 +
		bdtrit(s3, blackman, empty)) * 3 +
		bdtrit(s4, blackman, empty)) * 3 +
		bdtrit(s5, blackman, empty)) * 3 +
		bdtrit(s6, blackman, empty)) * 3 +
		bdtrit(s7, blackman, empty));
}

And a inline definition for bdtrit

Code: Select all

inline int bdtrit(int square, bit_t blackman, bit_t empty) {
	bit_t bitsquare = (bit_t)1 << square;
	if (bitsquare & blackman) return (2);
	else if (bitsquare & empty) return (1);
	else return (0);
}

And so far it seems to work.

Bert

[Fabien Letouzey]

And a inline definition for bdtrit

Of course, bdtrit is rigorously equivalent to my trit array. It was actually on my Todo list for a while. But I assumed it would be too slow, given the large number of times I need it. Do you have any hard figure? If not fast enough, it's also possible to make it branchless I think; not my cup of tea though.

[BertTuyt]

Fabien, it seems 40% slower , which surprised me as this is a lot.
I'm not sure what the remaining (more optimized) time is if also the bd.trit updates are removed.
Anyway i will have another quick look, if i can make it ( a little) faster.
I also don't like the code as it, so the Michel approach might be better in the end.
However i also believe that a 100% bitboard implementation in the end should be comparable or faster.

Bert

[BertTuyt]

Herewith a screenshot of the VS Profiler Output (with the i9).
Also the Q-search takes remarkably much time.

Bert

[Fabien Letouzey]

Anyway i will have another quick look, if i can make it ( a little) faster.

I have a feeling that a branchless version would be significantly "less slow", perhaps "only" 10-20% slower. Imagine that W and B are 0/1 booleans indicating a white (resp. black) piece on a given square. Then B - W + 1 is what we want. Actually I'm now using -1/0/+1 trits instead of 0/1/2 so it's even easier.

[Rein Halbersma]

So at depth=0, what do you do here? Return eval() or try 27-21 and 27-22?

I return eval() if it fails high, otherwise try the two moves.

Why? Is your definition of "quiescent" that no exchanges are possible? I would expect that to give very large QS trees, especially as you apply this recursively. E.g. in this position


White to move

So, depending on the search bounds, would your QS fully explore

Code: Select all

1. 32-27 21x32
2. 38x27 18-22
3. 27x18 13x22
4. 33-28 22x33
5. 39x28 19-23
6. 28x19 14x23
7. 34-29 23x34
8. 40x29 20-24
9. 29x20 15x24

White to move

before returning eval()?

[Fabien Letouzey]

Why? Is your definition of "quiescent" that no exchanges are possible? I would expect that to give very large QS trees, especially as you apply this recursively.

It's probably only a vocabulary issue but I don't think in terms of what is quiescent or not. Instead I focus on what I can do to improve my position (in a drastic way) when the score is bad. And my answer in QS is "try exchanges", recursively.

Regarding the tree-size explosion, it seems that it simply doesn't occur in practice. I would remember if depth "significantly" went down during testing.

So, depending on the search bounds, would your QS fully explore ... before returning eval()?

I guess so, IF the score precisely dances around beta after each exchange.

[Rein Halbersma]

Why? Is your definition of "quiescent" that no exchanges are possible? I would expect that to give very large QS trees, especially as you apply this recursively.

It's probably only a vocabulary issue but I don't think in terms of what is quiescent or not. Instead I focus on what I can do to improve my position (in a drastic way) when the score is bad. And my answer in QS is "try exchanges", recursively.

Ok, I think I understand your reasoning that it requires a very intricate dance around small score window to generate long exchange sequences forboth sides. But after I move-you-take my score has dropped even more, so then your QS would presumably go on to sacrifice even more material in hope of a big counter-combination, is that correct?

Did you ever try only extending pending captures or threatened captures? Evidently your search is very good, but it sounds counter-intuitive to me to try exchanges in QS when it is not forced, instead of quickly terminating and calling eval.

For me QS means, depth<=0 and resources are up: capture if you must, promote if you can and call eval otherwise. After all, the next iteration of the regular search will initiate the exchange anyway, so you won't miss any tactics, just delay them one iteration. I understand it's a tradeoff in practice

[Rein Halbersma]

Fabien, in this older thread, there was a similar discussion on QS exchanges with your compatriot Gérard Taille. I would be interested to learn how quickly Scan sees these difficult tactics posted there. (It can wait until you released Scan of course, just curious again!)

[Fabien Letouzey]

Ok, I think I understand your reasoning that it requires a very intricate dance around small score window to generate long exchange sequences forboth sides. But after I move-you-take my score has dropped even more, so then your QS would presumably go on to sacrifice even more material in hope of a big counter-combination, is that correct?

I don't understand where the sacrifice is coming from. My definition of "exchange" is: I move, he takes, I take (3 plies). The special move generator makes sure that I will be able to capture on the 3rd ply.

Let's assume that my opponent cannot capture on the 4th ply; I would expect this to happen > 50% of the time. Then I lose the initiative, my opponent can do whatever. Therefore, for me, "my score has dropped even more" has no bearing as it's not even my turn anymore. It's my opponent's turn to worry about his score and position.

Did you ever try only extending pending captures or threatened captures? Evidently your search is very good, but it sounds counter-intuitive to me to try exchanges in QS when it is not forced, instead of quickly terminating and calling eval.

Maybe "pending" is what I call a "pin"? I move a piece, and this allows the opponent to capture another one I was defending? No I haven't tried it. I assumed most would be bad in random positions (contrary to exchanges). Probably some restrictions should be added. I also assumed that "pins" would be rarer than exchanges, especially interesting ones.

"Threatened" I guess is the opponent captures. I tried extending 1 ply (= forbidding standing pat), possibly only in restricted cases; no improvement. I didn't insist on this front though, despite the "double quiescence" from Buggy which sounds a bit mysterious to me (no captures for either player?).

I do call eval first. However my position might actually be good, just not statically. The last step of a combination is usually in this case.

For me QS means, depth<=0 and resources are up: capture if you must, promote if you can and call eval otherwise. After all, the next iteration of the regular search will initiate the exchange anyway, so you won't miss any tactics, just delay them one iteration. I understand it's a tradeoff in practice

I think that's it, we just view QS differently. For me, QS is what you make it. In the 90's when everybody was extending tactical moves, it makes sense to reduce it to a minimum. But remember that I prune a lot, so I'd rather have some tactical safety at low depth. Static eval doesn't take that into account because I filter out capture positions during learning.

If still confused, I suggest you ask HGM for help. He is the king of QS and has much more experience than me on this subject in part due to Shogi. For all I know, he might agree with you.

[Fabien Letouzey]

I would be interested to learn how quickly Scan sees these difficult tactics posted there.

It's not clear to me what positions you have in mind in this large thread. Show me some FENs and I'll make it happen. Note though that I don't view Scan as a tactical engine.

[Rein Halbersma]

I would be interested to learn how quickly Scan sees these difficult tactics posted there.

It's not clear to me what positions you have in mind in this large thread. Show me some FENs and I'll make it happen. Note though that I don't view Scan as a tactical engine.

Just Scan's search output to nominal depth=25 for


White to move

[Fabien Letouzey]

Just Scan's search output to nominal depth=25 for


White to move

4/ 6.4 -2 1482 0.00 0.00 48-42 5-10 39-33 19-23
5/ 7.7 -1 3780 0.00 0.00 48-42 5-10 39-33 19-23 41-36
5/ 7.0 +0 5779 0.00 0.00 39-33 19-23 35-30 23-28 44-39
6/ 8.6 +0 11378 0.00 0.00 39-33 5-10 44-39 27-31 48-42 19-23
7/ 9.5 -2 16603 0.00 0.00 39-33 5-10 44-39 20-24 29x20 25x14 35-30
8/ 9.6 +1 31193 0.01 0.00 39-33 5-10 44-39 10-14 47-42 27-31 29-24
8/10.0 +7 39982 0.01 0.00 48-42 5-10 29-24 19x30 35x24 20x29 34x23
9/11.4 -6 60027 0.01 0.00 48-42 5-10 29-24 19x30 35x24 20x29 34x23
9/11.0 +6 78509 0.01 0.00 39-33 5-10 44-39 10-14 48-42 20-24 29x20
10/11.4 +6 97284 0.02 0.00 39-33 5-10 44-39 10-14 48-42 20-24 29x20
11/12.0 +1 128668 0.02 0.00 39-33 5-10 44-39 10-14 48-42 20-24 29x20
12/13.5 -5 199221 0.04 0.00 39-33 5-10 44-39 10-14 47-42 27-31 29-24
12/13.7 +2 274653 0.05 0.00 48-42 5-10 29-24 19x30 35x24 20x29 34x23
12/14.9 +29 316075 0.06 0.00 29-24 19x30 35x24 20x29 34x23 18x29 37-31
13/17.8 +21 337385 0.06 0.00 29-24 19x30 35x24 20x29 34x23 18x29 37-31
14/19.9 +24 358968 0.06 0.00 29-24 19x30 35x24 20x29 34x23 18x29 37-31
15/19.6 +14 436818 0.08 0.00 29-24 19x30 35x24 20x29 34x23 18x29 37-31
16/21.1 +12 640511 0.12 5.51 29-24 19x30 35x24 20x29 34x23 18x29 37-31
17/20.1 +11 1647078 0.30 5.57 29-24 19x30 35x24 20x29 34x23 18x29 26-21
18/20.4 +10 2355143 0.42 5.55 29-24 19x30 35x24 20x29 34x23 18x29 26-21
19/22.2 +14 4398942 0.79 5.54 29-24 19x30 35x24 20x29 34x23 18x29 26-21
20/23.6 +11 7477888 1.36 5.51 29-24 19x30 35x24 20x29 34x23 18x29 26-21
21/23.1 +11 11017058 2.00 5.50 29-24 19x30 35x24 20x29 34x23 18x29 26-21
22/24.0 +10 16796345 3.06 5.50 29-24 19x30 35x24 20x29 34x23 18x29 26-21
23/24.4 +12 28383677 5.20 5.46 29-24 19x30 35x24 20x29 34x23 18x29 26-21
24/25.4 +16 64437601 11.77 5.47 29-24 19x30 35x24 20x29 34x23 18x29 37-31
25/28.2 +15 74572415 13.64 5.47 29-24 19x30 35x24 20x29 34x23 18x29 37-31

Score is in cp.