Feike Boomstra 's Horizon Draughts Program

[BertTuyt]

Ed,

got your point.

You are right , for every match the results clearly indicates a better Horizon.
But as the differences between matches are so small, it is impossible to judge any change/difference in rating.
But that's also a clue !!
Even with 6 ply more depth, one is still not able to see a real difference compared with a 10Ply - 10Ply match.
What I believe, but the proof of the budding is in the eating, is that with more relevant evaluation knowledge , the differences become obvious.....

Bert

[TAILLE]

In situation like the above position, if the evaluation function is not able to tell you which is the better strategic move between 42-38 and 43-38 then you will never be able to avoid acculating small disadvantages that can lead to difficulties later in the game.

Gerard, it's clear that you understand draughts strategy better than me, as I don't see much difference between those 2 moves. Can you explain? Thanks.

-- Ed

White to move

Oops, for me there is a very big difference between these to moves.
I think 42-38 is not a good move at this stage of the game because it gives black a basic attacking strategy.
1) Black builds the arrow 17-11-06 => white as to play 47-42 or 48-42. If now you suppose that white chooses 47-42 in order to avoid creating a passive white man on 42 then the attacking strategy continues by :
2) Black exchange by 17-22 28x17 11x31 36x27 clearing completly the zone 36-41-46-47
3) Black exchange by 18-22 27x18 13x22
4) The black breakthrough threat so created put white under great pressure if not under difficulties!

In the real game the white (human) strong player chose 43-38 and the above strategy cannot work anymore due to the white man on 47

A program able to choose correctly between 43-38 and 42-38 would be very strong in semi-classic game!
For a strong player it is only the ABC of the semi-classic strategy.

[BertTuyt]

Gerard, like this.

But what is basically the minimum information a program needs to have to avoid this move sequence of white.
I guess that one could give a penalty if (too early in the game) the positions 41, 46, and 47 are empty?
Or do we need far knowledge to avoid this situation??

And last but not least, how could we construct an algorithm which learns this model of reasoning (by itself ?) ??

Bert

[TAILLE]

Gerard, like this.

But what is basically the minimum information a program needs to have to avoid this move sequence of white.
I guess that one could give a penalty if (too early in the game) the positions 41, 46, and 47 are empty?
Or do we need far knowledge to avoid this situation??

And last but not least, how could we construct an algorithm which learns this model of reasoning (by itself ?) ??

Bert

Two major comments:
1) First of all if you reach the two positions (the one after 42-38 and the other after 43-38) as leaves of the tree in two different branches of the tree, then you cannot decide which is better by looking simply at the zone 36-41-46-47 because at this stage of the analysis the two white men 36 and 47 are still in place
2) It would be a bad idea to give a penalty if the zone 36-41-46-47 is empty unless you analyse the position of the black men in details. If black cannot build the arrow 17-11-06 the situation becomes completly different. It is also very different if a black man is on 23 (the exchange 18-22 etc is no more possible).

I saw your post concerning learning by playing zillions of game but I am not able to see how it could work with such complex game. For the moment I prefer to continue to enfance Damy evaluation in order to avoid a great number of mistake like 42-38 in my above example. That implies a special implementation of the evaluation and for me it's a very interesting and funny job.

The only problem I have is that I cannot find time to spent on developping a damExchange protocol because I simply prefer the job described just above ! Anyway, is a source of damExchange protocol available ? If not is an example of source code using a some damExchange dll available ?

[BertTuyt]

The only problem I have is that I cannot find time to spent on developing a DamExchange protocol because I simply prefer the job described just above ! Anyway, is a source of DamExchange protocol available ? If not is an example of source code using a some DamExchange dll available ?

In Horizon I implemented my own Quick & Dirty DXP wrapper, which at least works with Damage and Dam 2.x.
I think is is relatively straightforward, both testing as to incorporate in your program.
No additional DXP .dll needed.
Whats is you development environment?
Both Ed and I use Visual Studio, and for both of us it worked...

