Algorithms: Plus One Game Ideas and the Graphed Plus One Game.
November 13, 2010
Here is what I came up with for the last post on the Plus One game, and a new game on graphs.
After some thinking and a number of good comments by Brooke, there seem to be a number of drawbacks with the original game. As I was writing up why I think the original infinite game has no winning solution for player B, I realized what Brooke was actually talking about when she told me to just sort of count by 2’s. I didn’t feel this worked, because you might “skip over” the number. For example, if Player A is the top row and Player B is the bottom row:
But this is really silly. Why doesn’t player B start at the beginning? Since there is no 0, we simply repeat 2. This gives us:
So player B gets it on the fourth try. Does this always work?
After a bit of thought, it should be clear why this works. Because Player A is only adding 1 to their number, Player B can “corner” Player A. What this means is that EVENTUALLY, either Player B gets to a number which is even and 1 less than player A, or Player B gets to exactly Player A’s number. If the latter is true, Player B wins. If the former holds, then on the next turn, they will be at the same number, and Player B wins.
Thus, this is not a very interesting game.
Graph Plus One.
Here’s a new game that I think is kind of fun to play. I’m not sure what a good solution is in general, but there are obvious solutions to certain graphs.
The Game (Graph Plus One): Given a graph (the kind with vertices and edges; see below) player A picks a vertex. Player B guesses. If Player B is right, the game ends and Player B wins. If Player B is wrong, he removes the vertex along with every edge that the vertex touches. Player A is now allowed (if he chooses) to move to any vertex that is connected to his original vertex by an edge.
The following pictures will make this clearer.
First, create a graph. It does not have to be finite, but the following one is. The points are vertices (vertex, singular) and the lines are edges. Let player A secretly pick a vertex. This is denoted by an “A” in my picture below (so A has picked the upper left-hand vertex):
Now player B guesses. Suppose he guesses the lower-left hand vertex. Since A is not on it, he can remove it, as well as the edges that touch it.
Now our graph looks like this:
Where player A has moved to a vertex connected to the one he was just at. Note that he didn’t have to move, but he wanted to. So. There. Now, suppose player B chooses the far-right point. A’s not there, so we remove it.
It should be obvious what to do here for player B, and he can get A in at most two moves. Notice that if player B picked the middle vertex, A cannot move anywhere, and he just must wait for player B to find him. Upsetting.
Now, this game terminates on finite graphs (obviously) and for certain infinite graphs. For example, if our graph is an infinite ray…
This is very similar to our previous Plus One game, with the exception that now player A can move backwards or forwards. With the addition of moving backwards, I no longer think that player B has a finite winning strategy, and he now potentially has, at best, only a countable winning strategy; that is, he will win it countably many turns at most. This statement kind of seems silly, but it’s better than not winning ever.
(Note: It is not even obvious to me that he has a countably winning strategy. The best I can get is sort of an “uncountable” winning strategy: he needs to go up by 2’s and make a whole bunch of single vertices, THEN go back and pick each one.)
For complete graphs, there is no good strategy that I could come up with. It takes at most however many vertices there are, and an average of the number of vertices over 2. If the graph is “not very conntected” we can do a lot better than this.
Either way, just try it out. And enjoy it!