I alluded yesterday to a problem with the way my AI ranked moves. In fact, it’s a problem with the way the whole game is scored. See, I took the rule where each side finishes parking its pieces “as if the opponent’s pieces were non-existent” and got it into my head as “as if the other pieces were non-existent.” This is one of those easier-said-than-done kind of distinctions! The latter is simply the total shortest-path distance of each piece from its destination. Easy-peasy. The real rule takes planning, which means more AI work.
Consider the board position that was causing all that trouble yesterday. The five of moons is three moves from its goal; the five of suns, seven. But not only is the four of stars in the way of both of them, it can’t get out of the way of both of them at the same time. Either it needs to shuffle around twice, or move farther out of the way, or one of the other pieces needs to divert around it. All of these add up to the same number of moves, meaning the correct penalty in this position is not seven but eleven.
Shortest-path distance is still a perfectly good way for the AI to do most of its planning. It’s a good, quick estimate, and when pieces get close it can often fall back to pathfinding with Djikstra’s algorithm anyway (which is one of the simpler versions of the sort of thing that Google Maps does for you, for example). But to actually figure out the final score, not only does the math have to change, so does the whole flow of control of the game. We now need to have a phase where the human player has a chance to bring their pieces home, and the AI has to do likewise. Moreover, we need to change some of our notions about what is a legal move (probably by simply removing the other player’s pieces, and restoring them later), and the final pathing AI has to be rock solid, because errors here will stick out like a sore thumb.
Now you know why I spent the time that I did figuring out what was up with that one of stars move yesterday, especially before I went and changed a whole bunch of other stuff.