Computer Draughts 2012

[TAILLE]

Hi Rein,

I have several questions concerning the building of this diagram but let's begin by two basic ones:
1) How do you decide to assign square 16 to white?
2) Will the calculation of this diagram change if, in the original position, I move the white man on square 43 to the square 44 as in the following diagram:

1) White can reach square 16 in 2 moves (27-21-16) and black only in 3 (1-7-11-16), so 16 is assigned to white. If Black would have 1 on 7 already, 16 would be neutral, if 1 was on 11 already, 16 would be assigned to black. As soon as black actually reaches 16 in the search, square 21 becomes neutral (both white and black have 2 pieces adjacent to it).
2) The answer is "no", but I know it should be "yes". This is a weakness in the current algorithm.
Rein

Your implementation is now very clear for me and obviously you know perfectly its weaknesses!

How does your algorithm assign square 16 to black? Does it "see" that white cannot safely do 27-21-16?
Rein

In my approach, and taking the white point of view, I consider that any white move (except a move towards the edge, like 30-25 or 21-16) towards the half upper part of the board is dangerous. The move 27-21 is then assumed unsafe and, as a consequence, square 21 is neutral and square 16 is a black one.
In order to give square 21 to white I have to wait for the move 27-21 in the dynamic search.

Generally, there are several things that needs to be resolved to make this algorithm work:

1) determining whether a square can be "safely" reached first by a color: I use parallel bitshifts and majority rule to determine that
2) translating reachable squares to the maximally advanced position: this is the most tricky part because my current implementation does not take into account two crucial ingredients
a) left/right imbalance (the example of moving piece on 43 -> 44 is not correctly handled)
b) obstruction of own/enemy pieces (because I do simultaneous bitshifts)
3) assigning scores to current position and maximally advanced position: I used to simply count number of controlled squares and let each square count for 2 tempi, but now I think that N most advanced squares should count (for position with N pieces for each color)

I don't know how sensitive the playing strength is on these issues. I think that the dynamic search should take care of these subtleties: this is a static analysis and it's impossible to get it 100% right. Perhaps Ed can join the discussion as he has also implemented this algorithm but in a slightly different way.

Rein

Yes Rein a number of problems have to be resolved like the three other following ones


of course it is only a part of a classical position. In this position you see the possibility 47-41-36-31 that gives 3 tempi but if in the position above the white man is on square 48 instead en 47 then this possibility disappear.


In this position I can understand that white could (?) control one of the squares 22, 23 or 24 but it would be completly incorrect to conclude that white controls all these 3 squares due to the only man on currently on square 33.


In this position and considering square 11, though black has 2 men against one, the square 11 is neutral isn't it?

[Rein Halbersma]

Yes Rein a number of problems have to be resolved like the three other following ones


of course it is only a part of a classical position. In this position you see the possibility 47-41-36-31 that gives 3 tempi but if in the position above the white man is on square 48 instead en 47 then this possibility disappear.

Well, it depends on which other pieces are on the board. If the diagram is as you state (without a piece on 33), changing piece 47 with one on 48 would still give 3 tempi: 48-43-39-33, right? But your general point about controlled squares that cannot be reached in reality (e.g. because of left/right balance or obstruction) is valid.

In this position I can understand that white could (?) control one of the squares 22, 23 or 24 but it would be completly incorrect to conclude that white controls all these 3 squares due to the only man on currently on square 33.

