move ordering problem

[ericlangedijk]

Hello fellow programmers,

I am implementing a search algorithm for Scrabble, using the same techniques as chess.
Some are not really applicable because the search tree can be gigantic.
But I use: iterative deepening, transposition table and alphabeta.

The following question is about an "absolute" endgame, which is: the 2 players have a rack with letters and the bag with letters is empty, so we have absolute knowledge of the complete gamestate, like in chess.

I am running into a move ordering problem, let me explain:
The eval function is (currently) simply the score-difference between the two players, however if we have a leaf node we know: WIN, LOSS or DRAW.

When examining the root moves, I use some extra heuristics about each move to find out if it is interesting. These will be examined first.
After my first iteration however I get evaluations back and re-sort my rootmoves according to the eval.
Which means: I lose my valuable "root-heuristic" evaluation. An interesting move which was in front can end up in the back.

Probably people encountered this problem as well...
And does anyone have some solution for it?

Best wishes,
Eric

[hgm]

In chess one usually doesn't have any evaluations in the root that you could re-sort on. Often none at all, because the best move of the previous iteration usually remains best in the next iteration. Where it was searched first. All other moves then fail low compared to the score of that move, and you have no idea what their evaluation was or how to sort them. (Except that they should not be in first place.)

If an 'interesting' move turns out bad after searching, why would you want to keep considering it interesting?

Scrabble is different from Chess in the way that your evaluation improves on every move, while in Chess it only does when you capture, and most moves are not captures. So every game state in Scrabble is similar to tactics in progress. It seems to me that when you are evaluating non-quiet positions your evaluation has to take (large) account of the side to move.

It should also be important to incorporate the letters in hand in the evaluation, and not just take the board score. If you can get many points by placing all your easy-to-place letters, but that leaves you with only difficult-to-place letters, it might be better to play a combination with a lower score to have a more-easily usable mix of letters left in hand.

[Lunar]

I think it's fairly canonical to order moves in the root with the previous best first, and then the rest of the moves ordered by the size of the subtree it took to refute them: https://www.chessprogramming.org/Move_O ... iderations

I also use this same principle in my own chess engine.

[ericlangedijk]

Thanks! That makes much sense. Makes it easier also.
Indeed I need to include a rack evaluation, which will make the eval more logical and better and no need for wild guessing at the root.

Probably I am going to precompute rack evals for all 1-6 letters racks - which will burn my low-math brain but anyway...