Open puzzle about game

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Open puzzle about game

Postby Goahead52 » Sat May 21, 2016 10:55 pm UTC

Game name : "Fill the board"

Goal of the game : the last player to place a piece on the board win.

Material :

Board : grid 14*14 squares
2 scissors
2 Bristol boards in form of grids 10*10 squares : two different colors (red and blue)
Technicalities : all the squares have to be of the same size.

At the setup the board 14*14 squares is empty and placed between the 2 players
How is the game working?

Step 1 : In the fist step each of the 2 players have to cut SECRETLY its grid 10*10 squares in 12 polyminoes of any form or size :
look here for polyminoes: http://mathworld.wolfram.com/Polyomino.html
Polyminoes with holes are allowed.
Each player must start the game with exactly 12 pieces (polyminoes) and the sum of squares of 12 pieces must be equal to 100 squares.
During this step no player knows how his opponents has cut its grid.

Step 2: After this step then the 2 players put simultaneously each one its 12 pieces on the table near his side such as the 24 pieces could be known to the players.

Step 3 : The criterion to determine who lay fist is the piece area.
Each piece have an area of squares.The area of a pentomino is equal to 5 for example, monomino = 1, domino =2 etc...
The player who owns a unique piece with less area start the game with this piece.
Example :
Player red has a piece with area = 1 and the player blue has a piece with less area = 2 then player red start placing this piece any where on the board 14*14.
Player red has a with area = 1 and the player has 2 pieces with less area = 1 then player blue start the game placing this piece.
We compare the pieces area. This step is very important. The minimal area must be UNIQUE. Only the player who owns it could start the game.

Step 4 : Players take their turns alternatively. Turn player is finished when he places one of his piece.

Rules of placement :
- All the pieces must be placed inside the board.
- No piece is allowed to be removed outside the board
- Players on their turn are free to manipulate any piece yet (opponent or friendly) placed on the board in the way they could place their own piece
- No overlapping is allowed.

The game finishes when one of the 2 players can not place his piece.
The winner is the last one who placed a piece.