I'm not sure if this is a real problem. White can of course only occupy one of the three 22/23/24 squares, but as long as black hasn't decided which one to counter-attack, he controls all three of them *for the time being*. Remember I use the majority rule, so whenever there are black attackers to squares on the 6th row, white loses control. The dynamic search will resolve this. But note that prematurely moving piece 33 will be penalized because then white loses at least one controlled square on the 6th row. So actually white is encouraged to first move supporting pieces to squares 32/34 before trying to occupy the 5th or 6th row (it is already encouraged to do so because isolated pieces are penalized, but that's another story). Also note that if it's black to move, then any black move that occupies the 3rd row, will also neutralize part of white's control over the 6th rank, so this position that you show is really a temporary picture of a more dynamic fight. It might make the search be slightly unstable, but I don't think that can be avoided and it's not too bad anyway (a tempo/square extra in such an open position should not really bother me: there is too much that can happen before everthing is closed up).

In this position and considering square 11, though black has 2 men against one, the square 11 is neutral isn't it?

No, I consider square 11 to be controlled by black. This may seem odd, but black has more options with square 11 than white. E.g. if there are black pieces on 12 and 18, black can make an exchange 7-11. Another thing is that if there were a white piece on 26/27/28, then a white sacrifice 26/27/28-21 would not give white control over 11. So you see that I use the controlled squares for more things than tempo/terrain alone. Also breakthrough potential is affected.

Compared to the diagram that you first showed, it's interesting that you consider 27-21 unsafe for white. I would like to encourage black to occupy square 7 because then it controls square 11 and a white 27-21-16 and a sacrifice 26-21 is no longer dangerous. For that to be detected sooner, it's necessary to add square 16 to white initally (so that the dynamic search will guide black to strengthen its right wing). I chose not to make any exceptions for particular moves, and only base the bitshifting (called flood-fill) on general principles. That makes it somewhat less precise perhaps, but also easier to program.

How does your algorithm work in more detail, Gerard? What other dangerously looking moves are being excluded? And do you perform a sequential (rather than simultaneous) search, first for white and then black? Do you move all pieces in parallel or one by one?

One thing that can still be improved I think is to distinguish between passive and active control. With passive control I mean to be able to prevent the opponent to occupy a square. E.g. white is prevented from occupying square 11 in the last diagram. With active control I mean the ability to have a piece that could reach a square without being captured. So black doesn't actively control square 11. With a black piece on 1, black would then also actively control square 11. I will have to think about this to see if this can be generated cheaply enough. I think the underlying bitboard patterns are already being generated so this might be a good idea to test.

Rein

[TAILLE]

Hi Rein,

How does your algorithm work in more detail, Gerard? What other dangerously looking moves are being excluded? And do you perform a sequential (rather than simultaneous) search, first for white and then black? Do you move all pieces in parallel or one by one?

One thing that can still be improved I think is to distinguish between passive and active control. With passive control I mean to be able to prevent the opponent to occupy a square. E.g. white is prevented from occupying square 11 in the last diagram. With active control I mean the ability to have a piece that could reach a square without being captured. So black doesn't actively control square 11. With a black piece on 1, black would then also actively control square 11. I will have to think about this to see if this can be generated cheaply enough. I think the underlying bitboard patterns are already being generated so this might be a good idea to test.

Rein

I see your point. Basically you want to avoid too many calculations in the eval function and you want to reuse the result of a long calculation for several purpose if it is possible.
My view is almost the opposite. I prefer to make a lot of calculation in the eval function if I feel that these calculations will allow me to have a more accurate evaluation with the following advantages
1) In common situations this evaluation looks like several plies under the leaves of the tree
2) with an accurate evaluation you can more easily put in place a more aggressive reduction/pruning mechanism.

Let's suppose that you explore a position at a "nominal" depth 22 and let's suppose you are able to find immediately (it is always the first move you decide to search) a cut move. That means that the tree you will search will have still about 10^11 leaves and reductions have to take place if I suppose you are not allowed to explore more than 10^9 positions due to time constraints. With this assumption you will reduce the tree to 1% of the positions based on your eval function. If the eval function is not that accurate enough the probability that your 1% of positions do not include the best branches could be very high.
I consider it is always fruitful to waste more CPU time in order to reach a more reliable evaluation because your reduction mechanism will be far more efficient (but I cannot prove this statement!).
Now you can understand my choice: for terrain/tempo I perform always two sequential searches, one for white and one for black; I am aware of the captures and I move the pieces one by one.

Another important point is the following: in rather open positions I do not do this terrain/tempo calculation because the frontier between white and black pieces is very unstable and the calculation will not really help to improve the eval function.
For me terrain/tempo calculation is interesting only in closed positions.

[BertTuyt]

Gerard with the addition of squares 25 and 26 I now know what you meant.

