Next steps for my engine?

[Fguy64]

Greetings. I'm looking for a few suggestions on next steps, where to take my engine from here.

What I have now is a recursive Negamax algorithm (I think) with Alpha Beta Pruning. That's it.

The engine can handle the WAC positions pretty well.

There is no quiescense at the moment. I recognize the importance, but I had trouble with the implementation so it's on the shelf for now. As I see it, the lack of a quiescence search should not prevent me from working on improving other aspects of the engine. I hope.

There's also no hash table to speak of. I can see the value of hash tables, but I have a hard time with the implementation, I find the available literature, such as that at the chess programming wiki, to be rather too advanced for my current level. I've done some very simple transposition checking, but the payoff in terms of speed has been minimal.

Dealing with time controls is not a priority for me at this time, but maybe down the road.

So if anyone has some ideas on how to ease my way into hash tables, that would be great.

Additional information about my program, including a description of the board representation and documented source code (Sun Java), is available at the website in my signature.

Thanks.

[Aleks Peshkov]

Even a dumb quiescence search is next best improvement after alpha-beta pruning.

Null-move pruning and some extensions and reductions (like LMR) may be much easier to implement and probably will gain more strength then writing a fast and bug free hash table.

[Jan Brouwer]

Greetings. I'm looking for a few suggestions on next steps, where to take my engine from here.

What I have now is a recursive Negamax algorithm (I think) with Alpha Beta Pruning. That's it.

The engine can handle the WAC positions pretty well.

There is no quiescense at the moment. I recognize the importance, but I had trouble with the implementation so it's on the shelf for now. As I see it, the lack of a quiescence search should not prevent me from working on improving other aspects of the engine. I hope.

There's also no hash table to speak of. I can see the value of hash tables, but I have a hard time with the implementation, I find the available literature, such as that at the chess programming wiki, to be rather too advanced for my current level. I've done some very simple transposition checking, but the payoff in terms of speed has been minimal.

Dealing with time controls is not a priority for me at this time, but maybe down the road.

So if anyone has some ideas on how to ease my way into hash tables, that would be great.

Additional information about my program, including a description of the board representation and documented source code (Sun Java), is available at the website in my signature.

Thanks.

Hi Fred,

Having a quiescence search is very important, I'm afraid

For a minimal baseline I would suggest
- alpha/beta search
- quiescence search with capture moves only
- use MVV/LVA move ordering of capture moves before other moves
- evaluation function with material and piece-square tables (e.g. the simplified evaluation function at the chess programming wiki)

Try to get this as bug-free as possible, and from then on only accept changes if they prove better in a few hundred games against a few different opponents.

Next step could be a simple transposition table combined with iterative deepening and time control.
The important part of a has table is get the Zobrist hash key calculation correct, perhaps have a look at one of the open source programs?

Good luck,

Jan

[jesper_nielsen]

Hello!

When I started writing an engine, a GREAT site for inspiration was Bruce Morelands programming pages. They can be found archived here:

http://web.archive.org/web/200404032117 ... /index.htm

The link is also in the Bruce Moreland entry at the chess programming wiki pages you mention.

I would strongly advice getting the quiescent search part working. The description in Bruce Morelands pages is very simple and clear I think. If not please ask here for help. People are generally very helpful here!

A great site for finding engines to compete/test against is the UCI engines ligue.

http://pagesperso-orange.fr/lefouduroi/ ... ci/uel.htm

The engines listed are all fairly stable and there are engines in all strength ranges.

Good luck with your engine!

Kind regards,
Jesper

[bob]

Greetings. I'm looking for a few suggestions on next steps, where to take my engine from here.

What I have now is a recursive Negamax algorithm (I think) with Alpha Beta Pruning. That's it.

The engine can handle the WAC positions pretty well.

There is no quiescense at the moment. I recognize the importance, but I had trouble with the implementation so it's on the shelf for now. As I see it, the lack of a quiescence search should not prevent me from working on improving other aspects of the engine. I hope.

There's also no hash table to speak of. I can see the value of hash tables, but I have a hard time with the implementation, I find the available literature, such as that at the chess programming wiki, to be rather too advanced for my current level. I've done some very simple transposition checking, but the payoff in terms of speed has been minimal.

Dealing with time controls is not a priority for me at this time, but maybe down the road.

So if anyone has some ideas on how to ease my way into hash tables, that would be great.

Additional information about my program, including a description of the board representation and documented source code (Sun Java), is available at the website in my signature.

Thanks.

You have to do a q-search first. Otherwise the ends of your PVs are going to be random noise and minimaxing random noise will lead to not-so-good play.

I would not proceed until that works. It is a tiny piece of code.

[Don]

You should do quies search next. Nothing else you can do makes any sense until you do this. It's easy, here is a way that you won't have to think too hard about:

1. create a new move call null, which does nothing to the board. It's a real move, so when white plays the null or "nothing" move, it's blacks turn to move. It should work like any other move except nothing is actually moved on the board.

2. In quies, always try the null move first, then try only captures.

3. If you want to deal with checks, try all the moves when in check.

Some program, even strong ones don't worry about checks and out of checks, just let the program capture the king but give it a super high score.

The pay-off for a quies search is huge, it's the next thing you want to have.

I wanted to make this simple, but if you don't actaully have to "make" the null move (it does nothing anyway.) Just pretend you are making it. Toggle the side to move, score the position, check to see if it's a beta cutoff, update alpha (and the best score), etc. Do everything you would do if you were actually making a real move. That is your quies search.