See below code from what i did in Horizon.
If you have any specific question, I'm sure Ed or I can answer and help you out here.


Bert

Code: Select all

int main()
{
	bool bContinue, bWhiteTurn, bHorizonTurn, bDXPGame, bGameEnd ;
	char movebuf[128], msgbuf[128], recvbuf[128], sendbuf[128] ;
	int iResult ;
	int iBytesRecv ;
	int iBytesSent ;
	int i, iBoard[51] ;
	int iNMoves ;
	int iNSeconds, iNMilliSeconds, iGameTime, iTime ;
	struct timeb SearchStartTime, SearchEndTime ;
	int clntLen ;
	SOCKET ServerSocket, ClientSocket  ;
	SOCKADDR_IN  service, service_client ;
	WSADATA wsaData ;


	// Create TimerThread
	hEventTimerStart = ::CreateEvent(NULL, false, false, NULL) ;
//	CreateThread( NULL, 0, wait_max_move_time, NULL, 0, NULL);	// Timer Thread

	// Initialize Winsock
	iResult = WSAStartup(MAKEWORD(2,2), &wsaData) ;

	if ( iResult != 0 ) {
		printf("WSAStartup failed: %d\n", iResult) ;
		return 1 ;
	}

	// Create a SOCKET for listening for incoming connection requests
	ServerSocket = socket(PF_INET, SOCK_STREAM, 0) ;

	if ( ServerSocket < 0 ) {
		printf("Error at socket(): %d\n", ServerSocket) ;
		return 0 ;

	} else printf("engine -- socket created\n") ;
	
	// The sockaddr_in structure specifies the address family,
	// IP address, and port for the socket that is being bound.
	service.sin_family = PF_INET ;
	service.sin_addr.s_addr = htonl(INADDR_LOOPBACK) ;
	service.sin_port = htons(27531) ;
	
	if ( bind( ServerSocket, (SOCKADDR*)&service, sizeof(service) ) == SOCKET_ERROR ) {
    
		printf("bind() failed.\n") ;
		closesocket(ServerSocket) ;
		return ( 0 );
	}

	// Listen for incoming connection requests 
	// on the created socket
	 if ( listen( ServerSocket, SOMAXCONN ) == SOCKET_ERROR ) {

		printf("Error listening on socket.\n") ;
		closesocket(ServerSocket);

		return ( 0 ) ;
	}

	printf("Listening on socket...\n") ;

	clntLen = sizeof(service_client) ;

//	ClientSocket = accept( ServerSocket, (SOCKADDR*)&service_client, &clntLen ) ;
	ClientSocket = accept( ServerSocket, NULL, NULL ) ;

	if ( ClientSocket == INVALID_SOCKET ) {

		printf("Error connect to client\n") ;
		closesocket(ServerSocket);

		return ( 0 ) ;
	}

	printf("Socket connected to client\n") ;

	// Declare and initialize variables.

	bContinue	= true ;
	bDXPGame	= false ;

	while ( bContinue ) {

		iBytesRecv = recv(ClientSocket, recvbuf, 128, 0) ;					// Wait for Client Message

		if ( recvbuf[0] == 'R' ) {		// GAMEREQ

			ProcessGameReq(recvbuf, &bHorizonTurn, &bWhiteTurn, iBoard) ;

			printf("Init Game : Start\n") ;
			init_game(recvbuf) ;
			printf("Init Game : End\n") ;

			iNMoves		= 0 ;
			iGameTime	= total_time_allowed ;

			strcpy_s(sendbuf, 128, DXP_STRING_GAMEACC) ;
			iBytesSent = send( ClientSocket, sendbuf, (int)strlen(sendbuf)+1 , 0 ) ;	// Sent GAMEACC Message

			bDXPGame = true ;
			bGameEnd = false ;

		} else if ( recvbuf[0] == 'E' ) { // GAMEEND

			if ( bGameEnd == false ) {

				strcpy_s(sendbuf, 128, DXP_STRING_GAMEEND) ;

				iBytesSent = send( ClientSocket, sendbuf, (int)strlen(sendbuf)+1 , 0 ) ;	// Sent GAMEEND Message

				bGameEnd = true ;
			}

				bDXPGame = false ;

		} else if ( recvbuf[0] == 'M' ) { // MOVE
	
			strcpy_s(movebuf, 128, recvbuf) ;

			ProcessMove(movebuf, iBoard) ;
			
			++iNMoves ;
			bWhiteTurn = !bWhiteTurn ;
		}

		if ( bDXPGame && ( bWhiteTurn == bHorizonTurn ) ) {

			if ( bHorizonTurn == true )
				msgbuf[1] = 'W' ;
			else
				msgbuf[1] = 'Z' ;

			for ( i=1; i<=50; i++ ) {

				if ( iBoard[i] == -2 )
					msgbuf[1+i] = 'Z' ;
				else if ( iBoard[i] == -1 )
					msgbuf[i+1] = 'z' ;
				else if ( iBoard[i] == 0 )
					msgbuf[i+1] = 'e' ;
				else if ( iBoard[i] == 1 )
					msgbuf[i+1] = 'w' ;
				else if ( iBoard[i] == 2 )
					msgbuf[i+1] = 'W' ;
			}

			sprintf_s(msgbuf+52, 128, "%.4d", iNMoves) ;
			sprintf_s(msgbuf+56, 128, "%.4d", iGameTime) ;

			ftime(&SearchStartTime) ;		// Start Time

			get_best_move(msgbuf+1);
	//		get_best_move_fixed_depth(msgbuf+1) ;

			ftime(&SearchEndTime) ;			// End Time

			iNSeconds		= int(SearchEndTime.time		- SearchStartTime.time) ;
			iNMilliSeconds	= int(SearchEndTime.millitm		- SearchStartTime.millitm) ;

			iTime	 = ( 1000 * iNSeconds )  + iNMilliSeconds ;
			iTime	/= 1000 ;

			iGameTime -= iTime ;

			if ( result[0] == 'E' ) {

				strcpy_s(sendbuf, 128, DXP_STRING_GAMEEND) ;
				iBytesSent = send( ClientSocket, sendbuf, (int)strlen(sendbuf)+1 , 0 ) ;	// Sent GAMEEND Message

				bGameEnd = true ;

			} else {

				strcpy_s(movebuf, 128, result) ;

				ProcessMove(movebuf, iBoard) ;

				++iNMoves ;
				bWhiteTurn = !bWhiteTurn ;

				if ( iNMoves == 1 ) {
					Sleep(100);		// Sleep 100 millisonds , to avoid communication error when first move is forced !!
					printf("First Message\n");
				}

				iBytesSent = send(ClientSocket, result, (int)strlen(result) + 1, 0) ;

				if ( iNMoves == 1 )
					printf("Message sent\n");

				if ( iBytesSent <= 0 )
					printf("Message communication Error\n");
			}
		}	
	}

	printf("engine -- Closing....\n") ;
	closesocket(ServerSocket) ;
	exit(0) ;

	return ( 0 ) ;
}

