Byte is AI-ready. If you have an algorithm for evaluating a given board position, go ahead and post your ideas.
Having the bottom checker of as many stacks as you can is important. At some point if you have the bottom checker on all of the stacks, and none of the stacks are adjacent, then only you can move the stacks. At that point, you move the stacks together in such a way that you win. Not the ultimate strategy, but something to keep in mind. - Mark
I don't believe this last observation is correct. Even having all bottom checkers and non-adjacent stacks does not guarantee a win. Consider two stacks one RBB and the other R???? (colors listed bottom up). Red is forced to move the stacks towards each other. Blue must wait. As soon as the stacks are adjacent Blue moves the top checker from the short stack to the tall stack. Now red is forced to commit suicide. - Paul
Although I've only played one game of Byte, and that was against the incredibly simple AI, I think I have some ideas as to how you could evaluate board position. As Mark points out, controlling the bottoms of stacks is important, since then you can choose when and where to move them, although as Paul points out that's not the whole story. Less important, but still a factor in deciding board position, is how many stacks you control the top piece in; if you control the top piece in a stack, merging from that stack to another is going to get you closer to capturing that stack, although of course this isn't certain either. Having two stacks with your piece on top next to each other is great, because then the other player will be forced to merge them at some point, raising one of your pieces higher. And as I've seen in several of the discussions between Jesse and Mark while playing games, “slack” is very important (this game wouldn't be the work of a certain JR “Bob” Dobbs, now, would it?). Slack means the amount of time you can spend avoiding forced moves. This may be a little tricky to calculate, since if you control two stacks that are close to each other, you could move one towards the other, merge them, and then you'd have to calculate the distance from that merged stack to the nearest other stack. You could do a bad estimate by just adding up the total distances from each stack you control to the nearest other stack. Anyhow, I think if you implemented something that calculated these parameters, and weighted them somehow, maybe by playing the AI against itself lots of times with some kind of genetic algorithm, simulated annealing, or simple hill-climbing to set the weights, you would be able to get a pretty decent AI. (lambda)
Oh, by the way, Paul, I don't think in your example red necessarily has to commit suicide. I'm assuming that by R???? you meant a stack with a red at the bottom, where it doesn't matter what the other pieces are. If it's RR???, though, then when blue merges the state will be RB and RR???B. Red can then merge to form RBR??? and R. Now blue can't merge, and R can merge to a capture. (lambda)
This is correct, lambda. Having the two bottom checkers in a stack is far less common than the two top checkers in a stack, though. Nevertheless, in my experience, it is almost always possible to manipulate the stacks in such a way as to ensure a win, if you own all the bottom checkers. (Jesse)
Now for some actual AI news: I (Jesse) have implemented an AI that is still fairly simple, but plays pretty well. ByteMonster does an alpha-beta search with iterative search deepening, with an evaluation function that depends only on the score, and for each stack, who owns the bottom checker and how many adjacent stacks there are. The rules are:
These are just the first values I decided to try, and have not been tuned at all. They are based on the observations that it is amost always possible to win if you control all the bottom checkers, having slack moves to make tends to help achieve this situation, and it is often advantageous to sacrifice the first point in order to gain that slack (what I like to call a “slackrifice”). The increased value for having one neighbor is based on the idea that that stack cannot move without giving you slack. Despite the slow implementation (in Mathematica, of all things), which is typically only able to look ahead two or three moves in the opening, and five or six moves in the middle game, and despite its inability to so much as count the number of moves that can be safely made in each region or decide how to resove local situations based on which stacks it wants to bring together in the endgame, its performance has been good. It has now played two games against humans, SDG's top ranked Byte players (MarkSteere and Jesse), and won both games. Even simple refinements (such as points for owning the top checker of a stack, as lambda suggests) should make it even stronger.
Any given opening works but one should keep in mind that giving your opponent a move advantage is generally risky. A move advantage would include letting an opponents piece become “unconnected” to the other pieces or allowing for a mid-stack move with out a mid-stack response for one's next turn.
At this juncture there seems to be a kind of symmetry that is developed while following the basic opening strategy.
At this point in the game it is a matter of counting the pieces on a stack and weighing the possible move responses to every kind of move one can make.
If you're interested in an analysis of Byte endgames, general strategies and a discussion about the first-move advantage of Byte, go to http://games.groups.yahoo.com/group/true-stacking-games/
This might also be very helpful if you try to write a Byte program.
The most important posts on Byte are archived and are the following ones:
message/8 message/6 message/4
The discussion still continues. - Ralph
The discussion there is interesting, but I think it's of limited value. For instance, one article suggests that symmetrical play leads to a 75% chance of a first-player win (which only follows if the distribution of the possible end positions is uniform), and that this suggests a possible first-player advantage. I think, rather, it suggests that the second player should not play symmetrically throughout the game. In the course of a typical game (in my experience), both players maneuver to preserve their own options while limiting those of the other player, until one player is forced to make an unfavorable move that the other can capitalize on. As long as play is symmetric, the first player should be the first to have to make an unfavorable move. At this point, the second player should break symmetry and take advantage of the first player's move, since the symmetric play is unfavorable. In self-play trials by my AI (of which one should always be skeptical), the second player wins about 75% of games. I haven't had the opportunity to analyze the games beyond that simple observation, and the results may depend on the amount of thinking time the AI gets per move. (Jesse)
And what about the final two-stack endgame which has been completely solved? http://www.boardgamegeek.com/thread/89603