Greetings. I'm looking for a few suggestions on next steps, where to take my engine from here.

What I have now is a recursive Negamax algorithm (I think) with Alpha Beta Pruning. That's it.

The engine can handle the WAC positions pretty well.

There is no quiescense at the moment. I recognize the importance, but I had trouble with the implementation so it's on the shelf for now. As I see it, the lack of a quiescence search should not prevent me from working on improving other aspects of the engine. I hope.

There's also no hash table to speak of. I can see the value of hash tables, but I have a hard time with the implementation, I find the available literature, such as that at the chess programming wiki, to be rather too advanced for my current level. I've done some very simple transposition checking, but the payoff in terms of speed has been minimal.

Dealing with time controls is not a priority for me at this time, but maybe down the road.

So if anyone has some ideas on how to ease my way into hash tables, that would be great.

Additional information about my program, including a description of the board representation and documented source code (Sun Java), is available at the website in my signature.

Thanks.

[Fguy64]

Well Alright. Thanks to all for all the ideas, my hopes have been exceeded. It all looks helpful. Lots of food for thought to keep me busy for some time to come.

OK, I'm convinced about q-search, I can't put it off any longer. Thanks to Don for the extra pointers there.

Didn't know about Bruce Borland's page. I spent a few minutes looking it over. My initial impression is I like the layman's sort of explanations he gave. That sort of stuff is worth its weight in gold to me. I can see myself backtracking here and working through something even more basic than I have, in order to fill in the gaps in my knowledge before pressing ahead.

Some good info here in the thread that helped me visualize a package of improvements coming together sometime down the road.

Thanks again.

[Don]

Well Alright. Thanks to all for all the ideas, my hopes have been exceeded. It all looks helpful. Lots of food for thought to keep me busy for some time to come.

OK, I'm convinced about q-search, I can't put it off any longer. Thanks to Don for the extra pointers there.

Didn't know about Bruce Borland's page. I spent a few minutes looking it over. My initial impression is I like the layman's sort of explanations he gave. That sort of stuff is worth its weight in gold to me. I can see myself backtracking here and working through something even more basic than I have, in order to fill in the gaps in my knowledge before pressing ahead.

Some good info here in the thread that helped me visualize a package of improvements coming together sometime down the road.

Thanks again.

When I started out, I didn't have Bruce Moreland's web page. But I did have this real gem of a book called "Chess Skill in Man and Machine." In particular one chapter of that book was worth more to me than the whole rest of the book combined. It pretty much layed out how to build a chess program in simple high level terms that you could easily understand. It was an outline of how the chess 4.5 Northwestern University chess program worked. This program dominated chess for a while in the 70's and I consider it the first "modern" chess program.

Of course by todays standards, you might consider that book chapter out of date, as nobody knew about null move pruning, late move reductions, etc. But this is where I first learned about how quies search really works, the idea of taking turns standing pat, etc.

I lent that book to someone and never got it back, and I still yearn for it Maybe the book chapter is online somewhere. I'll bet you would benefit from reading it. It's extremely readable.

[Fguy64]

Well Alright. Thanks to all for all the ideas, my hopes have been exceeded. It all looks helpful. Lots of food for thought to keep me busy for some time to come.

OK, I'm convinced about q-search, I can't put it off any longer. Thanks to Don for the extra pointers there.

Didn't know about Bruce Borland's page. I spent a few minutes looking it over. My initial impression is I like the layman's sort of explanations he gave. That sort of stuff is worth its weight in gold to me. I can see myself backtracking here and working through something even more basic than I have, in order to fill in the gaps in my knowledge before pressing ahead.

Some good info here in the thread that helped me visualize a package of improvements coming together sometime down the road.

Thanks again.

When I started out, I didn't have Bruce Moreland's web page. But I did have this real gem of a book called "Chess Skill in Man and Machine." In particular one chapter of that book was worth more to me than the whole rest of the book combined. It pretty much layed out how to build a chess program in simple high level terms that you could easily understand. It was an outline of how the chess 4.5 Northwestern University chess program worked. This program dominated chess for a while in the 70's and I consider it the first "modern" chess program.

Of course by todays standards, you might consider that book chapter out of date, as nobody knew about null move pruning, late move reductions, etc. But this is where I first learned about how quies search really works, the idea of taking turns standing pat, etc.

I lent that book to someone and never got it back, and I still yearn for it Maybe the book chapter is online somewhere. I'll bet you would benefit from reading it. It's extremely readable.

lots of hits on google, including several references to a specific chapter on chess4.5 I think it was. Lots of chances to buy, but no samples that I could see. Thanks for the tip. Maybe I'll buy it, or see if the library has it. I'll keep my eyes open as I browse the used bookstores.

Anyways, I have no problem with outdated material, if it leads to better understanding of the present. I often google for programming instruction, and often find gems that have been around for ten years or more. It may not apply directly, but lo and behold when I return to current material I have struggled with, it makes much more sense.

[Dann Corbit]

After quiescent search, hash table is a must.
Many other techniques will depend on it (like IID).
Other things become much easier because of it (like repetition detection).
Use Zobrist hashing.
Always make two versions of your hash function:
1. Incremental hash that updates the hash entry with XOR of the tiny change of the last makemove() or unmakemove()
2. Full hash that iterates over the full board to recreate the hash from scratch.

Then have a special compile option that will check every hash update by performing both the full hash every time you incrementally update it and check the value to make sure it is OK.

A debugged hash function is the start of a strong chess program. A buggy hash will cause many nightmares.