move ordering

[adams161]

Pulsar seems to be playing well at crazyhouse with the new mate detection code. I did in the end get rid of the beta-- line that was suggested as i think optional. I've extended measuring distanct to mate to all chessic variations it plays as well as regular chess and atomic. Its tricky maintaining a program that has 3 search functions and 5 evaluate functions that it goes through depending on the variant but i prefer the seperation so i can fiddle with one part or variant and not effect others.

Next step is working on move ordering. There hasnt been much work on search in recent years, prior to this year i only worked on the atomic code actually which his a different search function than regular chess or crazyhouse, and i'm seeing a lot of stuff that makes me wonder in my code.

Listening to hyatt there seems to be a different way to think about move ordering than i have always followed. In the past i thought you wanted to order the best moves first. But i think i saw bob post that is not neccesarily so, you want to order the moves that cause cuttoffs first.

My own testing may find the answers but i'm just looking for some guidlines. when you hash and teh depth test is not met you can play teh hash move. Should that only be played if the hash move forced a beta cuttoff? what if it just changed alpha? Should this move be played first? does the answer to if it should be played first depend on if it changed alpha or if it instead forced a beta cuttoff?

My other move ordering schemes are killer moves and order by captures. Apparently i'm trying to play winning captures first but i think i might test playing basic most valuable piece least valuable defender.

With killer moves any benefit to playing moves that changed alpha or just moves that changed beta? Should captures be included in killer moves? What priority should killer moves be given over captures and hash move? does it depend on if it changed alpha or also caused a beta cuttoff.

A lot of questions, in the past i've tried a lot of different stuff and never really settled on anything. Not sure i trust what i have there now for move ordering so i'm going to tinker.

Yours
Mike

[bob]

Pulsar seems to be playing well at crazyhouse with the new mate detection code. I did in the end get rid of the beta-- line that was suggested as i think optional. I've extended measuring distanct to mate to all chessic variations it plays as well as regular chess and atomic. Its tricky maintaining a program that has 3 search functions and 5 evaluate functions that it goes through depending on the variant but i prefer the seperation so i can fiddle with one part or variant and not effect others.

Next step is working on move ordering. There hasnt been much work on search in recent years, prior to this year i only worked on the atomic code actually which his a different search function than regular chess or crazyhouse, and i'm seeing a lot of stuff that makes me wonder in my code.

Listening to hyatt there seems to be a different way to think about move ordering than i have always followed. In the past i thought you wanted to order the best moves first. But i think i saw bob post that is not neccesarily so, you want to order the moves that cause cuttoffs first.

My own testing may find the answers but i'm just looking for some guidlines. when you hash and teh depth test is not met you can play teh hash move. Should that only be played if the hash move forced a beta cuttoff? what if it just changed alpha? Should this move be played first? does the answer to if it should be played first depend on if it changed alpha or if it instead forced a beta cuttoff?

There are only two circumstances where you have a "best move" in the hash (in a valid implementation). Either the move produced a beta cutoff on the search where it was stored, or the move was the best move in a search that produced an "exact score". If a search fails low at a node, there is no best move to store, although the hash entry should be stored reflecting that result, but the "best move" should be set to <null>...

A move can't just "change alpha" and be stored. It has to be one of the two previous cases...

BtW, my exact statement was "search the move that produces a beta cutoff with the _least_ effort required... One beta cutoff is as good as another, from a result point of view as either refutes the move at the previous ply. So try the move that will require the least effort to search (avoid a check, for example, if another move will produce a cutoff, since the search gets extended on a check. But even that rule is not absolute as it might lead to a quick mate that is even easier to search...

My other move ordering schemes are killer moves and order by captures. Apparently i'm trying to play winning captures first but i think i might test playing basic most valuable piece least valuable defender.

With killer moves any benefit to playing moves that changed alpha or just moves that changed beta? Should captures be included in killer moves? What priority should killer moves be given over captures and hash move? does it depend on if it changed alpha or also caused a beta cuttoff.

Again, I don't understand the idea. A move either fails low (no good), fails high (good move) or is the best move at a ply (good move). I don't get the "raised alpha" case since most don't update killers or hash until a ply is completely searched...

A lot of questions, in the past i've tried a lot of different stuff and never really settled on anything. Not sure i trust what i have there now for move ordering so i'm going to tinker.

Yours
Mike

[adams161]

i dont know how to do the fancy quote stuff so i'll just quote you as i remember you:

"i dont understnad the point since most dont change hash or killer moves tell a ply is searched completley"


while i do do that with hash i have to admit and now wonder if there is a consequnce, that i dont do that with killer moves. i have been updating killer moves whenever value>alpha at a ply.


i hash at the end of a search node, when all moves have been searched. to be honest i think there may be a bug were it is tryinf to find a hash move to play when its not an exact score ( what i refer to as changing alpha) or a beta cuttoff. I would think that there is no from and to assigned so it would never find such a move and have to then order bvvy the next move ordering technique, captures, but i'm going to have to check.

I'm taking it your suggesting i should not change a killer move tell i have searched all moves or have a beta cuttoff.

By changing alpha i'm not sure if i'm mistaken in what i'm doing or there is a misunderstanding. Lets assume for clarity i'm allowing that a move changes alpha only after all moves are searched. After all moves are searched the best move may be better than the alpha that was passed into the search node but not better or equal to beta or we would refer to that as a move that caused a beta cuttoff.

the question is, assuming i waited tell all moves are searched or a move triggered a beta cuttoff, is it worthwile to store a move that is value>alpha and consequently we return alpha=value, or should i only concern myself with killer moves that are value>beta.

Mike

[bob]

i dont know how to do the fancy quote stuff so i'll just quote you as i remember you:

"i dont understnad the point since most dont change hash or killer moves tell a ply is searched completley"


while i do do that with hash i have to admit and now wonder if there is a consequnce, that i dont do that with killer moves. i have been updating killer moves whenever value>alpha at a ply.

That is probably a bad idea. You are likely overwriting good killers way too often and losing them as a result. You should only update them when you finish a ply, not in the middle. Just like you say you are doing with hash.

i hash at the end of a search node, when all moves have been searched. to be honest i think there may be a bug were it is tryinf to find a hash move to play when its not an exact score ( what i refer to as changing alpha) or a beta cuttoff. I would think that there is no from and to assigned so it would never find such a move and have to then order bvvy the next move ordering technique, captures, but i'm going to have to check.

I'm taking it your suggesting i should not change a killer move tell i have searched all moves or have a beta cuttoff.

correct.

By changing alpha i'm not sure if i'm mistaken in what i'm doing or there is a misunderstanding. Lets assume for clarity i'm allowing that a move changes alpha only after all moves are searched. After all moves are searched the best move may be better than the alpha that was passed into the search node but not better or equal to beta or we would refer to that as a move that caused a beta cuttoff.

That would be a "PV" node, because the search window is not null (x,x+1) and the value of alpha was raised. Whenever you get a score >= beta, you immediately stop searching, and that is called a "CUT" node where the score for some move is >= beta...

the question is, assuming i waited tell all moves are searched or a move triggered a beta cuttoff, is it worthwile to store a move that is value>alpha and consequently we return alpha=value, or should i only concern myself with killer moves that are value>beta.

A "killer move" is defined is a move that improves move ordering at a ply. That is, any move that causes an immediate beta cutoff, or the best move, doesn't matter which. We'd like to have the best move at fail-low nodes because sometimes they become fail-high nodes as well and we would prefer to search the best move there. But there's no way (in the alpha/beta framework) to discover the best move at such nodes so we just store the search result with a <null> best move so that we don't try something ugly first, later on...

So killers should be simply the best move at any ply. For beta cutoff nodes, a killer is the move that caused the cutoff. For alpha cutoff nodes, a killer doesn't exist because all moves get searched without changing alpha or getting a result >= beta. For the rest, there is no killer move at all to deal with.

If you do what you suggest, you will have multiple killers stored from a single node, overwriting killers that should be remembered from other nodes. This will hurt move ordering, not help it.

Mike

[adams161]

Hi,

It seems like I am replacing killers much to often for the ordering to be terribly effective. I'm getting that only a move that triggers a beta cuttoff or a move that changes the score if all moves have been tried and no beta cuttoffs were found would be worth storing. But the second part i'm not sure i'm on the same page with yet.

<quote>
A "killer move" is defined is a move that improves move ordering at a ply. That is, any move that causes an immediate beta cutoff, or the best move, doesn't matter which. We'd like to have the best move at fail-low nodes because sometimes they become fail-high nodes as well and we would prefer to search the best move there. But there's no way (in the alpha/beta framework) to discover the best move at such nodes so we just store the search result with a <null> best move so that we don't try something ugly first, later on...
</quote>


or best move sounds like if a move is value>alpha, and maintains this position after all moves are searched you have a best move though not a cuttoff move.

<quote>
So killers should be simply the best move at any ply. For beta cutoff nodes, a killer is the move that caused the cutoff. For alpha cutoff nodes, a killer doesn't exist because all moves get searched without changing alpha or getting a result >= beta. For the rest, there is no killer move at all to deal with.
</quote>

I understand the concept that if no move is value > alpha , fail low, there could be a best move but we will never know it as i'm aware that alpha beta searching never allows for scoring of anything but best move. i.e. why we cant know our second best move for example when search is done. In the above quote the first two cases are clear. beta cuttofs we know the move that triggered it. alpha cuttoffs as you refer to a move that doesnt rise above alpha and change alpha we dont have a killer because there is just no indication that any move is better than any other move from our scoring method.

what i'm unclear on is <quote> For the rest, there is no killer move at all to deal with. </quote>

Once you eliminate fail low and fail high all you are left with are moves that succesfully changed alpha after all moves were searched, value > alpha , and i'm guessing these might be worth saving but not sure. Just for clarity i dont search with any aspiration windows yet. And i should say thanks for setting me straight that i'm over writing good killers much to often. My return on killers when i first implemented showed they worked to lower my branching factor but i was always disappointed they didnt work better in the past.

Mike

[bob]

Hi,

It seems like I am replacing killers much to often for the ordering to be terribly effective. I'm getting that only a move that triggers a beta cuttoff or a move that changes the score if all moves have been tried and no beta cuttoffs were found would be worth storing. But the second part i'm not sure i'm on the same page with yet.

<quote>
A "killer move" is defined is a move that improves move ordering at a ply. That is, any move that causes an immediate beta cutoff, or the best move, doesn't matter which. We'd like to have the best move at fail-low nodes because sometimes they become fail-high nodes as well and we would prefer to search the best move there. But there's no way (in the alpha/beta framework) to discover the best move at such nodes so we just store the search result with a <null> best move so that we don't try something ugly first, later on...
</quote>


or best move sounds like if a move is value>alpha, and maintains this position after all moves are searched you have a best move though not a cuttoff move.

<quote>
So killers should be simply the best move at any ply. For beta cutoff nodes, a killer is the move that caused the cutoff. For alpha cutoff nodes, a killer doesn't exist because all moves get searched without changing alpha or getting a result >= beta. For the rest, there is no killer move at all to deal with.
</quote>

I understand the concept that if no move is value > alpha , fail low, there could be a best move but we will never know it as i'm aware that alpha beta searching never allows for scoring of anything but best move. i.e. why we cant know our second best move for example when search is done. In the above quote the first two cases are clear. beta cuttofs we know the move that triggered it. alpha cuttoffs as you refer to a move that doesnt rise above alpha and change alpha we dont have a killer because there is just no indication that any move is better than any other move from our scoring method.

what i'm unclear on is <quote> For the rest, there is no killer move at all to deal with. </quote>

Once you eliminate fail low and fail high all you are left with are moves that succesfully changed alpha after all moves were searched, value > alpha , and i'm guessing these might be worth saving but not sure. Just for clarity i dont search with any aspiration windows yet. And i should say thanks for setting me straight that i'm over writing good killers much to often. My return on killers when i first implemented showed they worked to lower my branching factor but i was always disappointed they didnt work better in the past.

Mike

Couple of things. First, your HTML tags for quote and /quote need to be enclosed in square brackets "[]" rather than angle brackets "<>". That will solve your quoting issues.

Second, just follow this simple rule: only update killers after a ply has been completed. If it is completed by a quick fail-high, the move causing the fail-high is the one you want to add to the killers. If it is completed by searching all moves and when you finish, value is greater than alpha, then remember the best move as a killer. Do not try to remember all the others. Why would you want the second-best move as a killer, or the third-best?:?? That is what you are doing when you think about it...

[PK]

In my program there seems to be one important exception to the rule proposed by Robrty Hyatt:

only update killers after a ply has been completed. If it is completed by a quick fail-high, the move causing the fail-high is the one you want to add to the killers. If it is completed by searching all moves and when you finish, value is greater than alpha, then remember the best move as a killer.

Namely, using killer moves from nodes with no beta cutoff gave me a nice 20% speedup (and many thanks for pointing it to us illiterates) but only under the condition that it isn't done directly after a null move