![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
More abstract strategy game ideas
Apr. 4th, 2013 06:56 pmSo 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.
( Read more... )
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.
( Read more... )