[TAILLE]

The only problem I have is that I cannot find time to spent on developing a DamExchange protocol because I simply prefer the job described just above ! Anyway, is a source of DamExchange protocol available ? If not is an example of source code using a some DamExchange dll available ?

In Horizon I implemented my own Quick & Dirty DXP wrapper, which at least works with Damage and Dam 2.x.
I think is is relatively straightforward, both testing as to incorporate in your program.
No additional DXP .dll needed.
Whats is you development environment?
Both Ed and I use Visual Studio, and for both of us it worked...

See below code from what i did in Horizon.
If you have any specific question, I'm sure Ed or I can answer and help you out here.

Bert

Thank you bert for all this stuff.

My development environment is visual studio C++.
After having put your source in my program by only a copy/paste the compilation gives the following result (sorry but in french)

1>.\Arbre.cpp(16540) : error C2079: 'SearchStartTime' utilise une struct de 'main::timeb' non défini
1>.\Arbre.cpp(16540) : error C2079: 'SearchEndTime' utilise une struct de 'main::timeb' non défini
1>.\Arbre.cpp(16548) : error C2065: 'hEventTimerStart' : identificateur non déclaré
1>.\Arbre.cpp(16619) : error C3861: 'ProcessGameReq' : identificateur introuvable
1>.\Arbre.cpp(16622) : error C3861: 'init_game' : identificateur introuvable
1>.\Arbre.cpp(16626) : error C2065: 'total_time_allowed' : identificateur non déclaré
1>.\Arbre.cpp(16628) : error C2065: 'DXP_STRING_GAMEACC' : identificateur non déclaré
1>.\Arbre.cpp(16638) : error C2065: 'DXP_STRING_GAMEEND' : identificateur non déclaré
1>.\Arbre.cpp(16651) : error C3861: 'ProcessMove' : identificateur introuvable
1>.\Arbre.cpp(16681) : error C3861: 'ftime' : identificateur introuvable
1>.\Arbre.cpp(16683) : error C3861: 'get_best_move' : identificateur introuvable
1>.\Arbre.cpp(16686) : error C3861: 'ftime' : identificateur introuvable
1>.\Arbre.cpp(16688) : error C2228: la partie gauche de '.time' doit avoir un class/struct/union
1> le type est 'int'
1>.\Arbre.cpp(16688) : error C2228: la partie gauche de '.time' doit avoir un class/struct/union
1> le type est 'int'
1>.\Arbre.cpp(16689) : error C2228: la partie gauche de '.millitm' doit avoir un class/struct/union
1> le type est 'int'
1>.\Arbre.cpp(16689) : error C2228: la partie gauche de '.millitm' doit avoir un class/struct/union
1> le type est 'int'
1>.\Arbre.cpp(16696) : error C2065: 'result' : identificateur non déclaré
1>.\Arbre.cpp(16698) : error C2065: 'DXP_STRING_GAMEEND' : identificateur non déclaré
1>.\Arbre.cpp(16705) : error C2065: 'result' : identificateur non déclaré
1>.\Arbre.cpp(16707) : error C3861: 'ProcessMove' : identificateur introuvable
1>.\Arbre.cpp(16717) : error C2065: 'result' : identificateur non déclaré
1>.\Arbre.cpp(16717) : error C2065: 'result' : identificateur non déclaré

