Feike Boomstra 's Horizon Draughts Program

[BertTuyt]

Let's create a new thread related to the Horizon Draughts Program.

Here we can discuss the program, ask questions, and propose improvements ( where needed/possible) ........

Bert

[BertTuyt]

To test the speed of the Horizon MoveGenerator I implemented the Perft function.
For this purpose I also slightly re-wrote (removing hash-related updates) the populate_node() function (do_Move).
The system I use is based on the Intel i7 940 ( 2.93 GHz).
See below for the results for the initial position (without bulk-coating) :

Code: Select all

Perft(1)        N = 9      0.00 sec.    KN/sec = 0
Perft(2)        N = 81     0.00 sec.    KN/sec = 0
Perft(3)        N = 658    0.00 sec.    KN/sec = 0
Perft(4)        N = 4265           0.00 sec.    KN/sec = 0
Perft(5)        N = 27117          0.00 sec.    KN/sec = 27117
Perft(6)        N = 167140         0.00 sec.    KN/sec = 41785
Perft(7)        N = 1049442        0.03 sec.    KN/sec = 36187
Perft(8)        N = 6483961        0.18 sec.    KN/sec = 36426
Perft(9)        N = 41022423       1.17 sec.    KN/sec = 35061
Perft(10)       N = 258895763      7.10 sec.    KN/sec = 36479
Perft(11)       N = 1665861398    47.64 sec.    KN/sec = 34965
Press any key to continue . . .

Note: Today Intel introduced the Sandy Bridge processors, but we have to wait for Q2-Q3 2011, then the 8-core variants will be introduced !!

Bert

[Ed Gilbert]

Let's create a new thread related to the Horizon Draughts Program.

Here we can discuss the program, ask questions, and propose improvements ( where needed/possible) ........

Ok, I'll describe how I have used the Horizon sources. As I mentioned in another thread, I created a hybrid program for testing that consists of the kingsrow GUI and search connected to the horizon eval function. This wasn't very difficult, and the result is quite useful, a strong engine with a completely independent evaluation that I can use for engine match testing.

The horizon eval is spread amongst about 7 C files. The sources are designed for Linux, so I had to change a few things for Windows. There are a couple of compiler intrinsic functions for popcount and trailing zero count that I redefined with macros to some functions that I had for Windows, and then all I had to do was change the call from kingsrow eval function to the horizon function. The bit positions of the horizon and kingsrow bitboards are the same (I recently converted kingsrow to use gapped bitboards), but kingsrow uses a board struct which has fields of black, white, and king, where horizon uses the fields man_king, white_black, and occupied_empty to represent the same info, so I had to make a few assignments to get the board into horizon's representation.

The horizon eval function also handles the chore of looking up positions in the endgame database. Fortunately that function is handled by the search in kingsrow, so I simple deleted that block of code as it was unnecessary.

The horizon sources are are formatted in a style that is very different from the style that I use. This is mostly a matter of personal taste, but because of the style difference I found them difficult to read. I ran the sources through a C beautifier program called Great Code, which converted them to a style that is very close to my own. Great Code is an open source program which (I think) I found a few years ago on the Source Forge web site. It is infinitely customizable, so you can make it emit code in whatever style you like. It's very handy for these kinds of jobs.

Somewhere on this forum a few months ago we discussed debugging techniques, and I described how I like to test my eval function by calling it with large number of random positions, actually position pairs. For each position I get the eval score, and then create a color's reversed mirror image of the position and get its eval score, and check that the two scores are symmetrical. This test function is built into the kingsrow user interface, so I ran it on the horizon eval, and it found some symmetry errors. I started fixing these one at a time, and this went on for several days. In total I have found and fixed 18 errors, and there is at least one more in the eval of voorpost squares that I have not fixed yet. The voorpost eval is quite complex, and though I know the general location of the bug I haven't decided how to fix it yet. At the moment, if I temporarily disable the voorpost portion of the eval then it passes all my symmetry tests. In addition, the bug is rather subtle, as the voorpost eval seems correct for the majority of positions, and the black/white discrepency when it occurs is small, so it hasn't been a high priority for me to fix. I have been using it with voorpost eval enabled, bug and all.

