The Four Color Problem
Quick fact: Did you know that to color a map of the United States so that no two bordering states share the same color, the lowest number of colors you could use is four? Try it out! It's a great puzzle, and a fun way to waste down a box of crayons.
Now that you've gotten a bit of practice with territory-coloring, take a shot at Taro Ito's new game at GameDesign, The Four Color Problem. It's a turn-based strategy game between you and a computer opponent.
A grid of hexagons is created for you, and the hexagons are divided into large chunks (similar to the layout for Dice Wars). Your goal is to color in as much space as you can, while the computer opponent tries to do the same. The catch the size of Maryland is that like the map puzzle, no two adjacent areas can be filled with the same color. Can you dominate the majority of the map with your color?
You play as the black and grey colorer, while the computer plays with green and orange. You alternate turns with your opponent, and alternate between colors (black, green, grey, orange, black, green...). A tally of how many hexagons you've claimed appears at the bottom of the screen. While the immediate instinct is to color in the largest region you can, further play might reveal strategies to help you beat the computer. Each round is won by gaining over half of the hexagons, or if there is a draw (as in, a region can't be filled by either player because all four colors already border it), then the majority takes the cake.
How long can you last against the computer? My record is eight rounds, can you beat it?
This game's pretty fun. I goofed at stage 11, so that's my record so far. Luck plays a role in this game though too.
You actually only need 3 colors to color the map of the US. The 4 color only comes in very special cases(which doesn't exist on our state map).
I'm afraid you do need four colors to color the US State map. Consider the ring of states around Nevada.
However, the Four Color Theorem doesn't apply to the map because of the non contiguous states of Hawaii and Alaska and the oddball split state of Michigan.
Oh, and I liked the game. I could only get up to level 4 though.
Very neat - the only thing that I would like to see is how much each territory is 'worth' before you decide to choose it. Especially on the maps with lots of small areas.
I got to level 8
I believe not being able to tell how many hexagons a territory contains is part of the challenge of selecting the right one, while weighing in the strategy of color placement.
It seems that knowing the exact numbers would reduce the game more to one of rote, but I may be wrong.
I like that this game requires some thought about placing territories as the board fills in, and yet not so much thought to make it a 'heady' game. Just right for my casual self. :)
All that I would add would be an option to save and continue an unfinished game, since a "game" will likely span multiple stages.
Extremely addictive!
I have only one complaint. I think the player should be green/orange rather than gray/black. Your eyes are automatically drawn to the brighter colors, making it difficult to keep track of your own areas. In fact, the entire point of the game is to make the board dark, hard to focus on, and, in my opinion, non-aesthetically pleasing. Even after several games, I had to keep reminding myself that color was the enemy.
The Four Color Problem was actually a very famous issue in topology (a branch of geometry) for over 100 years -- it was proposed in 1852 that only four colors were necessary for any possible map on a plane or sphere, and no one could come up with a counter-example, but it took until the 1970s to come up with a proof. And the proof is still controversial because it contains so many separate cases that it can't be verified by a human.
Fun fact: On a torus (the surface of a donut) a map can take up to seven colors. Which means that if this game were modified so the grid wrapped around to opposite edges, like the game Asteroids, then they'd need to add three more colors to it.
it took me a while to realize that the brighter colors were what I wanted to avoid. To think, all this time I've been helping the enemy...
Jay - I disagree; I think that knowing the size of the area would hardly reduce the game to tedium, since the major gameplay element would still be planning ahead in order to ensure that you get as many of the large area as possible. Just going for the largest area will often end you with less in the end.
The problem, I think, is the AI. As far as I can tell, the computer really doesn't plan ahead much, instead going for the largest area. So letting you know area sizes might make the computer entirely predicatable. That would reduce the game from a competition to a pure logic puzzle - not a bad thing but probably less replayability.
Ideally, I'd like to know area sizes and have a better AI. Realistically, though, I can see why the current gameplay was used.
Ah. As a former mathematician, I was psyched to see this game. But I prefer a version where you try to be the last person who can place color in any area at all--where you strategically try to box out your opponent rather than just trying for maximum area.
I used to play this with kids in childrens' museums. They would draw a big scribble with a black marker, and then we would each get a crayon and see who could last longer in a two-color map war.
Taro Ito is one of my favourite gamedesigners, I like how he takes simple-ideas out of the history of math-puzzling and makes something very fresh out of it.
I totally agree with lizard on the wrong choice of colors, I'd like to add to it that on my old monitor with the sun shining bright outside I almost can't see the difference between black and gray. I think a blue/green-team and a red/yellow one for instance wouldn't really hurt the game. You would still be able to associate yourself with the cold or the warmer colors.
The game really makes you wonder if there isn't an incredible easy method of solving. That is what makes the game very interesting imo. For now I had most succes when I kept my occupied spaces as close to eachother as I could,
but that probably doesn't mean a thing :) .
Hey, if all of the states were perfect hexagrams, wouldn't you need six colors to color the map?
@ Jen
7, actually.
No two-dimensional map needs more than 4 colors.
A field of perfect hexagons (a hexagram is the shape known as the Star of David, and it doesn't tile), however, only needs 3 colors.
Here's an image that shows why three colors are enough for a hexagon field:
http://en.wikipedia.org/wiki/Image:Uniform_tiling_333-t012.png
Interresting game, but it has an extremely annoying sound.
well, i got to stage 13...
the big thing in this game is to lock the computer out of areas... once a few plays have been made, the main thing for you is to look at the board and make your plays only in places where he can also play. this way you take away the spaces he can play in. If you do it right, by the end, you will be left with a number of places to play in and he will be skipping his turns.
I got to level 18 before I stopped playing. I'm pretty sure you can always win every level due to a combination of getting to go first, and the AI making bad choices. The basic strategy is to pick large pieces with as few connections as possible (usually on the edge). It's also important to never take a square the computer has touched with both his colors... since he can't take it, you should save it for later, and take it at your leisure. Be careful when doing that to make sure your new black piece is an odd number of big-piece hops from your last black piece, and the same for gray. In almost every game, the AI will eventually make a bad choice, and pick something that blocks him out of a large number of pieces. Most games for me had me behind at the 3/4 point, but I finished ahead because the AI couldn't make any moves.
can't seem to get past level 3. how sad.
Nice game, well thought of. I agree with a some other people on the brighter colors, when you try to fill a space, you see this tiny dot with the color you're going to fill, but it's hard to tell the difference between gray and black in that tiny spot. Of course this isn't a real problem 'cause you can see the difference in the large blocks too (at the top).
P.S. This was my first post, so if it contains rubbish, please don't be too mad with me.
hehe thanks Jurney that strategy worked wonders.
What's the algorithm to choose country?
Update