August 13, 2009 at 2:22 pm
Can anyone come up with a set of moves in tic-tac-toe that follow these rules and where the very last square gives a win.
Rule 1: If a block is possible it must be made
Rule 2: If a win is possible it must be taken and Rule 2 supercedes rule 1.
I would be curious to know if this is a proven impossibility or if someone can come up with a solution.
EDIT: For sake of communication lets use the grid below:
A1 | B1 | C1
----------------
A2 | B2 | C2
----------------
A3 | B3 | C3
August 13, 2009 at 2:41 pm
Given competent players, tic-tac-toe should always end in a draw. The game only works until you actually understand the mechanics.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
August 13, 2009 at 2:46 pm
GSquared (8/13/2009)
Given competent players, tic-tac-toe should always end in a draw. The game only works until you actually understand the mechanics.
My youngest still likes to play tic-tac-toe sometimes, just not against me. I either win because she makes a dumb mistake or the game ends in a draw.
August 13, 2009 at 2:47 pm
Yes, I have seen wargames. 🙂 I was just curious to find a set of moves where the very last move was a win.
So lets say we change the objective and number of players. There is only 1 player and given the rules above as well as the back and forth of X's and O's being placed on the board the objective is to have a 3 in a row but only on the last X or O placed.
Does that make sense? I think I am confusing myself now. So
X - B2
O - C2
X - C3
O - A1 (must block)
X - A3
O - C1 (must block) choose 1
X - B3 (must win)
But this doesn't fill up the board (it only uses 7 squares) so it doesn't complete the objective'
August 14, 2009 at 7:39 am
This is what I can come up with for Tic-Tac-Toe in SQL:
if object_id(N'tempdb..#TicTacToe') is not null
drop table #TicTacToe ;
if object_id(N'tempdb..#Range') is not null
drop table #Range ;
set nocount on ;
create table #TicTacToe (
[Move] int identity,
Row tinyint not null,
Col tinyint not null,
Val char(1) not null,
Rationale varchar(100),
primary key (Row, Col),
check (Row between 1 and 3),
check (Col between 1 and 3),
check (Val in ('O', 'X'))) ;
create table #Range (
Num tinyint primary key) ;
insert into
#Range (Num)
select
1
union all
select
2
union all
select
3 ;
declare
@win char(1),
@InPlay char(1),
@Oponent char(1),
@Move varchar(100) ;
select
@win = '' ;
-- X goes first
insert into
#TicTacToe (Row, Col, Val, Rationale)
select
abs(checksum(newid())) % 3 + 1,
abs(checksum(newid())) % 3 + 1,
'X',
'First Move' ;
select
@Move = 'X to ' + (select
cast(Row as char(1)) + ':' + cast(Col as char(1))
from
#TicTacToe
where
[Move] = scope_identity())
raiserror (@Move, 10, 1) with nowait ;
select
@InPlay = 'O',
@Oponent = 'X' ;
while @win = ''
begin
-- Win on Row
if exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Val = T2.Val
and T1.Val = @InPlay
and T1.Row = T2.Row
and T1.Col != T2.Col
and not exists -- Not blocked
( select
*
from
#TicTacToe
where
Row = T1.Row
and Val = @Oponent ) )
begin
select
@win = @InPlay ;
raiserror ('Win on row', 10, 1)
break ;
end ;
-- Win on Column
if exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Val = T2.Val
and T1.Val = @InPlay
and T1.Col = T2.Col
and T1.Row != T2.Row
and not exists -- Not blocked
( select
*
from
#TicTacToe
where
Col = T1.Col
and Val = @Oponent ) )
begin
select
@win = @InPlay ;
raiserror ('Win on column', 10, 1)
break ;
end ;
-- Win on Diagonal (from center)
if exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Val = T2.Val
and T1.Val = @InPlay
and T1.Row = 2
and T1.Col = 2
and T2.Row in (1, 3)
and T2.Col in (1, 3)
and not exists -- Not blocked
( select
*
from
#TicTacToe
where
Col in (1, 3)
and Row in (1, 3)
and Val = @Oponent
and Row != T2.Row
and Col != T2.Col ) )
begin
select
@win = @InPlay ;
raiserror ('Win on diagonal (from center)', 10, 1)
break ;
end ;
-- Win on Diagonal (from ends)
if exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Row in (1, 3)
and T1.Col in (1, 3)
and T2.Row in (1, 3)
and T2.Col in (1, 3)
and T1.Row != T2.Row
and T1.Col != T2.Col
and T1.Val = @InPlay
and T2.Val = @InPlay )
begin
select
@win = @InPlay
raiserror ('Win in diagonal (from ends)', 10, 1)
break ;
end ;
-- Make a Move
insert into
#TicTacToe (Row, Col, Val, Rationale)
select top 1
Row,
Col,
Val,
Rationale
from
(
-- Block a threatened row
select
T1.Row,
Num as Col,
@InPlay as Val,
1 as Priority,
'Block Row' as Rationale
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Row = T2.Row
and T1.Col != T2.Col
and T1.Val = @Oponent
and T2.Val = @Oponent
inner join #Range R
on T1.Col != Num
and T2.Col != Num
where
not exists ( select
*
from
#TicTacToe
where
Row = T1.Row
and Col = R.Num )
union all
-- Block a threatened column
select
Num as Row,
T1.Col,
@InPlay as Val,
1 as Priority,
'Block Column' as Rationale
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Col = T2.Col
and T1.Row != T2.Row
and T1.Val = @Oponent
and T2.Val = @Oponent
inner join #Range R
on T1.Row != Num
and T2.Row != Num
where
not exists ( select
*
from
#TicTacToe
where
Col = T1.Col
and Row = R.Num )
union all
-- Block a threatened diagonal (from center)
select
R1.Num as Row,
R2.Num as Col,
@InPlay as Val,
1 as Priority,
'Block Diagonal' as Rationale
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Row = 2
and T1.Col = 2
and T2.Row in (1, 3)
and T2.Col in (1, 3)
and T1.Val = @Oponent
and T2.Val = @Oponent
inner join #Range R1
on R1.Num in (1, 3)
and R1.Num != T2.Row
inner join #Range R2
on R2.Num in (1, 3)
and R2.Num != T2.Col
where
not exists ( select
*
from
#TicTacToe
where
Row = R1.Num
and Col = R2.Num )
union all
-- Block a threatened diagonal (from corners)
select
2 as Row,
2 as Col,
@InPlay as Val,
1 as Priority,
'Block Diagonal' as Rationale
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Row in (1, 3)
and T1.Col in (1, 3)
and T2.Row in (1, 3)
and T2.Col in (1, 3)
and T1.Row != T2.Row
and T1.Col != T2.Col
and T1.Val = @Oponent
and T2.Val = @Oponent
where
not exists ( select
*
from
#TicTacToe
where
Row = 2
and Col = 2 )
union all
-- If no block needed, random move
select
Row,
Col,
Val,
Priority,
'Random Move' as Rationale
from
(select top 1
R1.Num as Row,
R2.Num as Col,
@InPlay as Val,
2 as Priority
from
#Range R1
cross join #Range R2
where
not exists ( select
*
from
#TicTacToe
where
Row = R1.Num
and Col = R2.Num )
order by
newid()) Combos) Moves
order by
Priority ;
-- Check for win
if exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Row = T2.Row
and T1.Col != T2.Col
and T1.Val = T2.Val
inner join #TicTacToe T3
on T1.Row = T3.Row
and T1.Col != T3.Col
and T2.Col != T3.Col
and T1.Val = T3.Val )
or exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Col = T2.Col
and T1.Row != T2.Row
and T1.Val = T2.Val
inner join #TicTacToe T3
on T1.Col = T3.Col
and T1.Row != T3.Row
and T2.Row != T3.Row
and T1.Val = T3.Val )
or exists ( select
*
from
#TicTacToe T1
inner join #TicTacToe T2
on T1.Row = 2
and T1.Col = 2
and T2.Row in (1, 3)
and T2.Col in (1, 3)
and T1.Val = T2.Val
inner join #TicTacToe T3
on T1.Val = T3.Val
and T3.Row in (1, 3)
and T3.Col in (1, 3)
and T3.Row != T2.Row
and T3.Col != T2.Col )
begin
select
@win = @InPlay ;
end ;
select
@Move = @InPlay + ' to '
+ (select
cast(Row as char(1)) + ':' + cast(Col as char(1))
from
#TicTacToe
where
[Move] = scope_identity())
raiserror (@Move, 10, 1) with nowait ;
select
@InPlay = case @InPlay
when 'X' then 'O'
else 'X'
end,
@Oponent = case @Oponent
when 'X' then 'O'
else 'X'
end ;
end ;
print @win + ' wins' ;
select
*
from
#TicTacToe
order by
[Move] ;
I'm sure it can be improved, but it does appear to work.
Edit: Fixed layout issues.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
August 14, 2009 at 9:08 am
Very cool. I have ran this a couple time but sometimes the execution result in an infinite loop. I didn't have time today to figure out where a test was needed I just wanted to let you know.
Thanks again
August 14, 2009 at 9:47 am
Actually, if the whole grid fills up without a win, it will loop forever. Didn't spot that.
Needs to have the While clause modified to add:
and (select count(*) from #TicTacToe) <= 9
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
August 14, 2009 at 10:03 am
You have to try to use up some of the bad squares first before everything becomes forced:
X - A2
O - B1
X - B3
O - C1
X - A1 (must block)
O - A3 (must block)
X - B2
O - C2 (must block) choose 1
X - C3 (must win)
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
Viewing 8 posts - 1 through 7 (of 7 total)
You must be logged in to reply to this topic. Login to reply