More abstract strategy game ideas
Apr. 4th, 2013 06:56 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
davvSo I coded up a very quick and dirty implementation of most of the games I suggested, and I found out that they don't really work.
Well, the ones that constrain the players to only put pieces down next to the last piece they put down do, but they're too much like Tron. I guess the reason that game works is because it is, in essence "competitive, obstructing longest path", and longest path is NP-hard.
So with all that determined, I started thinking about other concepts, and I found one. See if it sounds interesting :) I don't think it reduces to a competitive version of anything that's NP-hard, but here we go.
This is a two-player turn based game. Let's call it "Paths" for lack of anything better for now, and the players white and black. White goes first.
The game is played on a square nxn board. This board starts empty except for a few preset source points. (I'll leave it ambiguous where these source points are, since that's a parameter that can be tweaked.) The players then take turns placing stones of their own color on unoccupied squares of the board, and the game ends when both players pass.
The players then calculate score. First, the white player counts the length (in number of stones) of a contiguous path of black stones from one source to another. This is black's score. Then black counts the length of a contiguous path of white stones from one source to another. This is white's score.
If there is no such contiguous path, the player in question gets a score of zero. Contiguous is defined as an unbroken chain of stones from the starting point to the destination point, where stones next to each other along the cardinal directions, but not the diagonals, count as part of an unbroken path.
Highest score wins. If both players get the same score, it's a tie.
The strategy here involves first balancing obstructing moves that block the opponent's path and constructive moves that furthers one's own path, and second, knowing when moves will help and when they'll have no effect. Since the opposing player gets to pick the path the scoring goes along, he'll pick the shortest path (so as to minimize the score of his opponent), so adding branches won't really help. This also means that additional moves can hurt you, if you're forced to put a stone next to a source and thus make a much shorter path between two sources than was the case before.
Other possible variants:
- Lowest score wins, having no connected paths evaluates to a "score" of infinity, and otherwise as above. ("shortest longest path").
- Lowest score wins, having no paths is still bad (see above), and white counts white's path, black counts black's path ("shortest shortest path").
- Highest score wins and white counts white's path, black counts black's ("longest longest path").
- The game is over not when both players pass, but when they agree to end it (like agreeing to a draw in chess: no risk in passing and not knowing if the other player is going to pass too).
- Hex board instead of square. (Or some other exotic board)
Does this seem like a game that could work?
I imagine the four different counting rules would result in quite different game strategy. For instance, with standard rules ("longest shortest path"), obstructions slow the other player down but can add to the length of his path, whereas with shortest longest path, obstructions are much more effective.
If there's anything I can see that would be a problem, it's that the action is confined to a small part of the board. Once you have your path, stones outside of that path don't matter much and may even make your life worse. In that respect, it's a bit like Hex. I also don't know if there's some kind of unbeatable strategy. I also wonder how one would make an AI for the game - what kind of evaluation function would work?
Well, the ones that constrain the players to only put pieces down next to the last piece they put down do, but they're too much like Tron. I guess the reason that game works is because it is, in essence "competitive, obstructing longest path", and longest path is NP-hard.
So with all that determined, I started thinking about other concepts, and I found one. See if it sounds interesting :) I don't think it reduces to a competitive version of anything that's NP-hard, but here we go.
This is a two-player turn based game. Let's call it "Paths" for lack of anything better for now, and the players white and black. White goes first.
The game is played on a square nxn board. This board starts empty except for a few preset source points. (I'll leave it ambiguous where these source points are, since that's a parameter that can be tweaked.) The players then take turns placing stones of their own color on unoccupied squares of the board, and the game ends when both players pass.
The players then calculate score. First, the white player counts the length (in number of stones) of a contiguous path of black stones from one source to another. This is black's score. Then black counts the length of a contiguous path of white stones from one source to another. This is white's score.
If there is no such contiguous path, the player in question gets a score of zero. Contiguous is defined as an unbroken chain of stones from the starting point to the destination point, where stones next to each other along the cardinal directions, but not the diagonals, count as part of an unbroken path.
Highest score wins. If both players get the same score, it's a tie.
The strategy here involves first balancing obstructing moves that block the opponent's path and constructive moves that furthers one's own path, and second, knowing when moves will help and when they'll have no effect. Since the opposing player gets to pick the path the scoring goes along, he'll pick the shortest path (so as to minimize the score of his opponent), so adding branches won't really help. This also means that additional moves can hurt you, if you're forced to put a stone next to a source and thus make a much shorter path between two sources than was the case before.
Other possible variants:
- Lowest score wins, having no connected paths evaluates to a "score" of infinity, and otherwise as above. ("shortest longest path").
- Lowest score wins, having no paths is still bad (see above), and white counts white's path, black counts black's path ("shortest shortest path").
- Highest score wins and white counts white's path, black counts black's ("longest longest path").
- The game is over not when both players pass, but when they agree to end it (like agreeing to a draw in chess: no risk in passing and not knowing if the other player is going to pass too).
- Hex board instead of square. (Or some other exotic board)
Does this seem like a game that could work?
I imagine the four different counting rules would result in quite different game strategy. For instance, with standard rules ("longest shortest path"), obstructions slow the other player down but can add to the length of his path, whereas with shortest longest path, obstructions are much more effective.
If there's anything I can see that would be a problem, it's that the action is confined to a small part of the board. Once you have your path, stones outside of that path don't matter much and may even make your life worse. In that respect, it's a bit like Hex. I also don't know if there's some kind of unbeatable strategy. I also wonder how one would make an AI for the game - what kind of evaluation function would work?