Question : Is there an optimal strategy to cut the 12 pieces no matter what your opponent`s cut?

Thank you.

User avatar
Sizik
Posts: 1222
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Open puzzle about game

Postby Sizik » Sat May 21, 2016 11:07 pm UTC

If both players have the exact same set of pieces, who goes first?
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sat May 21, 2016 11:17 pm UTC

Good quesstion anyway
First : it is highly unlikely that the 2 players choose the same configuration
Second : If it is the case then they have to take a new re-cut or picking randomly the first player as usual on other games.
Third : that is not the core of the puzzle.

User avatar
Sabrar
Posts: 41
Joined: Tue Nov 03, 2015 6:29 pm UTC

Re: Open puzzle about game

Postby Sabrar » Sun May 22, 2016 12:20 pm UTC

Spoiler:
Did not do complete analysis but below strategy has no apparent weaknesses:

- Cut eleven separate 1x1 holes into your square, that will give you 12 pieces.
- Based on the rules you're guaranteed to go first (unless opponent has the same idea).
- Place your big piece anywhere.
- You can always place your 1x1 pieces into the original holes.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 12:25 pm UTC

Sabrar wrote:
Spoiler:
Did not do complete analysis but below strategy has no apparent weaknesses:

- Cut eleven separate 1x1 holes into your square, that will give you 12 pieces.
- Based on the rules you're guaranteed to go first (unless opponent has the same idea).
- Place your big piece anywhere.
- You can always place your 1x1 pieces into the original holes.


Keep in mind that if you start first with 1x1 as minimal area you need to play this piece 1x1. You can not start with another piece.

User avatar
Sabrar
Posts: 41
Joined: Tue Nov 03, 2015 6:29 pm UTC

Re: Open puzzle about game

Postby Sabrar » Sun May 22, 2016 12:30 pm UTC

Goahead52 wrote:Keep in mind that if you start first with 1x1 as minimal area you need to play this piece 1x1. You can not start with another piece.

I don't see this anywhere in the original rules. Could you point it put for me?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 12:43 pm UTC

Sabrar wrote:
Goahead52 wrote:Keep in mind that if you start first with 1x1 as minimal area you need to play this piece 1x1. You can not start with another piece.

I don't see this anywhere in the original rules. Could you point it put for me?

Quote :

"Player red has a piece with area = 1 and the player blue has a piece with less area = 2 then player red start placing this piece any where on the board 14*14."

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 2:25 pm UTC

In fact this rule is very important. There are pieces easier to place (like 1x1) for example).
If a player tried to use a piece easy to place then he must loose a turn by placing such piece. This allows the second player to "block" any further placement.
I introduced this rule to "sanction" the first player. Otherwise the game will be easy.

The game in fact is a "struggle" of "configurations.
You could start choosing randomly 2 configurations : C1 with a set of pieces (different areas and forms) and C2 another set you will always find that one is a winning one.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Open puzzle about game

Postby Cauchy » Sun May 22, 2016 10:42 pm UTC

Since the players have to place in an alternating fashion and the first player has to start with one of their smallest pieces, does that mean that the players have to play their pieces in size from smallest to largest as well? It sounds like you're making that assumption, but I don't see it anywhere.

Just to make sure I'm understanding your rules correctly, let me try rephrasing them.

1) Each player secretly divides a 10-by-10 grid of squares into 12 orthogonally contiguous pieces. At the same time, the players reveal their partitions.

2) Each player sorts their pieces in ascending order by size, and they compare their lists of sizes. The player whose list is lexicographically first becomes the first player. (Alternately, they go down the lists from the small side until they find a difference in size. The player with the smaller size goes first.) If the players have the same size lists, first player is determined randomly.

3) The player chooses one of their smallest pieces, and places it in the "piece pool". Then, they must take all the pieces from the piece pool and fit them, without overlap, onto a 14-by-14 grid of squares.

4) In alternating order, starting with the second player, the players first place one of their remaining pieces in the piece pool (any piece, or their smallest?) and then attempt to fit all the pieces currently in the piece pool onto the 14-by-14 grid. If a player cannot, then that player loses.

Does that sound correct?
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 11:00 pm UTC

Cauchy wrote:Since the players have to place in an alternating fashion and the first player has to start with one of their smallest pieces, does that mean that the players have to play their pieces in size from smallest to largest as well? It sounds like you're making that assumption, but I don't see it anywhere.

Just to make sure I'm understanding your rules correctly, let me try rephrasing them.

1) Each player secretly divides a 10-by-10 grid of squares into 12 orthogonally contiguous pieces. At the same time, the players reveal their partitions.

2) Each player sorts their pieces in ascending order by size, and they compare their lists of sizes. The player whose list is lexicographically first becomes the first player. (Alternately, they go down the lists from the small side until they find a difference in size. The player with the smaller size goes first.) If the players have the same size lists, first player is determined randomly.

3) The player chooses one of their smallest pieces, and places it in the "piece pool". Then, they must take all the pieces from the piece pool and fit them, without overlap, onto a 14-by-14 grid of squares.

4) In alternating order, starting with the second player, the players first place one of their remaining pieces in the piece pool (any piece, or their smallest?) and then attempt to fit all the pieces currently in the piece pool onto the 14-by-14 grid. If a player cannot, then that player loses.

Does that sound correct?


Correct except :
1 : players divide secretly a grid 10x10 in polyminoes of different size. Even polyminoes with holes are allowed.
2 : the player who goes first MUST place the piece of the smaller size which made him play first. If picked randomly the player could place any piece.
3 : players know each other pieces. So they are (after the starting of the game) free to use any of the remaining pieces. They are free to manipulate ANY piece inside the board 14x14 to place their pieces (rotation, move, etc.... ).
4 : Each player own his 12 pieces so he could place inside the board 14x14 only his own pieces.
5 : After the start of the game where the first player has no choice of placement players could place any of their remaining pieces in any order

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 11:19 pm UTC

Just as an example one of the players could cut a piece like a snake :

*--*---*---*
>>>>>*---*
>>>>>*--- *---*
>>>>>*
>>>>>*---*

a star is representing a square
> is empty space
Inside the "snake" he owns the pieces to place a domino 1x3 or a trimino 1*2*1 etc...
You are free to imagine any complex solution

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Open puzzle about game

Postby PeteP » Sun May 22, 2016 11:25 pm UTC

Goahead52 wrote:
Sabrar wrote:
Goahead52 wrote:Keep in mind that if you start first with 1x1 as minimal area you need to play this piece 1x1. You can not start with another piece.

I don't see this anywhere in the original rules. Could you point it put for me?

Quote :

"Player red has a piece with area = 1 and the player blue has a piece with less area = 2 then player red start placing this piece any where on the board 14*14."

In the suggested configuration (with ten 1 pieces) the small pieces aren't unique though "The player who owns a unique piece with less area start the game with this piece." or is unique just supposed to mean that the other player doesn't have such a piece?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 11:37 pm UTC

PeteP wrote:
Goahead52 wrote:
Sabrar wrote:
Goahead52 wrote:Keep in mind that if you start first with 1x1 as minimal area you need to play this piece 1x1. You can not start with another piece.

I don't see this anywhere in the original rules. Could you point it put for me?

Quote :

"Player red has a piece with area = 1 and the player blue has a piece with less area = 2 then player red start placing this piece any where on the board 14*14."

In the suggested configuration (with ten 1 pieces) the small pieces aren't unique though "The player who owns a unique piece with less area start the game with this piece." or is unique just supposed to mean that the other player doesn't have such a piece?

I meant :
If the players have both k pieces 1x1 then there is no unicity. If one a have k 1x1 and the other k+a (a<0) then the second goes first.
I called it unicity by eliminating those owned equally by each player.
Let us acall the smalllest area piece of the players m1 and m2
If m1<m2 then the player 1 goes first.
If m1=m2 then the player who has more than the other goes first. We look to the cardinal of the smaller pieces OPNLY if they are equal.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Sun May 22, 2016 11:40 pm UTC

I knew that the choice of who is going first will be hard to explain.
The rule is been set up to balance the game and to avoid the "pie rule".

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Mon May 23, 2016 11:06 am UTC

Is it interesting to start first?
If it is then what is the configuration giving more chances to start first?
How to determine : first the sructure of your pieces in terms of area? second : which piece form is optimal?
It is very hard puzzle I think and we need to find the best way to approach it.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Open puzzle about game

Postby Cauchy » Mon May 23, 2016 3:02 pm UTC

Here's a set that's guaranteed a win if it goes second. Cut off a 2-by-2 square from the corner of your 10-by-10 grid, and then cut a 1-by-1 square off of that to make a size 1 piece and an L-shaped size 3 piece. Cut the remaining 96 squares into ten pieces that reassemble to form the shape of a 14-by-14 grid with a 10-by-10 square cut out of the corner. (To maximize your ability to go second, these should be four pieces of size 9 and six pieces of size 10, but I couldn't come up with such a cut in my head so I don't know if it's for sure possible.) Across your first ten turns, assemble the ten larger pieces into the shape I described above, and put your opponent's pieces into the 10-by-10 square: since they were all cut out of a 10-by-10 square, they must all be able to go back in. On your eleventh turn, choose your 1-by-1 square, and for the placing phase, put your ten larger pieces and opponent's pieces into the same configuration as before. Since your opponent hasn't played their last piece, your 1-by-1 square can fit somewhere in the 10-by-10 area you've allotted for your opponent, and so you can place all your pieces. On your opponent's twelfth and final turn, they need to place all their pieces, and all your pieces aside from your size 3 piece. That's 197 squares worth of pieces, which can't possibly fit on a 14-by-14 grid, so they lose.

This sets a size bound on potential winning sets. If there's a single best set, it must beat this set, which means it needs to force this set to go first. That's not particularly hard, but it's nice to know that such a set can't have more than one size 1 piece or more than two pieces of size less than or equal to 3.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Open puzzle about game

Postby PeteP » Mon May 23, 2016 4:51 pm UTC

The most obvious counter is cutting the 2x2 into 2 2x1 instead (I will just call this build B), your build will have to begin with the 1x1 so the same tactic works since 2x1 fits in every piece bigger than 1 and you have to have one of those left at the end. Btw the B variant will also defeat any built without a piece smaller than 4. The other build will go second so when it is time to place the last piece (the second 2x1) the 10x10 shape of the other one will have place for a 2 2x1 (or is there a physically possible shape for a 4+ piece that doesn't allow the placement of 2 2x1?), variant A will probably still beat most builds without small pieces but it is possible that the remaining space does not fit the 3er piece. But builds with more than 1 1x1 could beat variant B while they couldn't beat variant A

Sandor
Posts: 177
Joined: Sat Feb 13, 2010 8:25 am UTC

Re: Open puzzle about game

Postby Sandor » Mon May 23, 2016 4:57 pm UTC

Cauchy wrote:This sets a size bound on potential winning sets. If there's a single best set, it must beat this set, which means it needs to force this set to go first. That's not particularly hard, but it's nice to know that such a set can't have more than one size 1 piece or more than two pieces of size less than or equal to 3.

That second limitation isn't quite right. For example a set with zero 1-pieces and lots of 2-pieces forces your set to go first.

An example of a set that beats your set is identical to your set, but with two 2-pieces instead of the 1-piece and 3-L-piece. You're forced to go first, and to play your 1-piece first. I follow the same procedure as you outlined. Come my second-to-last go, there's bound to be a 2-hole that I can put one of my 2-pieces in, and then you can't play your last piece.

Of course my set is vulnerable to any set with two 1-pieces. Such a set starts with a 1-piece, and saves the other until the end. On my second-to-last go, if there's only a 1-hole remaining, I can't put either of my 2-pieces anywhere.

So:
  • Any set that has two or more 1-pieces loses to your set (as you go second)
  • Any set that has a single 1-piece loses to my set (as I go second, and will have a 2-hole on my second-to-last go)
I conclude an always-wins set must have:
  1. Zero 1-pieces
  2. Fewer than three 2-pieces (zero 1-pieces and three or more 2-pieces loses to my set)
  3. At least one piece smaller than a 4-piece (edit, see PeteP's logic above)
Edit: Ninja'd by PeteP. :( Conclusion 3 added.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Mon May 23, 2016 11:22 pm UTC

Many interesting ideas. Thank you.
Either you play first or second you could start by cutting 2 large pieces : 4x10 and 4x4. No matter what your opponent play you could ALWAYS place them.
The maximal piece is a square of 10x10 assuming that it has holes. As the board is 14x14 you could place 4x10 either horizontally or vertically. Your first play.
I mean second turn if you play first and first turn if you play second.
No matter what your opponent plays you will always place 4x4.
That is the starting point.
10x10 - 56 = 44.
You have to think to how you cut 44 in 10 pieces.
To follow.
Just the first idea.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Open puzzle about game

Postby Cauchy » Tue May 24, 2016 12:24 am UTC

PeteP wrote:(or is there a physically possible shape for a 4+ piece that doesn't allow the placement of 2 2x1?)


The size 4 T-block from Tetris and the size 5 + sign both have this property. I think they're the only two.

Sandor wrote:That second limitation isn't quite right. For example a set with zero 1-pieces and lots of 2-pieces forces your set to go first.


Yeah, that was dumb.


I feel like between A Build and B Build, we're getting close to a thing I was looking for: a set of three builds, X, Y, and Z, such that X beats Y, Y beats Z, and Z beats X. Let's say Build C is the Fastest Build: one piece is the 10-by-10 with eleven 1-by-1 holes carved out, none of which are on the border or adjacent to each other, and the other eleven are the 1-by-1 holes. This is the fastest possible build and will always go first or tie for going first. Its strategy is to drop a 1-by-1 on turn 1, drop the size 89 piece on turn 2, and bide its time the rest of the game. The only ways to beat it when it goes first are to drop a piece on turn 1 awkward enough that the size 89 piece can't fit on the board anymore, or to count screw it by holding onto a size 3 piece on the last turn or two size 1 pieces on the last two turns.

Because of this, I'm pretty sure Build C beats Build B but loses to Build A. Build A goes second against it and hence wins (via the count-screwing method). Build B by design doesn't have sufficiently awkward pieces; it has no 1's; and it can't hold onto a size 3 piece for last, because it can't fit 97 squares worth of material on the board without taking advantage of the holes in the size 89 piece.

Someone can check me, but I think this is a rock-paper-scissors scenario.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Sandor
Posts: 177
Joined: Sat Feb 13, 2010 8:25 am UTC

Re: Open puzzle about game

Postby Sandor » Tue May 24, 2016 7:38 am UTC

Cauchy wrote:Someone can check me, but I think this is a rock-paper-scissors scenario.

I agree. Well played.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Tue May 24, 2016 10:56 am UTC

@Cauchy

Assume that at the turn 12 you have this situation :
- It is the turn of Player 2
- Player 1 has still 1 piece 1x1. Player 1 has played (turn 11). He has the 12th turn remaining
- The board 14x14 is not full yet. If you rearrange the board 14x14 you obtain a remaining square empty of mxm remaining. Player 2 have a piece mxm so if he places it Player 1 looses. I choose mxm but it could be any form on one block that Player 2 owns.

Owning easy pieces (1x1 for example) to place does not mean that you always have the opportunity to place them. It depends on the pieces placed yet on the board 14x14.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Tue May 24, 2016 11:09 am UTC

The big weakness of having 11 pieces 1x1 is that you "choice" is known to your opponent. The next turn you have no choice than placing somewhere on the board 14x14 a 1x1 piece.
Starting from this situation your opponent will have more opportunity to place his pieces if they are diversified.
Last edited by Goahead52 on Tue May 24, 2016 5:27 pm UTC, edited 1 time in total.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Open puzzle about game

Postby Cauchy » Tue May 24, 2016 5:21 pm UTC

Goahead52 wrote:@Cauchy

Assume that at the turn 12 you have this situation :
- It is the turn of Player 2
- Player 1 has still 1 piece 1x1. Player 1 has played (turn 11). He has the 12th turn remaining
- The board 14x14 is not full yet. If you rearrange the board 14x14 you obtain a remaining square empty of mxm remaining. Player 2 have a piece mxm so if he places it Player 1 looses. I choose mxm but it could be any form on one block that Player 2 owns.

Owning easy pieces (1x1 for example) to place does not mean that you always have the opportunity to place them. It depends on the pieces placed yet on the board 14x14.


Something you seem to be forgetting is the total size count. Since each player slices up a 10-by-10 grid, together between them they have 200 squares worth of pieces to work with. The 14-by-14 board has a size of 196 squares. If a player wins while their opponent is holding a 1-by-1 piece, it must be because the board is completely filled: otherwise, their opponent can just choose their 1-by-1 piece on their next turn, and place it in any vacant spot while leaving the rest of the board untouched. In turn, the board can only be completely filled if the sum of the sizes of pieces on it is 196, which means that the sum of sizes of pieces in the players' hands at that time is 4.

In effect, owning pieces that are easy enough to place turns the game into a simple numbers game.

Goahead52 wrote:The big weakness of having 11 pieces 1x1 is that you "choice" is know to you opponent. The next turn you have no choice than placing somewhere on the board 14x14 a 1x1 piece.
Starting from this situation your opponent will have more opportunity to place his pieces if they are diversified.


Yeah, which is why I said that if the opponent can make you unable to place your very large piece with their first move, you will lose. But if you can get that piece onto the board on your second turn, your entire hand is 1-by-1 pieces, which turns the game almost entirely into a numbers game. Your opponent wins if they can get the total to 196 on their turn, which is equivalent to having your two hands have 4 blocks worth of material together. Since you only have 1-by-1 pieces, your opponent can only do this if they end their 11th turn with a size three piece in their hand, or if they end their 10th turn with two 1-by-1 pieces in their hand. This, of course, requires that your opponent has pieces of the correct size, and that they can fit their remaining pieces on the board -- but that's their concern, not yours.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Tue May 24, 2016 7:53 pm UTC

Here is my winning configuration against the configuration suggested
First column : turns
2th column : player 1 who goes first
3th column : player 2
4th column : sum of p1 and p2
5th column : filling of the board 14x14=196
1 89 10 99 99
2 1 10 11 110
3 1 10 11 121
4 1 10 11 132
5 1 10 11 143
6 1 10 11 154
7 1 10 11 165
8 1 10 11 176
9 1 9 10 186
10 1 9 10 196
11 1 1 2 198
12 1 1 2 200
100 100 200

At the turn 10 player 2 has to re-arrange the board to place 9 (3x3). If player2 place his piece player1 looses.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Open puzzle about game

Postby PeteP » Tue May 24, 2016 8:19 pm UTC

There is no way that works (unless player 1 is nice and didn't create the 1x1 pieces by makink make holes in his big piece). The 10er and 9er pieces are too big to place them in holes in the big piece so they have to be distributed in the 96 remaining places. 8*10+2*9 is 98 the second 9er piece has no place.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Tue May 24, 2016 8:27 pm UTC

PeteP wrote:There is no way that works (unless player 1 is nice and didn't create the 1x1 pieces by makink make holes in his big piece). The 10er and 9er pieces are too big to place them in holes in the big piece so they have to be distributed in the 96 remaining places. 8*10+2*9 is 98 the second 9er piece has no place.


Hence you need to re-cut your 12 pieces another to fill the 11 holes (not completely) by adding the pieces 1x1.
I still do not know how many.
Thank for your comment.
You could fill 6 holes 1x1
Each configuration could be beat often by itself.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Tue May 24, 2016 8:58 pm UTC

The puzzle is not solved yet.
As you are allowed to re-arrange the pieces on your turn you could fill the holes (1x1) by the own pieces 1x1 of player 1 yet in the board.
So it needs little bit computation to find the best configuration.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Open puzzle about game

Postby PeteP » Tue May 24, 2016 9:04 pm UTC

Goadhead if the second on was also in response to my answer: That takes putting all 1x1 in the holes they come from into account, 2 of the 1x1 aren't placed yet and there are 9 open places remaining meaning that only 7 places remain where you could place something bigger than 1x1.
Goahead52 wrote:
PeteP wrote:There is no way that works (unless player 1 is nice and didn't create the 1x1 pieces by makink make holes in his big piece). The 10er and 9er pieces are too big to place them in holes in the big piece so they have to be distributed in the 96 remaining places. 8*10+2*9 is 98 the second 9er piece has no place.


Hence you need to re-cut your 12 pieces another to fill the 11 holes (not completely) by adding the pieces 1x1.
I still do not know how many.
Thank for your comment.
You could fill 6 holes 1x1
Each configuration could be beat often by itself.

re-cut? What do you mean by that?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Tue May 24, 2016 9:08 pm UTC

The goal of re-cut is finding new configuration of the 12. So forget 10,10,10,...1,1.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Wed May 25, 2016 12:04 am UTC

Here is the configuration of player2

1 89 1 90 90
2 1 1 2 92
3 1 16 17 109
4 1 16 17 126
5 1 12 13 139
6 1 12 13 152
7 1 12 13 165
8 1 10 11 176
9 1 9 10 186
10 1 9 10 196
11 1 1 2 198
12 1 1 2 200
100 100 200

Each time I re-arrange the board by filling the holes (11) ; 9 owned by my opponent et 2 owned by my (the first 2).
At the turn I fill totally the board 14x14.
As I could rearrange the board it suffices that I use what is required as pieces to make valid a remaining square 3x3.

Player 1 looses.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Open puzzle about game

Postby Cauchy » Wed May 25, 2016 1:06 am UTC

I don't think anyone was saying that Build C is unbeatable. At least, I hope not, because I already pointed out that Build A beats it. In general, Goahead, I think you're misunderstanding what we're doing. The Builds we're proposing aren't suggestions for the unbeatable build. Rather, they're obstacles, Builds that an unbeatable Build would need to defeat. By laying them out along with the criteria for how to defeat them, we impose restrictions on what an unbeatable Build must look like. The goal is to use these to help figure out what the unbeatable Build actually is, or (more likely in my mind) show that an unbeatable Build cannot exist. Case in point: see below.


To expand on the conditions needed for beating Build C: if you don't have a "sufficiently awkward" piece to place on the first turn, then you need a size 3 piece or two size 1 pieces. When you're holding these, the rest of your pieces need to be on the board. Since you only have 96 squares to work with outside Build C's large piece, then when you're holding a size 3 piece, you must have on the board: 10 pieces that make a 14-by-14 grid with a 10-by-10 grid removed from it; and a 1-by-1 piece that fits into one of the holes in Build C's large piece. When you're holding two 1-by-1's, you must have on the board: 8 pieces that make a 14-by-14 grid with a 10-by-10 grid removed from it; and 2 1-by-1's fitting into two of the large piece's holes.

Both of these latter options (a 1 and a 3, or four 1's) cause the Build to go at least as early as Build A and hence lose. So a Build trying to beat Build C in this second way cannot be unbeatable.

Hence, an unbeatable Build must have a piece that can't go on the board at the same time as a full 10-by-10 square. It can't exploit the "put your opponent's pieces back in their 10-by-10 and then place around it" strategy, because the only such Builds that can beat Build C lose to Build A.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Open puzzle about game

Postby curiosityspoon » Wed May 25, 2016 12:40 pm UTC

The smallest piece that can block a "swiss cheese 10x10" piece from coexisting on the board is 13 units, such as a 5x5 letter H, or three edges of a 5x5 square.

The thing about swiss cheese battles, though, is that they lead to a kind of anti-speed creep, up to and beyond the precipice. Obviously if both players have the same general approach, using pieces that are incompatible with each other, the player who goes second (and therefore gets the first discretionary opportunity to play their cheese piece) wins--the first move of the game cannot be large enough to block cheese, since it's guaranteed to be no larger than 8 units in size. As far as "pure" cheese designs, the slowest build that you have room to carve out with individual holes seems to be this:
Image
By easing up on the discontiguity of the holes, though, it's possible to make something like this, which will go second against it and thereby win:
Image
The holes here allow more freedom for both players to fill them in with various other pieces, but as there is no 5x5 open region, it nonetheless still bars anything that can possibly serve as a "cheesebreaker" shape from being able to squeeze into the interior.

And yet that, too, can be beaten by a minor twerk of itself: change the 3 and a 5 into a pair of 4s, and the new version will go second and win. However, in order to be that slow, you have to be devoid of all 1's, 2's, and 3's...which, as previously established, means that a "peaceful" build that has small pieces and focuses on fitting around your square will go first, and the count can never be pushed above 196 until you're stuck with the final piece on your last turn, causing you to lose.

Both lines of attack against the canonical cheese build therefore have their intractable counters: either you're fast enough to be forced into going first against a peaceful build like {1, 3, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10}, and they maneuver the count around you; or you run a cheese/cheesebreaker shape and are vulnerable to a slower cheese variation; or your build is so slow that it has no small pieces and can't possibly take up enough space to run your opponent out of room when it's their turn and they do have such pieces. There can be no "unbeatable" build, even disregarding a possible mirror match where one of the two identical builds has to lose.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Wed May 25, 2016 7:35 pm UTC

Maybe if reduce the size of the board we could see easily if there is an unbeatable configuration.
Player 1 : grid 5x5 to cut in 7 pieces.
Player 2 : grid 5x5 to cut in 7 pieces.
Board to fill : 7x7-49
As 50>49 one player will win. So draws are impossible.
An exhaustive analysis is possible without taking into account the form of the pieces and pieces with holes.

Partitioning 25 in 7 parts is doable so then we could compare in some sort of array the 2 configurations (who goes first is easy to know but who wins need some analysis.
Lot of work to do before reaching any conclusion.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Open puzzle about game

Postby PeteP » Wed May 25, 2016 8:21 pm UTC

That changes the game quite a bit since the difference is only one there will always be enough place (though not necessarily in the right form) until the last move of the second player. The first player will win unless they can't make use of some opening: My strategy (Build D) cut a 3x3 from one corner of the 5x5 the remaining piece consists of 16 and I think the biggest piece that can't be blocked over form. Cut a 2x2 from the 3x3 and turn the part you removed into 5 1x1. => 5*1x1 1*2x2 and the big piee => Beats anything that has less than 5 1x1 or by builds that have 5 but whose piece number 6 is bigger than 2x2. Easily beaten by any faster build though but all faster builds have a big piece that can't just fit around the 5x5 of the enemy.

Build E: cut a 2x1 and 5 1x1 from the inside of the 5x5. It goes first against Build D and wins but is of course beaten by any slower build capable of blocking.

Anyway I think that pretty much makes an unbeatable build impossible. If it has less than 5 1x1 Build D wins. If it is faster than Build D then a slower version of Build E wins.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Open puzzle about game

Postby Goahead52 » Thu May 26, 2016 4:10 pm UTC

The game will be fascinating and exciting if only the areas of the 12 pieces are known to everyone at the starting of the game.
The players are allowed then to cut the definitive form of the piece during the game.
So for the piece area = 19 for example player could cut it as wished on his turn after re-arranging the board. But he can not cut it such as the area is not = 19.

Game will start by publishing 12 areas for each player.
It has to be done simultaneously.
Example :
Player 1 : 89,1,1,1,1. etc...
Player 2 : 9,8,8,8,8,8.8...etc...
The game start when the player going first is chosen.
Any piece placed in the board could not be changed as piece. But could manipulate the piece as you wish (rotation, insertion, move up, down etc.... )
Cut pieces will be done as the game progresses.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Open puzzle about game

Postby curiosityspoon » Thu May 26, 2016 10:51 pm UTC

Figures for the delayed-cutting version:
  • 22 is now the smallest possible bid that allows you to craft a shape that cheese-blocks an opposing bid of 89
  • 64 is the largest possible bid that allows you to craft a shape that is guaranteed to be cheese-proof
  • If both players have a bid of 65 or more (which forces their hand as far as cutting strategy), the player with the slower combination of bids wins
  • In fact, a 65+ bid automatically loses against a bid as low as 36 (which is enough to cut the entire perimeter as a piece) if the 36's combo is slower--and since they have 29 extra points to allot to the rest of their bids and slow them down, it very likely will be.
  • If there are no cheese considerations, and both sides have no bids smaller than a 4, the faster player wins (so {8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9} is the worst set of bids you can possibly make, losing to absolutely everything else)
  • If both sides are headed by a 3, the slower player wins
  • If one side is headed by a 3 (abbreviated 3-x) and the other side has at least two 1s (1-1-x), the 1s win by cutting shapes with 1-space holes in the middle, so that at player 2 turn 11, they either save a 4+ piece for last (in which case they can't block player 1's turn 12, and go over on the final turn), or try to save the 3 for last, in which case there will be a 1-unit hole on the board that's inevitably wasted, to go along with exactly 4 units off the board in reserve, and the 11th piece won't be able to fit
  • 1-1-x loses to 1-3-x, which is slower by definition and can use their own 1 for hole-filling to avoid the wastage issue.
  • 1-3-x loses to 3-x, since the side with the 1 can't hold it in reserve to force an unfillable hole and it devolves into 3-x vs. slower 3-x


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests