Next steps for my engine?

[Sven]

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.

I have difficulties to see why this explanation makes quiescence search easier to understand. Why do you introduce the "null" move here and mix it with the qsearch? Is it a way of expressing the "stand pat" principle?

I'd propose not to follow that path with the "null" move for implementing quiescence search. QS can be simply explained like this:

- If the maximum search depth (horizon) is reached within the full width search and the moving side is not in check then the value of the current position is determined by a quiescence search (QS).

- Within QS, the value from the viewpoint of the moving side is at least the static evaluation of the current node, because we assume for simplicity that the moving side is not forced to capture anything.

- If there is a capture sequence which the moving side can enforce and which leads to a value better than the static evaluation then this is the QS value. So at each QS node, the moving side "decides" whether to start (or continue) a capture sequence or stick with the current static evaluation. Therefore evaluate() is always called first, then all captures are generated and tried in a "good" order.

- Move ordering within QS is important since this is by far the largest part of the whole search tree (often 80-90% of all nodes). Use the simple MVV/LVA.

- QS follows the normal rules of alpha-beta search.

I think that's it, and together with the Bruce Moreland page you should be able to implement this tiny piece of code. Generating only captures could, as a first but inefficient step, be simulated by generating all moves but selecting only captures for the search while discarding all others. Many efficiency improvements are possible in QS but can initially be skipped until later.

Sven

[Don]

I have difficulties to see why this explanation makes quiescence search easier to understand. Why do you introduce the "null" move here and mix it with the qsearch? Is it a way of expressing the "stand pat" principle?

Yes. This is a trivial concept to you and I, but not to him. Once the light bulb goes off he will understand it and it will seem trivial to him too.

He only needs to understand that you can stand pat and stop, but that standing pat is optional.

When I first implemented this as a kid, I missed the point that you must handle it like any other move. If it produces a beta cutoff handle it like you played a real move that produced a beta cutoff. And like a real move you have the option of either playing it, or trying to find something better.

I don't think you are putting yourself in his shoes. Your explanation is more technical and Fred already admitted he has trouble wrapping his head around computer chess concepts since he is so new at the game.


Anway, it totally amazes me how someone always rises to occasion -- the occasion to prove the saying that "no good deed goes unpunished."

[Fguy64]

I think as much as anything it's terminology. Initial readings on quiescence went over my head because even individual words were loaded with meaning that required lots of thought.

Anyways, that probably illustrates that I was getting ahead of myself. When I started this thread, I thought I'd be able to leave q on the shelf for a little while. But no, so now I'm gonna take a couple of steps back, refocus and reinforce on the basics, before I take another run at quiescence. So I expect It'll be few weeks before I return to this thread to look at the q stuff in detail.

[Don]

I think as much as anything it's terminology. Initial readings on quiescence went over my head because even individual words were loaded with meaning that required lots of thought.

Anyways, that probably illustrates that I was getting ahead of myself. When I started this thread, I thought I'd be able to leave q on the shelf for a little while. But no, so now I'm gonna take a couple of steps back, refocus and reinforce on the basics, before I take another run at quiescence. So I expect It'll be few weeks before I return to this thread to look at the q stuff in detail.

Keep us posted on your progress and don't be afraid to ask questions on the forum as they arise.

- Don

[JVMerlino]

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.

Everything that Dann says about hash tables is true, except that I think it doesn't have to be the next thing you do after qsearch. You should do it only when you feel like you fully understand it, preferably after looking at several other engine's implementations.