Maybe a lot of things depends on C/C++ environment. Not so obvious.

[BertTuyt]

Gerard,

I recognize most of it, and I'm sure I can help you.
I will post some more information in the next hours to support you.
Please let me know, where you still struggle...

Bert

[Ed Gilbert]

1) First of all if you reach the two positions (the one after 42-38 and the other after 43-38) as leaves of the tree in two different branches of the tree, then you cannot decide which is better by looking simply at the zone 36-41-46-47 because at this stage of the analysis the two white men 36 and 47 are still in place
2) It would be a bad idea to give a penalty if the zone 36-41-46-47 is empty unless you analyse the position of the black men in details. If black cannot build the arrow 17-11-06 the situation becomes completly different. It is also very different if a black man is on 23 (the exchange 18-22 etc is no more possible).

My feeling is that it is too dependent on context to draw conclusions about 42-38 vs. 43-38 based on the particular sequence of moves that you described. Those are dependent on there being a white man on 28, on black achieving the 6,11,17 line, and on white playing 47-42 rather than 48-42 at some point. Of course you may be right, but I try to avoid eval terms that depend on so much context. As Bert says, the proof is in the pudding! The game needs to be played out to see what happens.

Regarding DXP, I recommend that you use Frank's .dll, as it has the dxp functions nicely abstracted for use in a Windows program. It basically has 4 functions -- open, close, read, and write. After you open the driver, your user interface's message handler will receive USER messages when a new DXP message has been received, at which point you pick it up by calling the read function. In this way your code never blocks waiting for a message, which is a disadvantage of the code Bert used for horizon. Frank's driver also parses out the various pieces of info in the message and delivers them in easy to use structure fields. Of course Frank also supplies a header file with all the function prototypes, typedefs, and macros that you need to use the functions.

