NPS

[Chan Rasjid]

I forgot to mention I am using int _board[256] with int * board = _board+64

and apply 0x88 stuff with 'border' squares

Any way, I am wondering maybe I should withdraw my original assumptions

But even if I were not using the most efficient approaches to things, it still didnt seem I should suffer 100-200% slow-down.

Am I wrong?

If I could have managed to spend 3x longer than others in my prob-hash() routine, eg., that is still relatively insignificant [ie., not near 100-200%]

My InCheck() routine is similar in kind to TSCP's.

Now, InCheck() is in the top 2 routines when profiling [ IIRC 30-40%]

But even this, If I were doing it less than perfectly, couldnt account for 100-200% slow down in over-all NPS

I have tried rewriting these, but it hardly seems to matter.

InCheck() Gen() Eval()

Just looking for some help as to where I might look next. I ran out of ideas.....

I dont even collect attack information!

Hello David,

I'm not sure how serious you take chess programming (or the hobby).
If you have the slightest interest to write a fairly strong program, I believe there are good reason to start on some good basic foundations
as changes with a good starting foundation don't need "rewriting from scratch" as Uri discussed (not necessary) .

I know all along my recent Snailchess is the slowest in the world, but I am
aware of what I am doing, just as an experiment. When I come to
move_order, snailchess almost has full chess information for order(), eval() and gen() all legal moves with full checking status. But it does not work too well .

I then compiled Fruit and on my P4 1.4 Ghz, snailchess's nps is 40k at game start. Fruit's has 130-150k (I think tscp about 100k). So I reverse
direction and I am doing the NPS route now.

1) int _board[256]- good to ask other's if you should try char.
Even Ed uses unsigned cha WB[64], BB[64] for attack tables.
I'm quite sure char board[128/256] suffice somehow.
2) Decide on using piece list (unsorted ok ) early - ie. piece_count[w/b]
number of elements for both colors updated incrementally at
do/undo(). The good thing is when you restore a captured pc on undo(),
it is the move after the list, so it's easy.
You need to keep permanent 16 x 2 piece_type(PC) and the piece-list
has the index of the PCs.
3) What I am doing now don't need any incheck() function. Just do() a
move and when gen() at next ply, gen() in the order bishop, rook,
queen, .... and if ther is "capture" king, previous move is invalid and
gen() returns.
4) You can eliminate some easy(trivial) illegal king's move when a king's
to-sq runs into the attack-bitboards of opponent pawns/knights/king.
Pawns attack bitboard is the cheapest, done in parallel.
N/K can be done by precalculating the bitboard at sq D4 and then
shift by ranks, file to the appropriate square and mask by bits of the
file of sq + 1 or 2 side files. These simple bitboards also allow easy
determination of checkmoves of pawns/knight/king and so no need
to call incheck() here. When a B/R/Q captures a king and returns,
collect the
struct{
int attacker_capture_king_sq;
int brq_step.
}
and with these info you may list thru the remaining move and
can know which balance of moves in your list are xray-invalid.
Fo the list 1 ply down, you can know similar "xray-checks" and set the
move bits, again no need incheck() again(in most cases).

There may be more details which you can know yourself.

I have my PC and board strutures:

Code: Select all

typedef struct{
 char on;
 char c;
 char pc;
 char sq88;
 unsigned long info;
}PC;

PC piece[2][16];
char board[128];
char pcInd[2][16];


Hope these helps.

Rasjid

[David Weller]

Thanks Rasjid.

1. I was beginning to wonder about my data structures.

Currently PST's are int pst[16][192] which I think could be int pst[16][128]
and even char pst[16][128] or even char pst[12][120]

Is it possible that moving from int pst[16][256] to char[12][120] could be _VERY_ significant ?

2. Piece lists were on my todo list

3. I did this in quies() but when I was having some trouble, I thought to elliminate anything 'illegal' from the search. In fact, I only return draw at true 3 repetitions

4. currently I do not generate any attack information in do/unmove() so this information isnt available -[in GES I did this though]

Thank you for your input

[Sven Schüle]

Hi David,

when asking why your program is 2 or 3 times slower than expected, I think you may safely skip all these little optimization tricks, like 120 or 128 as array size, or char vs int. Even if you take all these tricks together I assume you won't get a factor 2 in result.

The key must be in algorithms. If you speed up your InCheck (profiled with 40% of total time) on the algorithmic level you may get 30% speedup from there. But perhaps you can do much more in search?

Just my 2 cents!

Sven

[Eduardo Waghabi]

I know that could sound incredibly dumb, and since you?re writing your second engine, it couldn?t possibly be that, but...

I started coding my first chess engine exactly 2 months ago, and one of my very first versions ran at about 30-40k. Since it was a very simple bitboard engine with a material + piece-square tables only, no fancy stuff, I was obviously very disappointed.

Later I found out I had declared my constant piece-square tables locally inside the eval() function. Making them global got me an instant 120% boost.

