[bushindo]

I saw this in a test long ago.

In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3×3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3×3 matrix is completed with five 1’s and four 0’s. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies, who will win and how?

[Guest]

Player 1 Wins


let the 3x3 matrix be


abc

def

ghi


Player 1 Starts, and no matter where he places his 1 the matrix can be rearranged as if he placed it in 'a'

this is based on the nature of a discriminant


for example if he places his 1 in 'f' so the matrix is


abc

de1

ghi


you can take a different matrix to play in and have the exact same results


abc..

de1de

ghigh

..cab


so you then have the matrix


1de

igh

cab


that the game takes place in, and because for now d,e,i,g,h,c,a,b are not yet defined we can just rewrite this matrix


1bc

def

ghi


so essentially player 1 always starts out by playing in 'a'


---


In order for player 0 to win he must make the matrix look like one of the following (with x representing a 0 or 1, because that place makes no difference to who wins.)


xxx	xxx	x0x	xx0

000	xxx	x0x	xx0

xxx	000	x0x	xx0



110	101	100	110	101

110	010	011	001	101

001	101	011	110	010

---


Player 1 Then tries to make every one of these matrices impossible by playing 1's where the 0's are in the above matrices


On turn 2 when player 0 places a 0 on the matrix, he can either leave himself 6 or 7 possible winning matrices. (Neither option will ultimately win... 

but lets assume he plays to get 7 possibilities) which would be playing in 'b', 'c', 'd', or 'g'


Player 1's next move can be made to remove 3 (or 4 in some cases) more possible matrices. Leaving Player 0 with a maximum of 4 matrices


Now when player 0 goes he must limit himself by at least two more, leaving only 2 possible matrices.


Player 1 then blocks one of them.


Player 0 places his 3rd 0, and is one place shy of victory when Player 1 places his fourth 1 to block the last possible winning matrix for player 0.


Thus player 1 will always win.


(I hope that makes sense, it does to me...)

[Guest]

quote name='K4D' date='04 January 2010 - 05:56 AM' timestamp='1262595390' post='215511']

Player 1 Wins


let the 3x3 matrix be


abc

def

ghi


Player 1 Starts, and no matter where he places his 1 the matrix can be rearranged as if he placed it in 'a'

this is based on the nature of a discriminant


for example if he places his 1 in 'f' so the matrix is


abc

de1

ghi


you can take a different matrix to play in and have the exact same results


abc..

de1de

ghigh

..cab


so you then have the matrix


1de

igh

cab


that the game takes place in, and because for now d,e,i,g,h,c,a,b are not yet defined we can just rewrite this matrix


1bc

def

ghi


so essentially player 1 always starts out by playing in 'a'


---


In order for player 0 to win he must make the matrix look like one of the following (with x representing a 0 or 1, because that place makes no difference to who wins.)


xxx	xxx	x0x	xx0

000	xxx	x0x	xx0

xxx	000	x0x	xx0



110	101	100	110	101

110	010	011	001	101

001	101	011	110	010

---


Player 1 Then tries to make every one of these matrices impossible by playing 1's where the 0's are in the above matrices


On turn 2 when player 0 places a 0 on the matrix, he can either leave himself 6 or 7 possible winning matrices. (Neither option will ultimately win... 

but lets assume he plays to get 7 possibilities) which would be playing in 'b', 'c', 'd', or 'g'


Player 1's next move can be made to remove 3 (or 4 in some cases) more possible matrices. Leaving Player 0 with a maximum of 4 matrices


Now when player 0 goes he must limit himself by at least two more, leaving only 2 possible matrices.


Player 1 then blocks one of them.


Player 0 places his 3rd 0, and is one place shy of victory when Player 1 places his fourth 1 to block the last possible winning matrix for player 0.


Thus player 1 will always win.


(I hope that makes sense, it does to me...)

[Guest]

quote name='K4D' date='04 January 2010 - 05:56 AM' timestamp='1262595390' post='215511']

Player 1 Wins


let the 3x3 matrix be


abc

def

ghi


Player 1 Starts, and no matter where he places his 1 the matrix can be rearranged as if he placed it in 'a'

this is based on the nature of a discriminant


for example if he places his 1 in 'f' so the matrix is


abc

de1

ghi


you can take a different matrix to play in and have the exact same results


abc..

de1de

ghigh

..cab


so you then have the matrix


1de

igh