-- Ed

[TAILLE]

Gerard,

I recognize most of it, and I'm sure I can help you.
I will post some more information in the next hours to support you.
Please let me know, where you still struggle...

Bert

Thank you Bert, may be we can exchange directly by email.
My mail address is : gerardtaille at orange.fr
Why didn't you take Frank dll as sugested by Ed ?

[TAILLE]

1) First of all if you reach the two positions (the one after 42-38 and the other after 43-38) as leaves of the tree in two different branches of the tree, then you cannot decide which is better by looking simply at the zone 36-41-46-47 because at this stage of the analysis the two white men 36 and 47 are still in place
2) It would be a bad idea to give a penalty if the zone 36-41-46-47 is empty unless you analyse the position of the black men in details. If black cannot build the arrow 17-11-06 the situation becomes completly different. It is also very different if a black man is on 23 (the exchange 18-22 etc is no more possible).

My feeling is that it is too dependent on context to draw conclusions about 42-38 vs. 43-38 based on the particular sequence of moves that you described. Those are dependent on there being a white man on 28, on black achieving the 6,11,17 line, and on white playing 47-42 rather than 48-42 at some point. Of course you may be right, but I try to avoid eval terms that depend on so much context. As Bert says, the proof is in the pudding! The game needs to be played out to see what happens.

Regarding DXP, I recommend that you use Frank's .dll, as it has the dxp functions nicely abstracted for use in a Windows program. It basically has 4 functions -- open, close, read, and write. After you open the driver, your user interface's message handler will receive USER messages when a new DXP message has been received, at which point you pick it up by calling the read function. In this way your code never blocks waiting for a message, which is a disadvantage of the code Bert used for horizon. Frank's driver also parses out the various pieces of info in the message and delivers them in easy to use structure fields. Of course Frank also supplies a header file with all the function prototypes, typedefs, and macros that you need to use the functions.

-- Ed

Ed, do you have an example available showing how you initialise the interface and how you use it ?

[BertTuyt]

Here a few hints, and it is also evident that you need to pass a MOVE from your program to the DXP interface to make it work, but we can disucss later...

You need to add the #include <sys/timeb.h at the start of the file, otherwise the structures struct timeb SearchStartTime, SearchEndTime ; is not recognized.

In my case I declared the next parameters outside the main()

int absolute_max_move_time;
HANDLE hEventTimerStart;

The missing defines are:
#define DXP_STRING_GAMEACC "AHorizon 3.0 0"
#define DXP_STRING_GAMEEND "E00"

Here the code of the routines ProcessMove() and ProcessGameReq()

Code: Select all

void ProcessMove(char *movebuf, int *iBoard)
{
	int iPFrom, iPTo, iTemp ;
	int i, iNCapture, iPCapture ;

	sscanf_s(&movebuf[5],"%2d%2d%2d", &iPFrom, &iPTo, &iNCapture);

	iTemp			= iBoard[iPFrom];
	iBoard[iPFrom]	= 0;
	iBoard[iPTo]	= iTemp;

	if ( iTemp == 1 && iPTo <= 5 )		// Promotion WhiteMan
		iBoard[iPTo] = 2;

	if ( iTemp == -1 && iPTo >= 46 )	// Promotion BlackMan
		iBoard[iPTo] = -2;

	if ( iNCapture > 0 ) {

		for ( i=0; i<iNCapture; i++ ) {

			sscanf_s(&movebuf[11 + 2*i], "%2d", &iPCapture) ;
			iBoard[iPCapture] = 0 ;
		}
	}
}


