Winning Strategy in a Diamond Game: Proving Player 1's Advantage

[roadrunner]

So I'm taking a course on game theory and as an intro he left us with this question. I'd like to have it solved fornext class as it is for bonus marks.I'm not sure how to add an attachment here so I will describe the game and board and hopefully someone can tell me how to upload a photo in the meantime.

The board:

Imagine a diamond made up of squares. (Like Fermats triangle) row 1 has one square, row 2 has 2...3 has 3 4 has 4 5 has 5 6 has 6 7 has 5 8 has 4 9 has 3 10 has 2 and 11 has 1.

On the upper left and bottom right sides of the diamond, the boxes touching the edge/side are labeled "b" and the upper right and bottom left are labeled "a"

The game: each player has a pile of blocks and takes turn placing a block anywhere in one of these squares. The object is to connect both a's together or both b's( depending on which was decided at the start) you also need to block the other player from winning.

The question: prove that player 1 ( whoever goes first) has a winning strategy.EDIT: added a photo in next post

My work. Since this is the first class we havnt learned anything so I'm just using what i know. If we assume that both players play optimally and that there is in fact a way to win with both players playing optimally, then played 1 has to have the winning stategy as he will alwas be one block ahead. Also since player 2 is second he will have to be the first one to block the other player to avoid him winning ) since optimally the shortest path would be ideal) That's about the best I can come up with. I also thought about amorous by contradiction but didn't know how to go about that. Ideas? Thoughts? Thanks. I'll post a pic of the board when I can

 

[roadrunner]

I figured out the attachment thing I think.

Player 1 wants to go from say a Red (a) on the top side to a red on the bottom and player 2 wants to go from a blue top side to bottom (or bottom to top)

They must connect using adjacent squares.

The brown tiles (top bottom left and right) are free spots that can be counted as an edge for either player. A player could go from the left brown tile to the right brown tile (or a red) and that would count as a winEDIT: apparently the photo is not working. Why does it show up as cross.bmp on the post but when i go to open it, it saes attachment.php

 

[Petek]

Your attachment works fine for me.

Here's a hint: Can you show that the game can't end in a draw? In other words, the only way for a player to win is by blocking the opponent. Then, think about what this means in terms of "forced wins."

Please post again if you need more hints.

Petek

 

[roadrunner]

but it can end in a draw...we played in class t get used to the game and most of us had draws.

but if i can show that it can't end in a draw if both play the ideal game, then that would mean one has to win and it would be red since he is always ahead one block?

 

[Petek]

I'm pretty sure the game can't end in a draw. It's isomorphic to a well-known (to me, anyway) board game that can't be a draw. I don't want to name the game, so you can try to figure this out for yourself.

You're on the right track when you say that Player 1 is always a move ahead. Assume that Player 2 has a winning strategy. Can you come up with a counter-strategy for Player 1 that contradicts this?

Petek

 

[roadrunner]

