Not sure if this belongs at a Zig forum. I asked the question at a chess forum as well
But anyway… Maybe some crazy creature vistiing this forum is interested in my next problem.
I am implementing a search algorithm for Scrabble, using the same techniques as in chess.
Some are not really applicable because the search tree can be gigantic very soon.
But I use:
- iterative deepening
- alphabeta (negamax) search
- transposition table
The 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.
The search i have now already can find some quite insane wins. I checked these from some youtube positions analysis of Mark Meller.
I am running into a move ordering problem (which is key for alphabeta), let me explain:
The eval function is (currently) simply the score-difference between the two players, however if we have a leaf node (end-of-game) 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 (maybe) valuable “root-heuristic” evaluation. An interesting move which was in front can end up in the back directly.
Does anyone know about this phenomena? Or have some ideas for stabalizing this ordering? Or just knows: this is the wrong way?