Maybe Math IS Useful?
December 10, 2019 8:04 AM Subscribe
Imagine you are making a game. The game board is made up of 56 square tiles randomly drawn and placed in an 7x8 grid by each player in turn. Each tile represents a room and the grid is a house, and each tile has at least one door up to a maximum of four doors, one on each side. Tiles can be placed anywhere on the grid - they don't have to be played adjacent to a tile already on the grid. The goal is to place tiles so they lead to a specific spot of the grid's outside edge Is there some accessible way to use math to figure out what combination of doored cards is best for minimizing dead ends, or is this ridiculous and if I knew even the barest shred of math I would know not to ask such foolishness?
Basically can math tell me that ten 4-doored cards, ten 3-doored cards, fifteen 2-doored cards with doors on opposing sides, and fifteen 2-doored cards with doors on intersecting edges, and six 1-doored cards (For example) would make the most navigable 7x8 grid? Or maybe this is old hat for gaming people and some lovely nerd somewhere has made a tool where you punch in your parameters and spits out an answer?
Basically can math tell me that ten 4-doored cards, ten 3-doored cards, fifteen 2-doored cards with doors on opposing sides, and fifteen 2-doored cards with doors on intersecting edges, and six 1-doored cards (For example) would make the most navigable 7x8 grid? Or maybe this is old hat for gaming people and some lovely nerd somewhere has made a tool where you punch in your parameters and spits out an answer?
To pass from one tile to another, do there need to be doors in both walls along that edge or just one?
posted by wanderingmind at 8:31 AM on December 10, 2019
posted by wanderingmind at 8:31 AM on December 10, 2019
It seems to me like you can place all of the 2-doored cars in a sequence to make a tunnel. That would be the tightest path. Place the other cards elsewhere on the board.
posted by cmcmcm at 8:33 AM on December 10, 2019 [2 favorites]
posted by cmcmcm at 8:33 AM on December 10, 2019 [2 favorites]
Trivially, having four doors on every tile avoids having any dead ends, and makes the most navigable grid, for some definition of navigable. But of course that doesn't make an interesting game.
I think you need to add more constraints, as well as make some clarifications. Does a door have to align with a door on an adjoining tile, or can you place a door against a wall, and if so, what does that mean? Can you place a door against the outside of the grid, and if so, what does that mean? What do you mean by "navigable?"
posted by DevilsAdvocate at 8:36 AM on December 10, 2019 [6 favorites]
I think you need to add more constraints, as well as make some clarifications. Does a door have to align with a door on an adjoining tile, or can you place a door against a wall, and if so, what does that mean? Can you place a door against the outside of the grid, and if so, what does that mean? What do you mean by "navigable?"
posted by DevilsAdvocate at 8:36 AM on December 10, 2019 [6 favorites]
Well, if you really want to minimize dead ends, then the optimal solution would be to make every card in the deck have four doors. But I think what you really want is a distribution that creates a challenging puzzle, one that can be solved if you make the right moves, but not necessarily otherwise.
On preview, DevilsAdvocate says most of what I wanted to say.
posted by J.K. Seazer at 8:37 AM on December 10, 2019 [2 favorites]
On preview, DevilsAdvocate says most of what I wanted to say.
posted by J.K. Seazer at 8:37 AM on December 10, 2019 [2 favorites]
As far as math goes, look up graph theory. Every room would be a node, and each door would be an edge to a different node. You can use a depth-first search to determine the "straightness" of a particular path.
posted by cmcmcm at 8:43 AM on December 10, 2019 [1 favorite]
posted by cmcmcm at 8:43 AM on December 10, 2019 [1 favorite]
Response by poster: To pass from one tile to another, do there need to be doors in both walls along that edge or just one?
Yeah there have to be doors on both edges, and doors are always centred on tiles edges so they match. Doorway would be a better way to put it, sorry.
Can you place a door against the outside of the grid, and if so, what does that mean? What do you mean by "navigable?"
The only exit (Game objective) of the grid house is the outside edge of the centre square of the top row. The game begins with the players' characters starting in separate rooms - each player draws and plays a room tile a minimum of 4 rows away from the 'exit' square, and in the first round cannot play a room tile adjacent to one occupied by another player (After that character tokens can share tiles and pass through 'rooms' played by other players). Each turn they draw and play a room tile and move their token to it working towards the exit. Deadends are inevitable and rules can state they should be avoided when possible, but I want them minimized while allowing for a variety of room shapes.
If a doorway is placed on an outside edge that isn't the 'exit' square it becomes a boarded up window and is impassable.
posted by Alvy Ampersand at 9:21 AM on December 10, 2019
Yeah there have to be doors on both edges, and doors are always centred on tiles edges so they match. Doorway would be a better way to put it, sorry.
Can you place a door against the outside of the grid, and if so, what does that mean? What do you mean by "navigable?"
The only exit (Game objective) of the grid house is the outside edge of the centre square of the top row. The game begins with the players' characters starting in separate rooms - each player draws and plays a room tile a minimum of 4 rows away from the 'exit' square, and in the first round cannot play a room tile adjacent to one occupied by another player (After that character tokens can share tiles and pass through 'rooms' played by other players). Each turn they draw and play a room tile and move their token to it working towards the exit. Deadends are inevitable and rules can state they should be avoided when possible, but I want them minimized while allowing for a variety of room shapes.
If a doorway is placed on an outside edge that isn't the 'exit' square it becomes a boarded up window and is impassable.
posted by Alvy Ampersand at 9:21 AM on December 10, 2019
Best answer: This feels like it could make an interesting game, but as others have noted, more rules and parameters have to be stated in order to be able to figure out the odds or the optimal mix of cards with different numbers of doors. (And why there even would be 1-doored cards, since they would not advance a path at all, unless the game also includes a defensive strategy of cutting off the path being built by another player.) All in all thought, the math involved with 56 squares would get very complex very quickly. The first card played, for example could go on any of 56 squares, but could be one of 4 different tiles, of which one (4 doors) can only be played one way, but the 3-door tile can be played 3 different ways, the two door can go 2 different ways, and the one-door can go 4 different ways, for a total of 10 different orientations, or 560 possibilities for Play # 1. Play #2 has 55 squares available, so 550 possibilities. The first two plays, therefore, can result in 550 x 560 = 308,000 possible configurations. With 54 more plays to go, the possibilities are astronomical. So on the face of it, without a supercomputer I don't think the game can be optimized mathematically.
Running a lot of trial games would get you pretty close, though. Also, since you presumably want to make it hard, not trivial, to built a wall-to-wall path, the available number of doors should be scarce, not abundant. This suggests including very few 4-door cards, a few more 3-door cards, and lots of 2- and 1-door cards.
posted by beagle at 9:24 AM on December 10, 2019 [1 favorite]
Running a lot of trial games would get you pretty close, though. Also, since you presumably want to make it hard, not trivial, to built a wall-to-wall path, the available number of doors should be scarce, not abundant. This suggests including very few 4-door cards, a few more 3-door cards, and lots of 2- and 1-door cards.
posted by beagle at 9:24 AM on December 10, 2019 [1 favorite]
You could try all 2-door cards, but change the mix of adjacent and opposite doors.
posted by clew at 9:37 AM on December 10, 2019
posted by clew at 9:37 AM on December 10, 2019
Correcting the above: the 3-door tile can go 4 different ways, not 3. So that just increases the complexity.
posted by beagle at 9:38 AM on December 10, 2019
posted by beagle at 9:38 AM on December 10, 2019
It sounds to me like you're looking for something like game balance rather than optimal navigability, since this is a competitive game so opposing players will have different definitions of what is optimal - for my opponent it is 0 after all.
posted by Think_Long at 9:39 AM on December 10, 2019
posted by Think_Long at 9:39 AM on December 10, 2019
This sounds a little like Karuba, so if you can find an analysis of that game it might apply to yours.
posted by RobotVoodooPower at 9:43 AM on December 10, 2019
posted by RobotVoodooPower at 9:43 AM on December 10, 2019
This sounds like the old Texas Instruments game "hunt the wumpus"...might give you some ideas.
posted by notsnot at 10:01 AM on December 10, 2019
posted by notsnot at 10:01 AM on December 10, 2019
Best answer: I don't think there's going to be a substitute for good old-fashioned game-testing here. (Try a certain mix, get people together and play several times. Is it too easy to get to the target square? Too hard? Too much of an advantage in going first? Adjust based on results and repeat.)
I think it's going to be too complex to model mathematically - but if you wanted to try, first you'd need to have clearly defined, objective goals, expressed mathematically; and other than "minimize dead ends," I haven't seen one yet. So maybe think about what those clear, mathematical goals should be?
Once you knew what those goals were, one approach would be to program a computer to play the game, and run a Monte Carlo simulation over thousands of trials to see what tile mix best meets your objectives. You'd need to program your computer players with some sort of strategy, though. "Play randomly" is simple, but not reflective of how humans would play. "Play towards the target square as much as possible" is somewhat better. It wouldn't fully capture how humans would play (doesn't consider the possibility of defensive play, for one), but it has the advantage of being easy to program, and might be enough to make a first approximation before you begin human playtesting. But only if you have clearly expressed mathematical objectives. Without that clear expression, you're asking for a mathematical answer to a non-mathematical question.
posted by DevilsAdvocate at 10:52 AM on December 10, 2019 [2 favorites]
I think it's going to be too complex to model mathematically - but if you wanted to try, first you'd need to have clearly defined, objective goals, expressed mathematically; and other than "minimize dead ends," I haven't seen one yet. So maybe think about what those clear, mathematical goals should be?
Once you knew what those goals were, one approach would be to program a computer to play the game, and run a Monte Carlo simulation over thousands of trials to see what tile mix best meets your objectives. You'd need to program your computer players with some sort of strategy, though. "Play randomly" is simple, but not reflective of how humans would play. "Play towards the target square as much as possible" is somewhat better. It wouldn't fully capture how humans would play (doesn't consider the possibility of defensive play, for one), but it has the advantage of being easy to program, and might be enough to make a first approximation before you begin human playtesting. But only if you have clearly expressed mathematical objectives. Without that clear expression, you're asking for a mathematical answer to a non-mathematical question.
posted by DevilsAdvocate at 10:52 AM on December 10, 2019 [2 favorites]
Best answer: I think this game would fall under the area of Mathematics called decision theory, but I don't think that's going to be very useful. You might be able to "solve" a 2x3 grid, or even a 3x3 grid, but the possibilities grow very rapidly as the array gets bigger.
A more likely approach is a computer simulation. It would not be too hard (for someone who does this sort of thing) to simulate what might be called a naive version where each player has a set of rules that get followed. A rule might be "if there is an empty path to the exit, place a door in the direction of the shortest empty path". The rules would be examined in order, and the first one that applies would be followed. Given such a program, you could run it a bunch of times and see how many games resulted in a player winning, and how many turns it required. So you would have a tool to experiment with the numbers of tiles of various types.
The problem is that a more realistic version where, for example, a player could play to block another player would be much more difficult to program. It would be a big project.
OTOH, I think that if you just make some guesses and try to play the game, you will learn a lot pretty quickly. Think about the total number of doors on all the tiles. You can guess that 1 is too few doors and (4x56) = 224 doors is too many. Just playing with 75, 100, and 150 doors should be instructive.
posted by SemiSalt at 10:56 AM on December 10, 2019 [2 favorites]
A more likely approach is a computer simulation. It would not be too hard (for someone who does this sort of thing) to simulate what might be called a naive version where each player has a set of rules that get followed. A rule might be "if there is an empty path to the exit, place a door in the direction of the shortest empty path". The rules would be examined in order, and the first one that applies would be followed. Given such a program, you could run it a bunch of times and see how many games resulted in a player winning, and how many turns it required. So you would have a tool to experiment with the numbers of tiles of various types.
The problem is that a more realistic version where, for example, a player could play to block another player would be much more difficult to program. It would be a big project.
OTOH, I think that if you just make some guesses and try to play the game, you will learn a lot pretty quickly. Think about the total number of doors on all the tiles. You can guess that 1 is too few doors and (4x56) = 224 doors is too many. Just playing with 75, 100, and 150 doors should be instructive.
posted by SemiSalt at 10:56 AM on December 10, 2019 [2 favorites]
Response by poster: The first two plays, therefore, can result in 550 x 560 = 308,000 possible configurations.
8O
since you presumably want to make it hard, not trivial, to built a wall-to-wall path, the available number of doors should be scarce, not abundant. This suggests including very few 4-door cards, a few more 3-door cards, and lots of 2- and 1-door cards
Thank god this jibes with what I was leaning towards, if only because my brain was associating the number of doorways to a specific sort of room and the 3+ doorway spaces were very boring; out of 56 rooms there were only a couple 4-door doorways (Foyers), a handful of 3-doorway T-intersections & 2-doorway opposite end tiles (Corridors & Hallways and two Secret Passage tiles that were exempt from the rules and could connect room tiles without doorways), a single 1-doorway room (Broom closet, or something more sinister...?), and a bunch of rooms with 2 orthogonal/perpendicular/L-shaped doorways.
- without a supercomputer I don't think the game can be optimized mathematically
- I think it's going to be too complex to model mathematically
Damn you, Math! Thank you, MeFi!
posted by Alvy Ampersand at 11:31 AM on December 10, 2019
8O
since you presumably want to make it hard, not trivial, to built a wall-to-wall path, the available number of doors should be scarce, not abundant. This suggests including very few 4-door cards, a few more 3-door cards, and lots of 2- and 1-door cards
Thank god this jibes with what I was leaning towards, if only because my brain was associating the number of doorways to a specific sort of room and the 3+ doorway spaces were very boring; out of 56 rooms there were only a couple 4-door doorways (Foyers), a handful of 3-doorway T-intersections & 2-doorway opposite end tiles (Corridors & Hallways and two Secret Passage tiles that were exempt from the rules and could connect room tiles without doorways), a single 1-doorway room (Broom closet, or something more sinister...?), and a bunch of rooms with 2 orthogonal/perpendicular/L-shaped doorways.
- without a supercomputer I don't think the game can be optimized mathematically
- I think it's going to be too complex to model mathematically
Damn you, Math! Thank you, MeFi!
posted by Alvy Ampersand at 11:31 AM on December 10, 2019
« Older Where are all the cool stamps? | What are the options for Mongolian BBQ in NYC or... Newer »
This thread is closed to new comments.
posted by Huffy Puffy at 8:24 AM on December 10, 2019