no idea what game you are referring to. WHen it comes to board games I play the "new ones" so to say. The only one I can think of would be like tik tak toe (which isn't very similar or isomorphic) or maybe chinese checkers. Maybe a hint on the game?

As for a draw, i think it IS possible. Let's say player one is going from a to a and player 2 is going from b to b. If player one were to connect (and take up the whole middle area) b to b (instead of a to a) then neither players would win (assuming player 2 played equally badly)

I could be mistaken, but I believe that the side you need to connect is pre determined.

although, since each player is playing optimally, they would not try to connect the other color right? is it safe to assume that given players playing optimally, this scenario would not take place?

and so if we assume that no such draw can take place, then obvioulsy player 1 or 2 has to win.

asusming player 2 has a strategy, since player 1 goes first he could place his cube in the space that is ideal or optimal for player 2. thus player 2 has to change strategies and then player 1 takes the new optimal place?

or, since player 1 goes first, player 2 ( who would require the same number of blocks to win) will need to block player 1 at some point. This would mean player 2 is going to stop gaining distance towards their goal and be stuck blockinh player 1 who will keep playing optimally and find his goal?

thanks for the help btw, this is a lot harder than i thought!

 

[Petek]

Your board has 11 rows. Try looking at boards with, say, 3 and 5 rows. That might make it easier to see why you can't have a draw.

Assume that Player 2 has a winning strategy. Now suppose that Player 1 could simply "pass" for his first move. Then he would become the second player and would thus have a winning strategy. The rules don't allow either player to pass, but do you see how Player 1 could "steal" Player 2's strategy? The ideas in your previous post are close to being correct, but can be made more precise.

The game I'm thinking of was invented in the 1940s. One of the co-inventors later won the Nobel Prize for economics. Like I said, I don't want to tell you the game's name. That would ruin the fun!

Petek

 

[roadrunner]

i even googled and tried to find this game with no such luck! :P

i attached another photo. If the green player is attempting to connect a(red) to a (red) and the purple player wants to connect b (blue) to b(blue) would the photo i posted not be a draw?

A game with 3 rows wouldn't work as that would produce 9 squares and eaach player would have an uneven number of pieces (not a fair game)

in 5 rows I can make the same situation that I posted in the photo.

However, if they just need to connect a to a OR b to b (not predefined, then I agree there is no draw possible)


As for your player 2 having a winning strategy info, I'm not sure how that helps. If anything it confused me more :) I understand what you said, but I'm not sure how it relates? I thought when making an assumption you could only assume one thing, not two (player 2 has a strategy and player 1 can pass).

 

[MaxManus]

As for your player 2 having a winning strategy info, I'm not sure how that helps. If anything it confused me more :) I understand what you said, but I'm not sure how it relates? I thought when making an assumption you could only assume one thing, not two (player 2 has a strategy and player 1 can pass).

I don't understand the game at all, but I think Petek only want you to assume that player 2 has a winning strategy and not that player 1 can pass. But you are supposed to think of a move that is equivalent of passing.

 

[Petek]

In your diagram, purple has won by connecting b to b. Note that purple has occupied all the squares in the diagonal row at the top left of the diamond. I see now that it isn't mentioned in your original post, but the four corner squares belong to both a and b. If the rules of your game are different, then I'm thinking of a different game.

Sorry that I confused the issue by introducing the notion of Player 1 passing. Forget about that. Just assume that Player 2 has a winning strategy and find a way for Player 1 to "steal" that strategy and win the game. Since Player 1 wins, the assumption that Player 2 has a winning strategy leads to a contradiction. Although you probably haven't learned it yet, in a perfect information game that cannot end in a tie, either the first or second player must possesses a winning strategy. Therefore Player 1 has a winning strategy.

Here's another hint about the game: The version that I'm thinking of uses hexagons instead of squares, but the possible moves are the same.

Petek

 

[roadrunner]

ahh I forgot about the purple squares. The TA (prof was sick) said that if the top/bottom purples connected or sides connected that was a win, but now that I look at it I think if a bottom connects a side then its still a win. Given that, yes a win is a must.

No we have not learned it, but I did assume that if a win has to happen, then one player has to have a winning strategy.

Are you referring to "HEX"? If so I had never heard of it but I can see how that would be isomorphic.So that makes more sense I think.

Assuming P2 has a wining strat, if player 1 were to make an arbitrary move (the skip you refer to) then he could "steal" player 2's position? and if the strategy ever meant that an already taken square had to be used then another arbitrary square qwould be picked? given that, player 1 would always win

Getting THere?

 

[Petek]

Yes, Hex is the game I had in mind. Your last paragraph is just about correct, but you need to explain why having played on an extra square can never be a disadvantage for Player 1. That might not be true in some other game. Also, just to be picky, the argument is that if Player 2 has a winning strategy, we get a contradiction. So Player 2 doesn't have a winning strategy. Therefore there exists a winning strategy for Player 1, but we don't know what it is.

Petek

 

[roadrunner]

ok cool thanks.

I'm not sure how to prove that having played an extra square is not disadvantageous to player 1. Is it just that since the game is finite, his extra square places him one move ahead of player 2? and if player 2's strategy would be to place his piece where red's extra piece is, then (since player 1 is following player 2's strategy) he would place another random piece (and do the same if it happens again?)

 

[Petek]

I can't speak to what your instructor would accept, but I think all you have to do is show that you considered the issue. Something along the lines of "Having an extra square occupied can never be a disadvantage in this game." or what you said. You can't give a rigorous proof, but you can show that you realized the issue needed to be addressed.

Sounds like this will be a fun course!

Petek