![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
A particularly expensive AI for unorthodox chess
I don't know if anyone's reading this, but I found this nifty enough that I'll write about it anyway. Or perhaps not this as much as what it's building up towards.
Looking at the "unorthodox chess" variant I defined earlier, one can see that it's not fully real-time. Although there are no fixed turns, no single master clock, the time penalties of the pieces are still connected to the concept of a time unit, and nothing can happen faster than 1/20 TUs.
That suggests a very expensive extension of minimax. Each player gets a 1/20 TU slice. He may do anything not otherwise prohibited. If all his pieces are under time penalty, he can do nothing and so has to pass, and in any event he always has the option of passing. When he passes, the turn goes to the other player. In effect, you get a bunch of "virtual turns" that are 1/20 TUs long.
Obviously, this is completely impractical for anything like actual chess. There's 40 ply just to get a single TU to pass. But there's also a more subtle difficulty: the players can move at the same time. The tiebreak rule keeps black from gaining any direct advantage by moving simultaneously with white when he could have moved earlier (all other things equal), but there's still the incentive of hiding one's own move.
To be more precise: if black moves at the very moment white does, white has lost some intelligence because he couldn't react to black's move beforehand. Similarly, if white moves at the very moment black does, black has lost some information he could otherwise have used to react to black's move.
The same thing exists in turn-based games where the players move simultaneously. As far as I understand, the "proper" way of solving these problems is to consider the moves and countermoves in a game-theory payoff matrix, i.e. one that says "for all moves I make, if he makes these moves at the same time, how much worse off am I and he afterwards?". Such a matrix can be churned through a solver to find the optimal strategies for white and black. As for the actual payoff values, those would have to be acquired from applying the same reasoning to the future... same as an ordinary chess AI does.
Needless to say, this makes pruning pretty tricky. Playing simultaneous-move chess (chess, but where the two players move simultaneously) well is harder than playing ordinary chess well, at least to a computer. Playing "unorthodox chess" is harder still than simultaneous-move chess. And then there's the matter of the extreme combinatorial blowup to deal with... "one does not simply search 40 ply deep" :)
Looking at the "unorthodox chess" variant I defined earlier, one can see that it's not fully real-time. Although there are no fixed turns, no single master clock, the time penalties of the pieces are still connected to the concept of a time unit, and nothing can happen faster than 1/20 TUs.
That suggests a very expensive extension of minimax. Each player gets a 1/20 TU slice. He may do anything not otherwise prohibited. If all his pieces are under time penalty, he can do nothing and so has to pass, and in any event he always has the option of passing. When he passes, the turn goes to the other player. In effect, you get a bunch of "virtual turns" that are 1/20 TUs long.
Obviously, this is completely impractical for anything like actual chess. There's 40 ply just to get a single TU to pass. But there's also a more subtle difficulty: the players can move at the same time. The tiebreak rule keeps black from gaining any direct advantage by moving simultaneously with white when he could have moved earlier (all other things equal), but there's still the incentive of hiding one's own move.
To be more precise: if black moves at the very moment white does, white has lost some intelligence because he couldn't react to black's move beforehand. Similarly, if white moves at the very moment black does, black has lost some information he could otherwise have used to react to black's move.
The same thing exists in turn-based games where the players move simultaneously. As far as I understand, the "proper" way of solving these problems is to consider the moves and countermoves in a game-theory payoff matrix, i.e. one that says "for all moves I make, if he makes these moves at the same time, how much worse off am I and he afterwards?". Such a matrix can be churned through a solver to find the optimal strategies for white and black. As for the actual payoff values, those would have to be acquired from applying the same reasoning to the future... same as an ordinary chess AI does.
Needless to say, this makes pruning pretty tricky. Playing simultaneous-move chess (chess, but where the two players move simultaneously) well is harder than playing ordinary chess well, at least to a computer. Playing "unorthodox chess" is harder still than simultaneous-move chess. And then there's the matter of the extreme combinatorial blowup to deal with... "one does not simply search 40 ply deep" :)