void ProcessGameReq(char *recvbuf, bool *bHorizonTurn, bool *bWhiteTurn, int *iBoard)
{
	int i ;

	if ( recvbuf[35] == 'W' ) {
		*bHorizonTurn = true ;
		printf("Horizon plays WHITE\n") ;
	} else {
		*bHorizonTurn = false ;
		printf("Horizon plays BLACK\n") ;
	}

	if ( recvbuf[42] == 'A' ) {	// Normal Board Position

		*bWhiteTurn	= true ;

		// Init Board
		for ( i=1; i<=20; i++ )
			iBoard[i] = -1;

		for ( i=21; i<=30; i++ )
			iBoard[i] = 0 ;

		for ( i=31; i<=50; i++ )
			iBoard[i] = 1 ;

	} else if ( recvbuf[42] == 'B' ) {	// Specific Board Position

		if ( recvbuf[43] == 'W' )
			*bWhiteTurn  = true ;
		else
			*bWhiteTurn = false ;

		for ( i=1; i<=50; i++ ) {

			if ( recvbuf[43+i] == 'e' )
				iBoard[i] = 0 ;
			else if ( recvbuf[43+i] == 'w' )
				iBoard[i] = 1 ;
			else if ( recvbuf[43+i] == 'W' )
				iBoard[i] = 2 ;
			else if ( recvbuf[43+i] == 'z' )
				iBoard[i] = -1 ;
			else if ( recvbuf[43+i] == 'Z' )
				iBoard[i] = -2 ;
		}
	}
}

If the number of errors reduce, i wille explain the format of the MOVE as output of your search-routine.

Bert

[BertTuyt]

I didn't use the Frank DLL as I wanted to understand myself how this socket() thing worked.
And I did want to be dependant on a DLL I not fully understood
So this is just a quick and dirty implementation which helped me also to understand the internals

Bert

[BertTuyt]

But I also agree with Ed.
If you want to have a structural solution go for the DLL.
If you want to understand some details, and need only a Q&D implementation (for the time being) , as I did in Horizon, then just use the code I sent you...

Bert

[Ed Gilbert]

Ed, do you have an example available showing how you initialise the interface and how you use it ?

Gerard, yes I have some code that I will email to you.

-- Ed

[Rein Halbersma]

In situation like the above position, if the evaluation function is not able to tell you which is the better strategic move between 42-38 and 43-38 then you will never be able to avoid acculating small disadvantages that can lead to difficulties later in the game.

Gerard, it's clear that you understand draughts strategy better than me, as I don't see much difference between those 2 moves. Can you explain? Thanks.

-- Ed

White to move

Oops, for me there is a very big difference between these to moves.
I think 42-38 is not a good move at this stage of the game because it gives black a basic attacking strategy.
1) Black builds the arrow 17-11-06 => white as to play 47-42 or 48-42. If now you suppose that white chooses 47-42 in order to avoid creating a passive white man on 42 then the attacking strategy continues by :
2) Black exchange by 17-22 28x17 11x31 36x27 clearing completly the zone 36-41-46-47
3) Black exchange by 18-22 27x18 13x22
4) The black breakthrough threat so created put white under great pressure if not under difficulties!

The 4 stage plan you are describing is at least a 12 ply search! E.g. 1. 42-38 8-12 2. 47-42 12-17 3. 33-28 17-22 4. 28x17 11x31 5. 36x27 18-22 6. 27x18 13x22. This alone is enough to convince me that you cannot put any preference for 42-38 vs 43-38 in an evaluation function. I think it is just too context dependent whether black can make a good pressure attack.

Moreover, there are also other considerations in case the game becomes classical. E.g. after 43-38 18-23 33-28 you still can exchange 37-31x31 and after 21-26 catch again with 47-42x31. After 42-38 18-23 33-28 white runs a small risk of leaving piece 36 behind. Of course in this particular position, that are two arguments for 43-38 over 42-38 and I probably would play 43-38 myself (for what it's worth anyway), but it requires a search, not an evalulation to make that decision.

A simple eval with only material, terrain, tempo, balance and formation counting would already prefer 43-38 over 42-38. At least mine does E.g. 42-38 destroys 37-42-48 and 33-39-44, but 43-38 maintains both of them and even builds 33-38-43.

Rein