Effective Branching factor

[Filipe Maia]

Hi!

I use a tranposition table, internal iterative deepening (when there is no tt move), SEE sorting, killers, history heuristics, null move and futility pruning yet my branching factor is not so good (average is around 2.90). I know I have a really crappy evaluation function (a copy of TSCP) so i wonder how much would by move ordering improve with a better evaluation function? Or is the evaluation function almost irrelevant for move ordering?

Am i missing any important move ordering algorithm?

[Uri Blass]

I think that you have no permission to use tscp functions in elturco without permission from the author of that program.

The fact that you even did not mention his name in Elturco source(score.c) is not acceptable.

calling the evaluation of tscp "really crappy evaluation function" after you use it is even worse.

The evaluation has nothing to do with bad branching factor.
A possible reason of bad branching factor is bugs and if you start by code of other people(tscp for evaluation book for Crafty) then I am not surprised if you have bugs.

I wonder if you did not took more code from other programs except evaluation code and book code.

I think that if you want to develop your chess program it is better if you start with something really simple(only material and piece square table) and simple alpha beta without pruning and improve from it.

addition:I only now see that you mention 2.90 as your branching factor and 2.90 is not a bad branching factor so I wonder why you considered it as bad.

Uri

[Uri Blass]

I sent an email to Tom kerrigan about using tscp code in El turco.

Uri

[Filipe Maia]

You are right, i thought TSCP's code was free. I used a copy of the evaluation function so i could compare my results with those obtained from TSCP. I will remove the function from the code in the next release.

When I said it was a crappy evaluation what i meant was that it was very simple (like the name of the program says).

By the way about not having any reference to TSCP if you look in score.c you will see this comment:

/* Code taken from TSCP!! */

And if you look at readme.html you will see "El Turco uses the same scoring function as TSCP from Tom Kerrigan."

and

"If there is any code in El Turco that is infringing any copyright please contact me and I will remove it as soon as possible."

So I will act as i said i would, by removing the evaluation function.

[Filipe Maia]

I considered 2.90 bad because it looked like that on longer time controls el turco would get depths much lower than gnuchess, yet it was getting pretty much the same depth at fast time controls.

This was a subjective evaluation so i could be wrong.

[Uri Blass]

What gnuchess was used?
There is gnuchess4 and there is gnuchess5.

I am surprised if gnu has a better branching factor than 2.90.

I guess that you usually can get depth 2 in less than 200 nodes and
200*2.9^12~70,000,000

If you get depth 14 even with only 100,000,000 nodes in the opening position then your branching factor is normal.

In the opening position a lot of good program are unable to get depth 14 with 100,000,000 nodes(for example yace with 64 mbytes hash finish depth 14 with 40,121 Knodes and need 97,490 knodes to get score at depth 13) and the opening position is not a position when it is extremely hard to go deep.


Fruit1.5 needs 87310 nodes to get a score at depth 14

New game - ChestUCI Ver.2.6, Blitz:2' Tel-Aviv
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Analysis by Fruit 1.5:

1.Na3
? (0.26) Depth: 1/1 00:00:00
1.Nc3
? (0.54) Depth: 1/1 00:00:00
1.Nc3 Nc6
= (0.00) Depth: 2/2 00:00:00
1.Nc3 Nc6 2.Nf3
? (0.54) Depth: 3/4 00:00:00
1.Nc3 Nc6 2.Nf3 Nf6
= (0.00) Depth: 4/6 00:00:00
1.Nc3 Nc6 2.Nf3 Nf6 3.d4
? (0.47) Depth: 5/9 00:00:00
1.Nc3 Nc6 2.Nf3 Nf6 3.d4 d5
= (0.00) Depth: 6/12 00:00:00 4kN
1.Nc3 Nc6 2.Nf3 Nf6 3.d4 d5 4.Bf4
? (0.42) Depth: 7/15 00:00:00 19kN
1.Nc3 Nf6 2.Nf3 Nc6 3.d4 d5 4.Bf4 Bf5
= (0.00) Depth: 8/20 00:00:00 43kN
1.Nc3 d5 2.d4 Nc6 3.Bf4 Nf6 4.Nb5 e5 5.dxe5 Bb4+ 6.c3
? (0.26) Depth: 9/20 00:00:01 226kN
1.e4 Nc6 2.Nc3 Nf6 3.Nf3 d5 4.exd5 Nxd5 5.d4
? (0.31) Depth: 9/20 00:00:01 305kN
1.e4 Nf6 2.Nc3 Nc6 3.d4 d5 4.e5 Ne4 5.Nf3 Bf5 6.Nxe4 Bxe4
= (0.03) Depth: 10/31 00:00:03 954kN
1.Nc3 d5 2.d4 Nc6 3.Bf4 Bf5 4.Nb5 Rc8 5.Nf3 Nf6
= (0.11) Depth: 10/31 00:00:04 1183kN
1.Nc3 Nc6 2.d4 e6 3.Nf3 Nf6 4.e3 Bb4 5.Bd2 0-0 6.Bd3
? (0.27) Depth: 11/31 00:00:09 2544kN
1.Nc3 Nc6 2.d4 d5 3.Nf3 Nf6 4.Ne5 Bf5 5.Nxc6 bxc6 6.Bf4 e6
= (0.13) Depth: 12/33 00:00:16 4632kN
1.Nc3 d5 2.d4 Nf6 3.Nf3 Nc6 4.Ne5 Nxe5 5.dxe5 d4 6.Nb5 Ng4 7.Bg5
= (0.20) Depth: 13/36 00:00:52 15144kN
1.e4 Nc6 2.Nc3 Nf6 3.Nf3 d5 4.exd5 Nxd5 5.d4 Bg4 6.Bb5 e6 7.0-0
= (0.23) Depth: 13/40 00:01:18 22629kN
1.e4 e5 2.Nc3 Nf6 3.Nf3 Bb4 4.a3 Bxc3 5.dxc3 Nc6 6.Bc4 h6 7.Qe2 d6
= (0.13) Depth: 14/46 00:04:51 87310kN

(Blass, Tel-Aviv 07.12.2004)



Uri

[Uri Blass]

You are right, i thought TSCP's code was free. I used a copy of the evaluation function so i could compare my results with those obtained from TSCP. I will remove the function from the code in the next release.

When I said it was a crappy evaluation what i meant was that it was very simple (like the name of the program says).

By the way about not having any reference to TSCP if you look in score.c you will see this comment:

/* Code taken from TSCP!! */

And if you look at readme.html you will see "El Turco uses the same scoring function as TSCP from Tom Kerrigan."

and

"If there is any code in El Turco that is infringing any copyright please contact me and I will remove it as soon as possible."

So I will act as i said i would, by removing the evaluation function.

Ok I see that I was wrong here and you mentioned the fact that you took code from tscp so I was probably too aggresive and your case is at least better than previous cases of tscp clones when the author did not mention tscp,but I know from the past that Tom does not allow other people to use the same evaluation.

Uri

[Filipe Maia]

I really wasn't aware of that.
Do you know of any piece square tables that i can use in the program?
I'll try to replace the function asap and use the opportunity to implement the pawn
structure hash function.

Here are the results from the analyze:
xboard
post
setboard rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
go
1 48 0 47 e4
2 0 0 170 e4 e5
3 35 0 1359 e4 d5 Nc3
4 12 0 4164 e4 Nf6 e5 Ne4
5 35 2 26290 e4 e5 Nc3 Nc6 Nf3
6 13 5 61324 e4 e5 d4 exd4 Qxd4 Nc6 Qd1
7 30 41 546182 d4 d5 Nf3 Nf6 Nc3 Nc6 e3
8 14 153 1828470 e4 e5 Nf3 Nc6 d4
9 25 569 7004267 Nc3 d5 d4 Nf6 Nf3
10 18 1428 17148395 d4 d5 Nc3
11 28 4043 47635439 d4 d5 e3 Nf6 Nc3 Bg4 f3 Be6 Bd3 Nc6 Nge2
12 22 14058 162782964 e4 e5 Nf3 Nc6 Bb5 Bc5 d3 Nge7
13 25 43286 494936761 e4 e5 Nf3 Nc6 Nc3 Nf6 Bb5 Bb4 Nd5 Bc5 Nxf6 Qxf6 O-O O-O d3
14 24 119959 1340779259 e4 e5 Nf3 Nc6 Nc3 Nf6 Bb5 Bb4 Nd5 a5 Nxb4 axb4 d3 Ra5

1340779259 nodes (it includes quescient nodes), way to much i think.

The way I calculated the average EBF was to average all the EBF of all my games. This includes end game EBF and that's why the value looks better than it is.
It would be nice if there were some sets of positions from which one could evaluate his branching factor.

[Filipe Maia]

The gnuchess version used was 5.07.

[Uri Blass]

I really wasn't aware of that.
Do you know of any piece square tables that i can use in the program?
I'll try to replace the function asap and use the opportunity to implement the pawn
structure hash function.

Here are the results from the analyze:
xboard
post
setboard rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
go
1 48 0 47 e4

Movei get exactly 20 nodes at depth 1
I wonder how do you get more than it
because I assume no qsearch and extensions in the first ply.

2 0 0 170 e4 e5
3 35 0 1359 e4 d5 Nc3
4 12 0 4164 e4 Nf6 e5 Ne4
5 35 2 26290 e4 e5 Nc3 Nc6 Nf3
6 13 5 61324 e4 e5 d4 exd4 Qxd4 Nc6 Qd1
7 30 41 546182 d4 d5 Nf3 Nf6 Nc3 Nc6 e3
8 14 153 1828470 e4 e5 Nf3 Nc6 d4
9 25 569 7004267 Nc3 d5 d4 Nf6 Nf3
10 18 1428 17148395 d4 d5 Nc3
11 28 4043 47635439 d4 d5 e3 Nf6 Nc3 Bg4 f3 Be6 Bd3 Nc6 Nge2
12 22 14058 162782964 e4 e5 Nf3 Nc6 Bb5 Bc5 d3 Nge7
13 25 43286 494936761 e4 e5 Nf3 Nc6 Nc3 Nf6 Bb5 Bb4 Nd5 Bc5 Nxf6 Qxf6 O-O O-O d3
14 24 119959 1340779259 e4 e5 Nf3 Nc6 Nc3 Nf6 Bb5 Bb4 Nd5 a5 Nxb4 axb4 d3 Ra5

1340779259 nodes (it includes quescient nodes), way to much i think.

The way I calculated the average EBF was to average all the EBF of all my games. This includes end game EBF and that's why the value looks better than it is.

Yes and positions when the program got deep got higher weight.

It would be nice if there were some sets of positions from which one could evaluate his branching factor.

[Filipe Maia]

Movei get exactly 20 nodes at depth 1
I wonder how do you get more than it
because I assume no qsearch and extensions in the first ply.

I believe the reason for this are the following:
-I was increasing node_count in negamax before calling quiescent().
By reversing the order the node count change to 24.
-I have 1 extra node because I count the root node (no moves made)
-The other 3 are caused by re-searches due to the the result of a negamax coming out
of the minimal windows (i use -INF +INF in the root and for the PV nodes but all the others are searched with alpha,alpha+1). At depth 1 the ordering is terrible so it's not uncommon for this to happen.

[Filipe Maia]

Output with node_count++ and quiescent reversed:

1 48 0 24 e4
2 0 0 98 e4 e5
3 35 0 753 e4 d5 Nc3
4 12 0 2545 e4 Nf6 e5 Ne4
5 35 2 14931 e4 e5 Nc3 Nc6 Nf3
6 13 5 35879 e4 e5 d4 exd4 Qxd4 Nc6 Qd1
7 30 42 321168 d4 d5 Nf3 Nf6 Nc3 Nc6 e3
8 14 158 1130716 e4 e5 Nf3 Nc6 d4
9 25 653 4638434 Nc3 d5 d4 Nc6 Nf3 Nf6 e3 e6 Bd3
10 18 1790 12618681 d4 d5 Nc3 e6
11 28 5862 39705874 d4 d5 e3 Nf6 Nc3 Bg4 f3 Be6 Bd3 Nc6 Nge2
12 20 22597 157248232 e4 e5 Nf3 Nf6 d4 Nxe4 Bd3 d5 Nxe5 Be7 Bxe4
13 25 79366 544837258 e4 e5 Nf3 Nc6 Nc3 Nf6 Bb5 Bb4 Nd5 Bc5 Nxf6 Qxf6 O-O O-O d3
14 24 198719 1387208128 e4 e5 Nf3 Nc6 Nc3 Nf6 Bb5 Bb4 Nd5 a5 Nxb4 axb4 d3 Ra5

[Filipe Maia]

I have removed the TSCP code from my engine and replaced it with code from Faile (which, I checked, is MIT licensed so I can use the code).

I have released a new version with no TSCP code.
http://xray.bmc.uu.se/~filipe/elturco/