I?m that stupid.

With that in mind, you probably shouldn?t hear what I?m saying, and I would say that 30-40% for a InCheck routine is just outrageous. In my tests my InCheck takes less than 5%, but maybe this is the case where YMMV.

Like Chan (above), I don?t generate legal moves either, but I had to code an InCheck in order to easily detect mates, stalemates, and I knew later I would need it for extensions and null-move. In fact I would like to know from Chan how does he handle that without an InCheck routine.

[mathmoi]

I know that could sound incredibly dumb, and since you’re writing your second engine, it couldn’t possibly be that, but...

I started coding my first chess engine exactly 2 months ago, and one of my very first versions ran at about 30-40k. Since it was a very simple bitboard engine with a material + piece-square tables only, no fancy stuff, I was obviously very disappointed.

Later I found out I had declared my constant piece-square tables locally inside the eval() function. Making them global got me an instant 120% boost.

Hi,

I already have done that kind of error:

Code: Select all

void SomeFunct()
{
const int tab[64] = {...};
}

I thought that since tab was const it won't be initialized each time the function is runned. I was wrong, and I now know why it is not.

I kept the tab local, I just maked it static :

Code: Select all

static const int tab[64] = {...}

[David Weller]

Thanks Andrew, Sven, Eduardo, and mathmoi

My propensity for mistakes is infinite, so anything is possible.

There must be some sort of algorithmic bug since I think it is unlikely that even several inefficiencies would add up to 100-200% ... I am working on getting a decent trace output for search ...

Thanks again for your help

[Chan Rasjid]

Later I found out I had declared my constant piece-square tables locally inside the eval() function. Making them global got me an instant 120% boost.

I?m that stupid.

With that in mind, you probably shouldn?t hear what I?m saying, and I would say that 30-40% for a InCheck routine is just outrageous. In my tests my InCheck takes less than 5%, but maybe this is the case where YMMV.

Like Chan (above), I don?t generate legal moves either, but I had to code an InCheck in order to easily detect mates, stalemates, and I knew later I would need it for extensions and null-move. In fact I would like to know from Chan how does he handle that without an InCheck routine.

Hello Edwardo,

Firstly if you used :-

int eval(){
static const char PST[][128] ={
.........


};

}

I believe it may even be 3-5% faster if PST not needed elsewhere and never 120% slower(caveat I am a non-expert!).

My former slowest snailchess has full legal moves so the question of knowing incheck for extention.etc did not apply. I am currently rewriting using the "capture-king invalid" approach.

Capture king invalid by P/N/K is trivial and adding it in gen() by setting
bits flag may be used in order(). Adding this in incheck() after do() will miss ordering check moves high. Only sliding_attack() is the very expensive thing to put inside incheck() and called after every do().

Without incheck(), we first have to take care no capture king by P/N/K.
On capture-king-invalid, we collect (assuming 0x88):-
struct {
int attacker-sq;
int step;
}

We have 3 cases:-
1) king's move-to square attacked by B/R/Q - exceptional treatment needed.
2) move-from opens up xray attack(thus invalid) by B/R/Q -
Then we can list thru the remaining balance of moves and detemine
all similar xray-invalid moves of the current piece.
3) move is check-invalid as we have no incheck() calls -
This case means ply 1 below has a sliding check of king (a check path).
We list thru for ply 1 below
a) if this attack path is opened by the move_to of current-move ply 1
below, similar xray-check by the same piece is easily detected and
bits flag set
b) if case a) do not apply, then move-to is a 1-time direct B/R/Q check
and we cannot detemine any extra check moves in the list.

As my current re-write is not yet completed, I may miss some details, like
not detecting incheck status the first time for B/R/Q.,etc. I believe you will have some idea of what can be done and probably most strong prgroams like crafty/fruit must be doing something similar - simply because sliding attack is the most expensive.

Thanks
Rasjid

[Pallav Nawani]

Thanks Andrew, Sven, Eduardo, and mathmoi
My propensity for mistakes is infinite, so anything is possible.

There must be some sort of algorithmic bug since I think it is unlikely that even several inefficiencies would add up to 100-200% ... I am working on getting a decent trace output for search ...

Thanks again for your help

Hi david,

40% of time in in_check() is way too high, you definitely have a problem there. If the routine is correct, maybe you are calling it too many times, and some calls can be avoided? Are you using a pawn hash? That can speed things up quite a bit as well. Take a look at your code and see if you are doing unnecessary things?

Recently I found out (with some help in this forum) that I was calling check_for_input() (or the bioskey()) function too many times, fixing that got me a 15% increase in NPS.

bye,
Pallav

[David Weller]

Hi All,

Pallav, I was wrong - it is only around 10%

Still no change with the NPS however.

Had an 8 game match Xpdnt vs Fruit20-fast 4 wins 4 draws but since a few bug repairs, 7 losses 1 draw ... dont you hate that?

Of course I dont consider 8 games conclusive, but ... hey its gotta mean something