cab


that the game takes place in, and because for now d,e,i,g,h,c,a,b are not yet defined we can just rewrite this matrix


1bc

def

ghi


so essentially player 1 always starts out by playing in 'a'


---


In order for player 0 to win he must make the matrix look like one of the following (with x representing a 0 or 1, because that place makes no difference to who wins.)


xxx	xxx	x0x	xx0

000	xxx	x0x	xx0

xxx	000	x0x	xx0



110	101	100	110	101

110	010	011	001	101

001	101	011	110	010

---


Player 1 Then tries to make every one of these matrices impossible by playing 1's where the 0's are in the above matrices


On turn 2 when player 0 places a 0 on the matrix, he can either leave himself 6 or 7 possible winning matrices. (Neither option will ultimately win... 

but lets assume he plays to get 7 possibilities) which would be playing in 'b', 'c', 'd', or 'g'


Player 1's next move can be made to remove 3 (or 4 in some cases) more possible matrices. Leaving Player 0 with a maximum of 4 matrices


Now when player 0 goes he must limit himself by at least two more, leaving only 2 possible matrices.


Player 1 then blocks one of them.


Player 0 places his 3rd 0, and is one place shy of victory when Player 1 places his fourth 1 to block the last possible winning matrix for player 0.


Thus player 1 will always win.


(I hope that makes sense, it does to me...)

I think you are wrong...

there are a couple more matrices where 0 wins

001 010 100

001 010 100

111 111 111

as well as any permeutation of the rows so 0's 3rd can always be put in a place to have 2 wining moves available

111

[

Edited January 4, 2010 by K4D

[bushindo]

Player 1 Wins


let the 3x3 matrix be


abc

def

ghi


Player 1 Starts, and no matter where he places his 1 the matrix can be rearranged as if he placed it in 'a'

this is based on the nature of a discriminant


for example if he places his 1 in 'f' so the matrix is


abc

de1

ghi


you can take a different matrix to play in and have the exact same results


abc..

de1de

ghigh

..cab


so you then have the matrix


1de

igh

cab


that the game takes place in, and because for now d,e,i,g,h,c,a,b are not yet defined we can just rewrite this matrix


1bc

def

ghi


so essentially player 1 always starts out by playing in 'a'


---


In order for player 0 to win he must make the matrix look like one of the following (with x representing a 0 or 1, because that place makes no difference to who wins.)


xxx	xxx	x0x	xx0

000	xxx	x0x	xx0

xxx	000	x0x	xx0



110	101	100	110	101

110	010	011	001	101

001	101	011	110	010

---


Player 1 Then tries to make every one of these matrices impossible by playing 1's where the 0's are in the above matrices


On turn 2 when player 0 places a 0 on the matrix, he can either leave himself 6 or 7 possible winning matrices. (Neither option will ultimately win... 

but lets assume he plays to get 7 possibilities) which would be playing in 'b', 'c', 'd', or 'g'


Player 1's next move can be made to remove 3 (or 4 in some cases) more possible matrices. Leaving Player 0 with a maximum of 4 matrices


Now when player 0 goes he must limit himself by at least two more, leaving only 2 possible matrices.


Player 1 then blocks one of them.


Player 0 places his 3rd 0, and is one place shy of victory when Player 1 places his fourth 1 to block the last possible winning matrix for player 0.


Thus player 1 will always win.


(I hope that makes sense, it does to me...)

Some comment

The argument is that player 1 and player 0 compete on acheiving and denying possible winning matrices. However, it seems the argument above assumes player 1 and player 0 can make their moves independently of one another. Player 0, however, can force player 1 to make certain moves. For instance, player 0 automatically wins if he get a horizonal or vertical row of all 0's. Therefore, whenever player 0 has a two 0's in a row or column, player 1 is forced to fill in the respective row or column with a 1 to block certain defeat. That may change the dynamic of the game tree.

Edited January 4, 2010 by bushindo

[Guest]

I think you are wrong...

there are a couple more matrices where 0 wins

001 010 100

001 010 100

111 111 111

as well as any permeutation of the rows so 0's 3rd can always be put in a place to have 2 wining moves available

111

[

The matrices you said i left out i excluded for a reason.

If you read the first part I showed that player 1 will always play in spot 'a' the matrices you have listed have player 0 playing in spot 'a'

except for that last one, but I doubt it will effect who wins, I will look into it