After qsearch (with MVV/LVA move ordering, which is essential), I actually implemented null move, extensions (just check and single reply) and late move reductions. These are much easier to understand and implement correctly (and, more importantly, debug when they don't work), and will give you the satisfaction of very noticeable improvement.

But, of course, if you do feel comfortable with hash tables, then Dann is right and you can jump into that deep end whenever you want. They're very easy to turn on and off, so you don't have to worry about permanently breaking your engine if you get it wrong. But getting it right (and I'm not 100% convinced that I have) will open the door to many other improvements (and debugging nightmares).

jm

[Fguy64]

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.

Everything that Dann says about hash tables is true, except that I think it doesn't have to be the next thing you do after qsearch. You should do it only when you feel like you fully understand it, preferably after looking at several other engine's implementations.

After qsearch (with MVV/LVA move ordering, which is essential), I actually implemented null move, extensions (just check and single reply) and late move reductions. These are much easier to understand and implement correctly (and, more importantly, debug when they don't work), and will give you the satisfaction of very noticeable improvement.

But, of course, if you do feel comfortable with hash tables, then Dann is right and you can jump into that deep end whenever you want. They're very easy to turn on and off, so you don't have to worry about permanently breaking your engine if you get it wrong. But getting it right (and I'm not 100% convinced that I have) will open the door to many other improvements (and debugging nightmares).

jm

Thanks.

I've played a little bit with hash tables, I guess, though it was just brute force transposition checking, and there didn't seem to be much if any payoff in terms of time. My impression is that it is something you can ease your way into slowly, but I can't really speak with authority on that point.

Anyways, after some unhappy experiences with wasted work and backtracking, I'm now very careful with revisions and backups of last known good etc, so It's no problem to code things and then just throw it away if it doesn't work. Turning it off/on is something I'll keep an eye out for. I suppose I could do the same thing for q-search if I wanted to. It'd be usefull for comparison purposes.

[plattyaj]

I've played a little bit with hash tables, I guess, though it was just brute force transposition checking, and there didn't seem to be much if any payoff in terms of time. My impression is that it is something you can ease your way into slowly, but I can't really speak with authority on that point.

From one of your other posts you don't have iterative deepening. Without that you won't see the huge boost you get by not having to re-do most of the work you did when searching to shallower depths. Move ordering really improves with a move stored in the hash table too.

I agree with all advice that says get qsearch working before anything else - and, personally, you can ignore ordering of captures for now. Just having qsearch so you won't hang your Queen is such a big boost.

Andy.

[Sven]

I have difficulties to see why this explanation makes quiescence search easier to understand. Why do you introduce the "null" move here and mix it with the qsearch? Is it a way of expressing the "stand pat" principle?

Yes. This is a trivial concept to you and I, but not to him. Once the light bulb goes off he will understand it and it will seem trivial to him too.

He only needs to understand that you can stand pat and stop, but that standing pat is optional.

When I first implemented this as a kid, I missed the point that you must handle it like any other move. If it produces a beta cutoff handle it like you played a real move that produced a beta cutoff. And like a real move you have the option of either playing it, or trying to find something better.

Just to make sure I understand what you say: You want to start every qsearch by making the null move, then stop the search and call evaluate(), then undo the null move, and finally continue with searching all captures to possibly find an improvement over not moving in case the null move did not already cause a cutoff. Correct?

So why do you need a null move for this, which IMO complicates things a little bit? I think it is enough to just call evaluate() in the beginning.

I don't think you are putting yourself in his shoes. Your explanation is more technical and Fred already admitted he has trouble wrapping his head around computer chess concepts since he is so new at the game.

Anway, it totally amazes me how someone always rises to occasion -- the occasion to prove the saying that "no good deed goes unpunished."

My intention was to show that your explanation was not wrong but also not simple enough for a beginner, since you introduced unnecessary complexity by referring to "null move" which is not needed to understand qsearch. Also I think that a beginner probably can't understand your abstract explanation if he does not understand a more basic and concrete explanation like the one I have given.

Nothing personal was intended from my side, so we can leave this out here.

Sven

[Fguy64]

I've played a little bit with hash tables, I guess, though it was just brute force transposition checking, and there didn't seem to be much if any payoff in terms of time. My impression is that it is something you can ease your way into slowly, but I can't really speak with authority on that point.

From one of your other posts you don't have iterative deepening. Without that you won't see the huge boost you get by not having to re-do most of the work you did when searching to shallower depths. Move ordering really improves with a move stored in the hash table too.

I agree with all advice that says get qsearch working before anything else - and, personally, you can ignore ordering of captures for now. Just having qsearch so you won't hang your Queen is such a big boost.

Andy.

Well, I don't think I have it, but once or twice I have discovered that I had implemented something well known without realizing it. I understand the basic concept, but perhaps you can tell if it's there by a quick perusal of my engine code. I believe my search is an example of depth-first sarching, if that tells you anything about iterative deepening.

[Dann Corbit]

I think as much as anything it's terminology. Initial readings on quiescence went over my head because even individual words were loaded with meaning that required lots of thought.

Anyways, that probably illustrates that I was getting ahead of myself. When I started this thread, I thought I'd be able to leave q on the shelf for a little while. But no, so now I'm gonna take a couple of steps back, refocus and reinforce on the basics, before I take another run at quiescence. So I expect It'll be few weeks before I return to this thread to look at the q stuff in detail.

The simplest quiescent search is this:
Just make beneficial captures until there are not any left.