Most of the bugs look like copy/paste errors. It's a shame that Feike did not apply this relatively simple test to find them, as they really create a lot of problems with the eval scores. There is no doubt that horizon would be stronger with these bugs fixed. In some cases the bug was that the eval term got added to the variable for the wrong color. For example, there is a piece of code that detects that some white men are locked, which is good for black, and the code ends with the statement

white_locked += 700;

when in fact it should read

black_locked += 700;

These numbers represent 1/1000 of the value of a man, so this bug adds 0.7 times the value of a man to the wrong color. It's easy to see how a few bugs like this can really cause problems.

So now with all these bugs fixed, I have a hybrid test program consisting of the kingsrow gui, search, and endgame databases, and the horizon eval. I have played a few thousand automated games between kingsrow and this hybrid, and this has been very useful to me. I have found and fixed a couple of bugs in kingrow's eval, and I also noticed a few recurring themes in some of the losses and was able to adjust the weights of some eval terms so that these are no longer recurring themes. The win:loss ratio of kingsrow against this hybrid is running about 3:1, which makes this hybrid much stronger than truus or flits, as the ratio against those is around 10:1. What is also very nice is that while watching the games, if I see that the hybrid is (for example) showing a big score that kingsrow does not also seem to know about, and if horizon ends up winning that game or even just getting kingsrow into a difficult ending, I can stop the game, play through each position, ask each engine what their detailed static evaluation terms are, and see exactly what each one thinks is going on.

I'm really not sure why the horizon hybrid does not test better than it does. From what I can see, and with my limited draughts skills, much of the draughts knowledge in it looks sound, and it is quite extensive. The search speed of the hybrid is about 0.55 times the kingsrow search speed, so perhaps this accounts for some of that 3:1 ratio, but probably not all or even most of it. It has been my experience that good draughts knowledge in the eval is more important than speed. It's also possible that I created some bug in hooking it up into the kingsrow search. It would be interesting if someone else can repeat this hybrid experiment and see what kind of results they get.

The speed difference is partly because the horizon eval has more lines of code, but another reason may be that it has very many more "if" conditionals. In kingsrow I try to detect many formations in parallel using bitboard shifts, ANDs and ORs, count the number of formations and add that sum with some scaling into an eval term. Sometimes this can be done without using any conditionals. The horizon eval tends to test for formations at each square separately, so it has a lot of "if" statements.

I have sent Bert the diff's that show where the 18 eval bugs are located. I can email them to anyone else that is interested.

-- Ed

[wellnesswrotter]

I spoke to Feike once about his program. Its funny to say, that he indeed said the Voorpost-function was the most difficult.

But i think it is great work from you to fix `bugs` in the Horizon-algorithms Maybe, you can post them on the OpenSource webpage, in stead of hiding it behind an e-mailadres on this Forum:?:

[Rein Halbersma]

I spoke to Feike once about his program. Its funny to say, that he indeed said the Voorpost-function was the most difficult.

But i think it is great work from you to fix `bugs` in the Horizon-algorithms Maybe, you can post them on the OpenSource webpage, in stead of hiding it behind an e-mailadres on this Forum:?:

Hi Johan Teake,

I agree with you that it would be nice if Ed's cleaned-up Horizon-eval() and Bert's added Horizon-DXP interface were submitted to the Subversion repository that also contains the original code, especially if someone is already willing to supply the source by email to interested persons.

However, the phrase "hiding it" is perhaps a bit too strong of a response since the Boost license under which Horizon is released does not require anyone to release their modifications.

Rein

[Ed Gilbert]

Maybe, you can post them on the OpenSource webpage, in stead of hiding it behind an e-mailadres on this Forum:?:

It should be clear that nothing is being hidden, in fact just the opposite. Bert is doing a complete port of the horizon program to Windows, and when he is finished that code along with the bug fixes will be committed to the Source Forge repository. You can wait for that to happen and then get the fixes that way, or you can get them right now via email.

-- Ed

[BertTuyt]

As was mentioned already Ed has worked on the Evaluation function and created a Hybrid version of Kingsrow.
The Horizon program was developed for Linux and I translated the OS specific parts, so the program now also runs within the Windows environment.
Next tot that I have included a very-simple DXP wrapper to enable game/mach play against other engines.
The version which is now available, lacks the parallel search-implementation , but that is a matter of time.
I was able to compile all sources without errors/warnings.
However Ed uses a different programming environment, and so far we were not able to make things 100% work.
I'm also convinced that (in the end) this will be resolved.

And people who know Ed and me, will understand that without any doubt we will distribute our findings/results/sources through the normal channels.
For the short term however, it is better to do some more testing to make everything more robust, to avoid confusion for all who want to built on this....


Bert

[BertTuyt]

Ed,

could you do a match (or a limited number of games) KingsRow against the Hybrid with fixed-depth (maybe 12 - 14 ply ).
This way you don't see the side effects of the impact on search-depth, and you only compare the strength of both evaluation functions.

I will also construct a Hybrid, but first I focus on the Horizon Windows Port.

Bert

[BertTuyt]

In the next weeks/months, I want to discuss the architecture of the Horizon program.
This time I want to focus on the Horizon MoveGenerator.
The MoveGenerator is one of the many MoveGen related functions in the file generate_legal_moves.v2.4.cpp file.

Function description: void generate_legal_moves(NodePnt node, WsPnt ws, int color_white, int best_move)

Input:
NodePnt node : a pointer to a tnode structure (see below)

Code: Select all

struct tnode {
	unsigned long long man_king;				// bit array [0..] man = 1 king = 0
	unsigned long long white_black;			// bit array [0..] white = 1 black = 0
	unsigned long long occ_empty;			// bit array [0..] occupied = 1 empty = 0
	unsigned int hash_key;					// the hash key related to the board position
	unsigned short int status;
	unsigned char nr_of_white_man;
	unsigned char nr_of_black_man;
	unsigned char nr_of_white_king;
	unsigned char nr_of_black_king;
	unsigned char total_nr_of_pieces;
	char depth;							// debug
	struct tnode *previous_node;
};

node->white_black BitArray containing all white pieces (man & king)
node->man_king BitArray containing all man (white and black)
node->occ_empty BitArray containing all occupied squares (white man, white king, black man, black king)

See below code:

Code: Select all

if (color_white) {

		ws->own_man = node->occ_empty & node->white_black & node->man_king;
		ws->own_king = node->occ_empty & node->white_black & ~(node->man_king);
		ws->other_piece = node->occ_empty & ~(node->white_black);

	} else {	
		
		ws->own_man = node->occ_empty & ~(node->white_black) & node->man_king;
		ws->own_king = node->occ_empty & ~(node->white_black) & ~(node->man_king);
		ws->other_piece = node->occ_empty & (node->white_black);
	};

int color_white: Side to move 1 = White, 0 = Black
int best_move: Index of the best move for this node, used for ordening. If no best move is available best_move = -1

Output:
wsPnt ws: a pointer to a work_space_move_generator structure (see below)

Code: Select all

struct work_space_move_generator {
	unsigned int max_nr_of_captures;		// to keep hold of the rule: you have to capture as many pieces as possible
	BitArray current_start_position;		// to keep the start position during capturing with a king
	unsigned int nr_of_legal_moves;		// to keep track of the total number of legal moves
	unsigned int current_move;			// to keep track of the current move
	struct move_type legal_moves[200];	// to store the legal moves
	int move_order[200];
	BitArray own_man;				// bit arrays, the names are self explaining
	BitArray own_king;
	BitArray other_man;
	BitArray other_king;
	BitArray other_piece;
	BitArray empty_field;
	unsigned int hash_key;
	int quiescence;					// is current position quiescence
	int capture;						// has color on move a forced capture
	CRITICAL_SECTION ws_lock;			// lock for parallel operation
	int first_free_move;				// used for get_next_move
	int best_move;					// save the current best move
	int best_value;					// and the current best value
	int master_thread;				// to identify the owner of this split point
	NodePnt org_node;				// the node used by the move generator
	int depth;
	int alpha;
	int beta;
	int distance_from_root;
	WsPnt parent;
	bool finished;
	sig_atomic_t cpus;
	int ActiveSplitPoints;
	int slaves[THREAD_MAX];

};

The generate_legal_moves() function updates member data elements of the work_space_move_generator structure ws (as the naming of most of the data elements in Horizon is quite straightforward , detail explanation is not always required).
ws->nr_of_legal_moves
ws->max_nr_of_captures
ws->ws->legal_moves[200], the moves are a movetype structure ( see below definition)

Code: Select all

struct move_type {
	unsigned long long start;						// The start position of the piece that moves (or captures)
	unsigned long long stop;						// The stop position of the piece that moves or captures
	unsigned long long captured;						// Bit array of pieces that are captured in this move
};

Bert

[BertTuyt]

DXP function now working here.
Started a small match Horizon - Damage.
I have also sent the files to Ed to see if things also work in his environment and computer.

Will keep you all posted.

Bert

[BertTuyt]

The engine match Damage - Horizon is still running.
So far no Horizon problems encountered.
The only issue (so far) is that I manually had to input twice a forced move into the Damage Engine (the forced move was the first Horizon move in the 2-move ballot game, maybe there was a communication timing issue within Damage, which caused the miss).

I have sent the files to Ed yesterday, and he is also now running some engine matches (one against Kingsrow, and a match Kingsrow against a Hybrid Kingsrow/Horizon based on the Horizon evaluation function).

Ed found (and corrected) some symmetry bugs in the Horizon eval function.
In the match i run now i did not (yet) correct for these bugs.
Also in this version of Horizon i did not activate/implement the parallel search, as i want to be sure that the normal sequential program has no major bugs.

The Damage version i use for this match is the same as the Culemborg program (so with parallel search and a 7p DB).

The system used is a Intel i7 940 (Quad core) with 12 GByte RAM.

The Damage Endgame DB is stored on a SSD, the 6p Horizon Endgame DB (based on Dam 2.x) is stored on a normal HD.

Match stats so far after 30 games: 9+ 21= 0- (all from the perspective of Damage)

Keep you all posted

Bert

[Rein Halbersma]

In the next weeks/months, I want to discuss the architecture of the Horizon program.
This time I want to focus on the Horizon MoveGenerator.
The MoveGenerator is one of the many MoveGen related functions in the file generate_legal_moves.v2.4.cpp file.

Function description: void generate_legal_moves(NodePnt node, WsPnt ws, int color_white, int best_move)

Input:
NodePnt node : a pointer to a tnode structure (see below)

Code: Select all

struct tnode {

	struct tnode *previous_node;
};

Output:
wsPnt ws: a pointer to a work_space_move_generator structure (see below)

Bert

Hi Bert,

Very nice of you to dissect the Horizon code here. I must admit that when I first saw the repository, I wasn't really eager to study it because I thought the code was pretty bad. As Ed already pointed out, the formatting is not very standardized, there are lots of successive if-else clauses, there is a lot of duplication of black/white code (sometimes with bugs!) etc. etc. All in all a good portion of "code smells", to use the language of the book Clean Code. However, one should of course not judge a program by its weaknesses, but by its strengths. And indeed it has many! Most of all it's a working parallel program, with a GUI, and thanks to you also DXP capable. I wish I was at that point already

In any case, I find the code you showed quite interesting. I think the "tnode" struct is missing one crucial piece of information to play a legal game of draughts: the number of moves since the last conversion move. If this counter goes above 50 ply, the position is a draw. But that detail aside, I think the code indicates that Horizon uses the copy-make approach to move generation both for the reversible and the irreversible parts of a position. But it also does not have an explicit array of hash keys to do repetition detection. Rather it uses an implicit array through pointer to the previous position.

This is also the way Don Dailey described how his CilkChess program (and its current program Komodo) works. Now we know of course that CilkChess was a very strong parallel program. Part of that was the ease of doing parallel computations by not maintaining a big global state but copying a small state and tracing history through pointers. The Cilkchess state was 192 bytes (3 cache lines) but I think the "tnode" struct of Horizon is even less than 64 bytes (single cache line!!) so the copy overhead should be a lot smaller than in a chess program. Although I have no idea how often (in % of number of move generated) a new thread is spawned, copying a big global state with a long history (several kilobytes?!) could easily be more expensive than the copy-make approach.

Rein

[BertTuyt]

Rein, thanks for your post.

Without immediately going into details like code readability, I think it is good to spent the time to try to understand the underlying program architecture.
And also to dig into the specific design principles made for functions and data-structures.
I'm convinced that everyone has brilliant ideas, which if we recognize them, can apply in our own programs. And where different choices were made, think about the pro's and con's.
And last but not least, share and discuss this in the open, like this forum.
In the next weeks i will continue to do so, and I'm sure others (including myself) will learn from this..

