World Draughts Forum

It is currently Thu Dec 13, 2018 12:13

All times are UTC+01:00




Post new topic  Reply to topic  [ 162 posts ]  Go to page Previous 1 2 3 4 511 Next
Author Message
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 15:42 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Quote:
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 :D

Bert


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 15:51 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
Rein Halbersma wrote:
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 16:05 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Quote:
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:
// 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:
 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:
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:
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


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 16:30 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
BertTuyt wrote:
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 17:00 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 17:10 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith a screenshot of the VS Profiler Output (with the i9).
Also the Q-search takes remarkably much time.

Bert


Attachments:
Profile.png
Profile.png [ 29.21 KiB | Viewed 2626 times ]
Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 17:24 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
BertTuyt wrote:
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 19:27 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1609
Fabien Letouzey wrote:
Rein Halbersma wrote:
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

Image
White to move

So, depending on the search bounds, would your QS fully explore
Code:
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

Image
White to move

before returning eval()?


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 20:08 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
Rein Halbersma wrote:
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.

Quote:
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 20:34 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1609
Fabien Letouzey wrote:
Rein Halbersma wrote:
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 :)


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 20:51 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1609
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!)


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 21:23 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
Rein Halbersma wrote:
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.

Quote:
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.

Quote:
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 21:29 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
Rein Halbersma wrote:
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 21:43 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1609
Fabien Letouzey wrote:
Rein Halbersma wrote:
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

Image
White to move


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 21:55 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
Rein Halbersma wrote:
Just Scan's search output to nominal depth=25 for

Image
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.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 162 posts ]  Go to page Previous 1 2 3 4 511 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited