![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
A possibly less expensive AI for unorthodox chess!
(Oops, it seems that my reduction might not be so safe after all. I'll say why in the main text, but oh well!)
-
In my previous post, I mentioned a way of solving semi-realtime games by the use of minimax, by just splitting the timeline into a series of "virtual turns", one for each instant of the clock, where each player may pass or do something. I then said that this would be horribly expensive because each minimum time instant would be a move and the game tree would get really deep really fast.
Here's an idea regarding how one may solve it. It may hold in unorthodox chess, and if it does, in realtime games in general.
Say you have a timeline like this:
[-----|--------|-------|---] --> to the future
......A........B.......C...
At time A, one of white's knights goes out of penalty and now white can move. At C, one of black's rooks goes out of penalty and black can move. Say the AI's reasoning engine is at point B, so it's trying to find out whether to move or not.
Then we should ask ourselves: why should white even consider time B? If white is considering moving his knight, why didn't he do it at time A? The only difference between A and B is that time has passed: remember, black can't move yet. So, one should reason, the only difference between moving at A and moving at B is that white has to wait a longer time before the knight is available again.
Thus, it seems that there's no reason for white not to move the knight at point A (or wait until C, if he wants to respond to C's threat at the expense of having to wait longer for the knight to become available afterwards). So the only points the AI has to consider is when something happens, or immediately after.
In other words, if black can't move at A, the AI only has to consider white at A. So the AI considers white at A. If white doesn't move, it needs to consider both white and black at C - since there may be a simultaneous move where white doesn't want to give his intelligence away - but if white does move, it needs only to consider black at C.
That a significant cut from having to think about every time instant. The logic becomes: "a difference that makes no difference is no difference at all". Each player only needs to consider moving at a point at or just after something did change.
However, it might not be so simple. Thinking about it in retrospect, I can see two possibilities where waiting might be beneficial. Let's handle the first... err, first. Say white has a rook and a knight available. White might want to move the rook first, then wait one TU, then move the knight, so that both are available at the same time the next time around. This is parallel to the idea of time on target, where you fire different artillery pieces with delay between each so that the shells all reach the target at the same time.
(However, again, I have a counter-counter to this. Say that white has both rook and knight available from having executed that strategy. Then say he moves the knight. Now, since we're assuming lightning-fast computers, black might move after the knight move but before white gets to move his metaphorical hand to get to the rook. Thus, time-on-target is illusory. I don't know if the argument holds, though.)
The second possibility is to play games with the opponent's thinking time. If white has an elaborate plan, he might stagger his moves so that many pieces are available in the future at the same time, and then once all the pieces are ready, execute his plan before black has a chance to react to his moves. It's still a time-on-target, but it's a mental one: white gets to pull off a number of moves before black can respond, because black is busy thinking about how to respond.
So there you are. Perhaps the less expensive AI is possible. Perhaps it wouldn't be smart enough. I don't know... I can argue both in favor and against.
But the revealing insight, really, was the idea that real-time games could be coerced to be turn-based by adding lots of virtual turns. In a real game, this might even produce desirable side effects: if each virtual turn is, say, one second, that means no player can go faster than 60 APM. No more silly AIs that only win because they're inhuman at micromanagement.
(The stock Starcraft II AI can reach 2000 APM. The human record is somewhere around 500 for longer times, 800 for instants. At least in my opinion, an AI is much more interesting if it can play better than humans while otherwise sharing the handicaps - reaction time, etc., of humans.)
And after writing all of the above, I found that my minimax-generalization idea had already occurred to others. If you want a rigorous paper, go there. It investigates the consequences of the AI having to actually think while time passes, too.
Finally, again, I really do wonder what unorthodox chess would play like. I could see lots of time strategies: the mental time-on-target I mentioned above, the tension between waiting (so as not to reveal intelligence) and moving (so as not to lose on time)...
-
In my previous post, I mentioned a way of solving semi-realtime games by the use of minimax, by just splitting the timeline into a series of "virtual turns", one for each instant of the clock, where each player may pass or do something. I then said that this would be horribly expensive because each minimum time instant would be a move and the game tree would get really deep really fast.
Here's an idea regarding how one may solve it. It may hold in unorthodox chess, and if it does, in realtime games in general.
Say you have a timeline like this:
[-----|--------|-------|---] --> to the future
......A........B.......C...
At time A, one of white's knights goes out of penalty and now white can move. At C, one of black's rooks goes out of penalty and black can move. Say the AI's reasoning engine is at point B, so it's trying to find out whether to move or not.
Then we should ask ourselves: why should white even consider time B? If white is considering moving his knight, why didn't he do it at time A? The only difference between A and B is that time has passed: remember, black can't move yet. So, one should reason, the only difference between moving at A and moving at B is that white has to wait a longer time before the knight is available again.
Thus, it seems that there's no reason for white not to move the knight at point A (or wait until C, if he wants to respond to C's threat at the expense of having to wait longer for the knight to become available afterwards). So the only points the AI has to consider is when something happens, or immediately after.
In other words, if black can't move at A, the AI only has to consider white at A. So the AI considers white at A. If white doesn't move, it needs to consider both white and black at C - since there may be a simultaneous move where white doesn't want to give his intelligence away - but if white does move, it needs only to consider black at C.
That a significant cut from having to think about every time instant. The logic becomes: "a difference that makes no difference is no difference at all". Each player only needs to consider moving at a point at or just after something did change.
However, it might not be so simple. Thinking about it in retrospect, I can see two possibilities where waiting might be beneficial. Let's handle the first... err, first. Say white has a rook and a knight available. White might want to move the rook first, then wait one TU, then move the knight, so that both are available at the same time the next time around. This is parallel to the idea of time on target, where you fire different artillery pieces with delay between each so that the shells all reach the target at the same time.
(However, again, I have a counter-counter to this. Say that white has both rook and knight available from having executed that strategy. Then say he moves the knight. Now, since we're assuming lightning-fast computers, black might move after the knight move but before white gets to move his metaphorical hand to get to the rook. Thus, time-on-target is illusory. I don't know if the argument holds, though.)
The second possibility is to play games with the opponent's thinking time. If white has an elaborate plan, he might stagger his moves so that many pieces are available in the future at the same time, and then once all the pieces are ready, execute his plan before black has a chance to react to his moves. It's still a time-on-target, but it's a mental one: white gets to pull off a number of moves before black can respond, because black is busy thinking about how to respond.
So there you are. Perhaps the less expensive AI is possible. Perhaps it wouldn't be smart enough. I don't know... I can argue both in favor and against.
But the revealing insight, really, was the idea that real-time games could be coerced to be turn-based by adding lots of virtual turns. In a real game, this might even produce desirable side effects: if each virtual turn is, say, one second, that means no player can go faster than 60 APM. No more silly AIs that only win because they're inhuman at micromanagement.
(The stock Starcraft II AI can reach 2000 APM. The human record is somewhere around 500 for longer times, 800 for instants. At least in my opinion, an AI is much more interesting if it can play better than humans while otherwise sharing the handicaps - reaction time, etc., of humans.)
And after writing all of the above, I found that my minimax-generalization idea had already occurred to others. If you want a rigorous paper, go there. It investigates the consequences of the AI having to actually think while time passes, too.
Finally, again, I really do wonder what unorthodox chess would play like. I could see lots of time strategies: the mental time-on-target I mentioned above, the tension between waiting (so as not to reveal intelligence) and moving (so as not to lose on time)...