I have regular discussion with Ed about Draughts programming , and I guess that somewhere we still do not fully understand the reason why programs play so good, and what really is the deeper cause that some programs perform better then others. Take the Horizon program for example. Although there are some bugs in the evaluation function (which Ed is trying to resolve), it is not unlikely that after these fixes, Horizon is still not able to win a match against Damage and/or Kingsrow. On the other hand , when you see the amount of information Feike included in the Horizon evaluation function , it is strange that Horizon does not perform better.

It is also peculiar that the best programs (so far) are not always constructed by people with a huge draughts knowledge. Could it be that to create a prefect program some of the "traditional" human knowledge is less important/relevant as the search will find a way out or resolve related obstacles/threads?

And when a program like Horizon looses a match against for example Damage/Horizon is then the best way to go forward remove parts of the eval-function and improve the search, or the other way around?

Many years ago I had some thoughts about the search/evaluation optimization and that programs with the same rating (but with different evaluation knowledge and search depth) could behave different when thinking time increases or processing power improves.
Maybe we should re-discuss this some day...........

Bert

[ildjarn]

I think the "tnode" struct is missing one crucial piece of information to play a legal game of draughts: the number of moves since the last conversion move. If this counter goes above 50 ply, the position is a draw.

Slight nuance: If there are more than 50 ply since the last conversion, a draw can be claimed. This is something else than 'is a draw'.

IMO (and I've mentioned this before) computer programs shouldn't use the 50-ply rule for endgames for which the result can be proven. The 50-ply rule is a human invention to avoid endless play by humans. If a program, by using its EGTB, can prove that a position is definitely won, then it should be marked as a win, not as a draw due to the (rather arbitrary) 50-ply rule.

[Ed Gilbert]

I fixed the symmetry bugs in the voorpost eval. Horizon evaluates a voorpost formation in a similar way for the 6 advanced center squares. For black these are 27, 28, 29, 32, 33, and 34. For each square there are two functions, one for evaluating white attacks coming from the northeast direction and another from northwest. Take the example of a black voorpost on square 33. White can attack from the northeast direction by placing a backing man on 42 and an attacking man on 38. Similarly black can defend by placing a backing man on 20 and a defending man on 24. The voorpost evaluations do not consider the case where there is a backing black man on 29. It only evaluates the cases where the white attacks can result in one or more exchanges of the voorpost square. The basic idea of the eval is to count both the number of potential white attacking and black defending men, as well as the number of moves required to attain the attacking and defensive positions for the first and second waves of attacks.

For a black voorpost on 33 the candidates for a white backing man are the set {42, 47, 48}, and for the white attacking man they are {38, 43, 48, 49}. The code below identifies a backing and attacking white man and returns the number of plies required to achieve these positions.

Code: Select all

his_min_backing_steps = calc_dist_2((FLD43), (FLD48 | FLD49), &his_pieces_used, white_man);
his_min_attack_steps = calc_dist_3((FLD39), (FLD44), (FLD49 | FLD50), &his_pieces_used, white_man);

The function keeps track of which white men are used in the bitboard his_pieces_used, so that once it assigns a man to be used for backing it does not also use it for attacking.

Notice that there is a bit of overlap in the sets of backing and attacking. It is important that in identifying a backing man the priority should be to check 43 first, then 48, and 49 last. If 49 was checked before 48, then there is a potential for error because 49 can be used either for backing or attacking where 48 can only be used for backing. This is the source of the bug, because the same calc_dist_x functions are used not only for attacks from the northeast, but also for those from the northwest, and also for identifying defending pieces in the southeast and southwest directions. The calc_dist functions always search the bitboards starting at the lowest bit numbers first. This doesn't work for the case of white attacks from the northwest, as there the white backing set is {44, 49, 50}, attack set is {39, 43, 48, 49}, and 50 should be considered for backing before 49. It is also incorrect for identifying black defensive backing men from the southwest.

To fix the bugs, I wrote a similar set of calc_dist_x functions that search the bitboard sets in the opposite direction, i.e. starting at msb and advancing towards lsb, and then substituted calls to the new functions for the appropriate directions. The horizon eval now passes all symmetry tests.

-- Ed