What next?

[evandam]

Ok so I have a Friday night to program, but I'm struggling to figure out what to do next.

A little background.

- square-centric board representation, 10x12 Mailbox to be exact which stores char piece representations.

- Alpha Beta search algorithm with queiscene search at terminal nodes. I iteratively deepen and save the PV's from the previous search and they are first in the move ordering followed by captures, checks, pawns, others

- My eval is materiel, center control (quantified by attacking center squares) and attacking around the king. So it is pretty minimal. No positional elements etc. This seems hard to quantify when you do make a change, so I have been kind of putting it off until I can dedicate a computer to testing.

- The code is bug free at this point and passes every perft test i can throw at it.

It has got to where it beats me (not a big feat). But any of the engines you can get online will absolutely smoke me. Anyone have any BAD engines to test with. I'm getting tired of bearing up on previous versions of my engine.

I think move generation speed may be one of the issues i'm having. I'm generating aprox 500k nps in my perft (At work so I don't have an exact #). So I think my MakeMove and UndoMove are probably terribly ineffiecient. Also when I search the same position my nps probably drop to maybe 80k (which seems drastic to me since my eval is pretty simple). When I started this code I was really just trying to get an engine to play a legal game. Seriously my search initially started out as selecting a random legal move. So that is what I'm leaning towards doing tonight. I see some of these programs generating millions of nps in a perft and I hope they are all bitboard engines or i guess I have some serious problems.

So does anyone have any suggestions from streamlining my move generation and search/eval to squeeze out a few more nps?

Hash tables are on the table, but I'm still not quite clear on how they are used/updated etc. So that would require some research time on my part.

Any other suggestions based on how to proceed are appreciated.

I'm just looking for what would give me the best bang for my buck from my evening of programing I have.

[Dann Corbit]

Ok so I have a Friday night to program, but I'm struggling to figure out what to do next.

A little background.

- square-centric board representation, 10x12 Mailbox to be exact which stores char piece representations.

- Alpha Beta search algorithm with queiscene search at terminal nodes. I iteratively deepen and save the PV's from the previous search and they are first in the move ordering followed by captures, checks, pawns, others

- My eval is materiel, center control (quantified by attacking center squares) and attacking around the king. So it is pretty minimal. No positional elements etc. This seems hard to quantify when you do make a change, so I have been kind of putting it off until I can dedicate a computer to testing.

- The code is bug free at this point and passes every perft test i can throw at it.

It has got to where it beats me (not a big feat). But any of the engines you can get online will absolutely smoke me. Anyone have any BAD engines to test with. I'm getting tired of bearing up on previous versions of my engine.

Youk is the weakest stable engine:
http://wbec-ridderkerk.nl/html/5thdiv.htm

I think move generation speed may be one of the issues i'm having. I'm generating aprox 500k nps in my perft (At work so I don't have an exact #). So I think my MakeMove and UndoMove are probably terribly ineffiecient. Also when I search the same position my nps probably drop to maybe 80k (which seems drastic to me since my eval is pretty simple). When I started this code I was really just trying to get an engine to play a legal game. Seriously my search initially started out as selecting a random legal move. So that is what I'm leaning towards doing tonight. I see some of these programs generating millions of nps in a perft and I hope they are all bitboard engines or i guess I have some serious problems.

So does anyone have any suggestions from streamlining my move generation and search/eval to squeeze out a few more nps?

Hash tables are on the table, but I'm still not quite clear on how they are used/updated etc. So that would require some research time on my part.

Any other suggestions based on how to proceed are appreciated.

I'm just looking for what would give me the best bang for my buck from my evening of programing I have.

Move generation is not nearly so important as reducing the branching factor.

Hash tables really are a must, because they are helpful for many other things, like move ordering (which will reduce your branching factor).

Do a web search for "Zobrist hash". It's what everyone uses and quite simple.

[Dann Corbit]

Another very important thing is a move list.
If you scan all 64 squares to examine the board, you are throwing a lot of time in the toilet.

[evandam]

Another very important thing is a move list.
If you scan all 64 squares to examine the board, you are throwing a lot of time in the toilet.

I have a piece list which tells me which squares have pieces on them, is this what you mean. I don't differentiate what the piece is, just that there is one there. I use this when generating moves so I don't have to scan the whole board.

[Dann Corbit]

Another very important thing is a move list.
If you scan all 64 squares to examine the board, you are throwing a lot of time in the toilet.

I have a piece list which tells me which squares have pieces on them, is this what you mean. I don't differentiate what the piece is, just that there is one there. I use this when generating moves so I don't have to scan the whole board.

Yes, that is what I was referring to. Many chess programs scan the whole board in the beginning. It's a killer when the board is sparse (e.g. look at 7 chessmen instead of scanning 64 squares).

[Dann Corbit]

Another very important thing is a move list.
If you scan all 64 squares to examine the board, you are throwing a lot of time in the toilet.

I have a piece list which tells me which squares have pieces on them, is this what you mean. I don't differentiate what the piece is, just that there is one there. I use this when generating moves so I don't have to scan the whole board.

Yes, that is what I was referring to. Many chess programs scan the whole board in the beginning. It's a killer when the board is sparse (e.g. look at 7 chessmen instead of scanning 64 squares).

I should have said "a piece list" and not "a move list".
I used the wrong terminology but fortunately, you saw through the smoke.

[Roman Hartmann]

Hi,
congratulations to your chess engine. In writing something on your own you did already more than a lot of other "chess programmers".

Anyway, don't expect your first chess engine to be a match for all those strong engines out there. Many of these took years to get as strong as they are now.

I don't know how strong/weak your engine is. But one of the most important things is definitely move ordering. You might want to look up and read about MVV/LVA (Most valuable victim/least valuable attacker).

Null-move-pruning is also rather easy to implement and if done properly it should improve playing strength of your engine quite a bit.

LMR (Late move reduction) is also rather simple to implement and it might help you either a lot a bit or maybe not at all. My personal experience with LMR is that you need a good QS or otherwise it might even hurt playing strength.

Move generation/move making/unmaking might be a bottleneck of your engine but don't get mislead by engines which generate millions of nodes per second. Generating/making/unmaking millions of moves (half-moves) per second is not necessary to create a strong engine. Also be aware that some of the fastest engines don't actually make the moves at the leafs but only count them (while perfting that is).

Improving the move generation/move making/unmaking process won't help playing strength much at this rather early stage of engine development. So better improve this part later when you did all the other more important things. Having a bug free move-generation/making/unmaking process is a must, having also a really fast move-generation/... process is nice but not necessary.

Roman

[smatovic]

Hi Erik,

I Anyone have any BAD engines to test with. I'm getting tired of bearing up on previous versions of my engine.

Try my
https://github.com/smatovic/zeta_dva/tr ... _dva_005-6

Like Roman and Dan mentioned move ordering is pretty important for alpha-beta algorithm and i think it is faster to implement than Transposition Tables.

If you consider that ~ 90% of searched nodes are in Q-Search than MVV-LVA or SEE is a must. You can also use TT to pick a bestmove first.

If you got an legal-move generator then you could get a speedup by optimizing checkmate functions in search/eval.

The move generator i use returns for example 0 if there are no legal moves left, this means the side to move is in checkmate or stalemate...so i dont need to check every search iteration if the board is in checkmate with an own function because the move generator will tell me and this information i can pass to my evalfunction.

--
srdja

[evandam]

Thanks for the tips guys.

I started a TTHash in a branch, but went on to MVVLVA instead. That seems to help a bit. I'm also going to look into Null Move Pruning next.

The TTHash is still a bit of a mystery. I have the ZHashKey almost done and tested with my make and unmake move functions, but I'm still sketchy on replacing them, what to store and how to use it in my search. I'm sure it will come.

Have not had a chance to try the engine one of you posted, but I will soon.

Thanks again.

[Dann Corbit]

Thanks for the tips guys.

I started a TTHash in a branch, but went on to MVVLVA instead. That seems to help a bit. I'm also going to look into Null Move Pruning next.

The TTHash is still a bit of a mystery. I have the ZHashKey almost done and tested with my make and unmake move functions, but I'm still sketchy on replacing them, what to store and how to use it in my search. I'm sure it will come.

Have not had a chance to try the engine one of you posted, but I will soon.

Thanks again.

The magic of the zobrist hash is that it uses xor.

Since you are using xor, the same operation that added a chessman on a square is the operation to subtract the chessman.