Bert

As soon as you recognize a classical position it is essential to look for the control of squares 25 and 26. If one side control both squares then it controls the 2 wings which could be a great advantage. In other words this side controls a bigger terrain and thus this side gets more tempi on its terrain which could be a decisive advantage.

[BertTuyt]

I shared in a previous post that I also changed some evaluation code.
In several posts I want to discuss the breakthrough routine.

So far I implemented a breakthrough-table, which I didn't like as it contains rubbish (positions which most likely will never occur), and with an exploding size.
For simplicity i initially only implemented 1 man against multiple opponents (on the last X ranks). I implemented so far only 3 ranks. So in the case of black squares 1 - 15 , and the white man could be placed on squares 6 - 15 . The table was twofold, for the white an black side to move. Although rubbish the index (especially for black in this case was very easy as it was directly derived from the bitboard). However expanding to more rows and more white man (or for the black breakthrough black man) this seems to me not the way to go forward.
therefore i started from scratch (and by observing games, I will expand the routine step by step).

Especially as matches against Kingsrow learned by that you need to detect breakthrough from a distance, and my routine was not very well suited for this. Therefore I switched to a bit board approach.

The first part of the code is below, which I will explain first. The second part will be included in a next post

Code: Select all

iScore = 0 ;

	// Test on Open PromotionPath
	bbWhiteMan0 = pTDepth->bbField[BB_WHITEMAN] & DFLD_BREAKTHROUGH_WHITE ;	// Position 6 - 30

	if ( bbWhiteMan0 == 0 )
		return ( 0 ) ;	// No BreakThrough, Return Score 0

	bbWhiteMan	= bbWhiteMan0 ;
	bbBlackMan	= pTDepth->bbField[BB_BLACKMAN] ;
	bbLockedMan	= 0 ;

	iOffset = ( pTDepth->bTurn == true ? 0 : 64 ) ;
	bKing	= ( pTDepth->bbField[BB_BLACKKING]  ? true : false ) ;

	while ( bbWhiteMan ) {

		_BitScanForward64(&iBitSet, bbWhiteMan) ;

		bbPosition = (BITBOARD)1<<iBitSet ;

		bbWhiteMan ^= bbPosition ;

		bbOPPathWhite	= m_bbOPPathWhite[iBitSet] ;
		bbBlockMan		= bbOPPathWhite & bbBlackMan ;

		iCountBlack = (int)POPCNT64(bbBlockMan) ;
		iCountWhite = (int)POPCNT64(bbOPPathWhite & bbWhiteMan0) ;

I only include/examine breakthrough opportunities for white (in this example, i have another routine for black) man on squares 6 - 30

Code: Select all

bbWhiteMan0 = pTDepth->bbField[BB_WHITEMAN] & DFLD_BREAKTHROUGH_WHITE ;	// Position 6 - 30

Next I scan through all found white man on squares 6 - 30

Code: Select all

	while ( bbWhiteMan ) {

		_BitScanForward64(&iBitSet, bbWhiteMan) ;

		bbPosition = (BITBOARD)1<<iBitSet ;

		bbWhiteMan ^= bbPosition ;

Then I access an array containing all the squares a white man on square iBitSet can reach (i think you name this also flood fill).
The black man bitboard is masked (AND operation) with this Bitboard bbOPPathWhite (the OP means OPEN or free here).

Code: Select all

		bbOPPathWhite	= m_bbOPPathWhite[iBitSet] ;
		bbBlockMan		= bbOPPathWhite & bbBlackMan ;

Next I count the number of white man and black man in this masked bitboard.

Code: Select all

		iCountBlack = (int)POPCNT64(bbBlockMan) ;
		iCountWhite = (int)POPCNT64(bbOPPathWhite & bbWhiteMan0) ;

Based on the value of iCountBlack and iCountWhite (and some additional conditions/test) i determine score and/or if a breakthrough / free-path is possible.
Will post some more details next time.

Note:
The code is not perfect yet, and some conditions are missing (the routine does not detect yet if there is left and right from the white man a blocking black man, , which blocks a first move).
Also the routine does not detect/evaluate black man outside the mask which can still block progress.

Bert

[MichelG]

So far I implemented a breakthrough-table, which I didn't like as it contains rubbish (positions which most likely will never occur), and with an exploding size.

That's what dragon uses. Dragon looks at fields 1-25. For each combination of pieces, a 8 or more ply search is stored in the table to find out if a breakthrough is possible.

That would be 2^5*3^20=a hell of a lot of data, but the key is to keep out the rubbish by only storing the configurations that occur the most frequently on the board. Some positions will not be in the table, but i think i get 99+%.

Michel

[BertTuyt]

Michel, thanks for sharing.

I assume you have process criteria whether to do a specific breakthrough search and later include a specific configuration or/not in the table.
I guess you have 3 values in the end, no breakthrough, breakthrough and unknown, which you then compress in line with the algorithm used for Endgame Databases.
Right?

If so, could you detail the criteria used for table include ?

And if I'm completely wrong, then I'm curious to understand the actual process
Do you have a specific trick for the table index function, so that the calculation is not so time consuming as in the endgame DB case?

Bert

[MichelG]

Michel, thanks for sharing.

I assume you have process criteria whether to do a specific breakthrough search and later include a specific configuration or/not in the table.
I guess you have 3 values in the end, no breakthrough, breakthrough and unknown, which you then compress in line with the algorithm used for Endgame Databases.
Right?

If so, could you detail the criteria used for table include ?

And if I'm completely wrong, then I'm curious to understand the actual process
Do you have a specific trick for the table index function, so that the calculation is not so time consuming as in the endgame DB case?

Bert

I just let the program play against itself, and count which type of positions occur most frequent.

The table index is fairly simple:

index=map1(pos(field1)+3*pos(field2)+*pos(field3)+....etc)+x*map2(pos(field4)+pos(field5)+....etc

pos(field)=0, 1 or 2 depending on white/black/empty
map1() maps the index value (12 fields, 0....3^12-1) to small value (say 0-20000). map2() maps the index value for the 13 other fields (0....3^13-1) to another index.

value=bittable[index]

There is no compression, except for using only 1 bit/position (breakthrough or unknown). 400 million positions are encoded to 100 MB of data

I'll let you figure out the details yourself.

[BertTuyt]

Herewith the second part of the breakthrough routine, in view of time (today) i will not include remarks and/or further explanation.
Thats for tomorrow otherwise the weekend.

Code: Select all

		bBreakThrough = false ;

		if ( iCountBlack == 0 && iCountWhite >= 0 ) {

			if ( iCountWhite == 0 && ( bbPosition & DFLD15 ) && ( bbBlackMan & DFLD14 ) )	// Special Case
				iScore += 40 ;
			else
				bBreakThrough = true ;
		
		} else if ( iCountBlack == 1 && iCountWhite == 1 ) {

			// Special cases no Breakthrough
			if ( ALLPIECE( bbWhiteMan0, ( DFLD15 | DFLD20 ) ) && ALLPIECE( bbBlackMan, ( DFLD4 | DFLD19 ) ) )
				iScore += 30 ;
			else
				bBreakThrough = true ;

		} else if ( iCountBlack == 1 && iCountWhite > 1 ) {
			bBreakThrough = true ;
		
		} else if ( iCountBlack == 1 && iCountWhite == 0 ) {

			if ( bbNBWhite[iBitSet + iOffset] & bbBlackMan )
				bBreakThrough = true ;
			else if ( bbLockedMan & bbBlockMan )	// the Blocking Man is already Locked through another Attacker
				bBreakThrough = true ;
			else
				bbLockedMan |= bbBlockMan ;

		} else if ( iCountBlack == 2 && iCountWhite == 0 ) {		// 2 Black Man defend 1 White Man against a breakthrough.

			if ( ( bbPosition & DFLD_ROW2 ) && ( POPCNT64( bbOPPathWhite & bbBlackMan & DFLD_ROW0 ) == 2 ) )
				iScore += 40 ;
		}

		if ( bBreakThrough == true ) {

			iRow	= m_iRow[iBitSet] ;
			iPly	= 2* iRow - ( pTDepth->bTurn == true ? 2 : 1 ) ;

			if ( bKing )
				iScore += ( m_iBreakThroughScore[iPly] / 2 ) ;
			else
				iScore += m_iBreakThroughScore[iPly] ;
		}

	}

	return ( iScore ) ;
}

Bert

[BertTuyt]

After counting the number of white and black man in the masked bitmaps of the squares for the (potential) breakthrough white man, the next 5 conditions are evaluated :

Code: Select all

if ( iCountBlack == 0 && iCountWhite >= 0 ) {

} else if ( iCountBlack == 1 && iCountWhite == 1 ) {

} else if ( iCountBlack == 1 && iCountWhite > 1 ) {

} else if ( iCountBlack == 1 && iCountWhite == 0 ) {

} else if ( iCountBlack == 2 && iCountWhite == 0 ) {

if A breakthrough is detected ( breakthrough = true ) then the breakthrough score for that man is calculated.
The score is a function of the Row (or distance to the promotion row).

In case the opponent has a King ( or more than one .. ) then the score is reduced ( by /2 ).

Code: Select all

if ( bBreakThrough == true ) {

			iRow	= m_iRow[iBitSet] ;
			iPly	= 2* iRow - ( pTDepth->bTurn == true ? 2 : 1 ) ;

			if ( bKing )
				iScore += ( m_iBreakThroughScore[iPly] / 2 ) ;
			else
				iScore += m_iBreakThroughScore[iPly] ;
		}

Condition 1:
In case iCountBlack == 0 && iCountWhite >= 0 then basically a breakthrough should be possible.
However there are many cases where the white man is blocked by 1 or 2 adjacent opponent man. So far i test only one case which i often observed during games (but need to add more in the future, and probably have to translate that into a more generic condition).

Code: Select all

if ( iCountBlack == 0 && iCountWhite >= 0 ) {

			if ( iCountWhite == 0 && ( bbPosition & DFLD15 ) && ( bbBlackMan & DFLD14 ) )	// Special Case
				iScore += 40 ;
			else
				bBreakThrough = true ;

Condition2 :
Also here the condition should be sufficient for a breakthrough in many case, i included (so far) one exception.

Code: Select all

} else if ( iCountBlack == 1 && iCountWhite == 1 ) {

			// Special cases no Breakthrough
			if ( ALLPIECE( bbWhiteMan0, ( DFLD15 | DFLD20 ) ) && ALLPIECE( bbBlackMan, ( DFLD4 | DFLD19 ) ) )
				iScore += 30 ;
			else
				bBreakThrough = true ;

Condition 3:
Here no exception, so always breaktrough.

Code: Select all

} else if ( iCountBlack == 1 && iCountWhite > 1 ) {
			bBreakThrough = true ;

Condition 4:
First check if the black man can block the white man. Basically the "flooded" bit board is the first step, but a better check is needed ( the bitboard bbNBWhite[] contains all the black locations which can not block the white man!) . But if the black man is blocking 2 different white man at once, the assumption is that a breakthrough is possible. If no breakthrough is possible , than the the specific black man is ""locked" and added to the bbLockedMan bitboard.

Code: Select all

} else if ( iCountBlack == 1 && iCountWhite == 0 ) {

			if ( bbNBWhite[iBitSet + iOffset] & bbBlackMan )
				bBreakThrough = true ;
			else if ( bbLockedMan & bbBlockMan )	// the Blocking Man is already Locked through another Attacker
				bBreakThrough = true ;
			else
				bbLockedMan |= bbBlockMan ;

Condition 5:
No breakthrough possible but a special case is checked where 2 black man are needed to block the white man, with a positive score result.

Code: Select all

} else if ( iCountBlack == 2 && iCountWhite == 0 ) {		// 2 Black Man defend 1 White Man against a breakthrough.

			if ( ( bbPosition & DFLD_ROW2 ) && ( POPCNT64( bbOPPathWhite & bbBlackMan & DFLD_ROW0 ) == 2 ) )
				iScore += 40 ;
		}

Bert