Hi all! I have a quick (I hope) question about checking for a
tic-tac-toe win.
I'd like to be able to check for a X-in-a-row win on a Y-by-Y board.
I'd eventually like to be able to check for a 10-in-a-row on a 50-by-50
board. Are there any easy methods I could use, besides doing a check
for each possible win?
Thanks!
CBlair1986 wrote:
Hi all! I have a quick (I hope) question about checking for a
tic-tac-toe win.I'd like to be able to check for a X-in-a-row win on a Y-by-Y board.
I'd eventually like to be able to check for a 10-in-a-row on a 50-by-50
board. Are there any easy methods I could use, besides doing a check
for each possible win?
Hmm, the question seems quick enough 
You're not ready for this, then:
http://www.rubyquiz.com/quiz11.html
(Artificially Intelligent Tic-Tac-Toe)
=====
The method I use for checking is:
1) Only need to check if the current player has won.
( 'O' can't win on 'X's move - and vice-versa)
2) If the player plays on row 2 - check that row only
3) If the player plays on col 1 - check that col only
4) Check both diagonals after each move 'cos it's
probably quicker than deciding whether or not
it's necessary (?)
Summary - check:
1 row, 1 column, 2 diagonals for 1 player after each move.
To do that, I use 4 flags winx, winy, wnd1, wnd2 (ugh!)
They're all set to 'true' at the top of 'check_win'
and within the loop, they're set to false if any test
fails. Once false, they can't become true again before
the end of the method. If any remain true, a complete
row/column/diagonal must have passed the stringent tests!
I know you wanted to do this yourself but I appear to
have done it for you -- which is slightly dumb but I
can never trust my descriptions unless tested.
Thanks!
No problem.
All the busy people are missing.
All the missing people are busy.
~daz
* PLEASE SNIP AS MUCH AS POSSIBLE ON ANY FOLLOW-UP REPLY *
(e.g. everything)
+ + + S T O P H E R E + + +
#-------------------------------------------------------------------
class TTT
def initialize(n, ox = :X)
@dims = n
@grid = Array.new(n) { Array.new(n) }
@player = ox
end
def play(x, y)
puts "\n#@player plays: #{x}, #{y}"
if @grid[y]
puts "... square occupied by #@player"
return
else
@grid[y] = @player
end
puts inspect
if check_win(x, y)
puts "\n #@player is the WINNER"
exit
end
@player = (@player == 
? :X : :O)
end
def check_win(x, y)
winx, winy = true, true
wnd1, wnd2 = true, true
@dims.times do |n|
winx = false if @grid[n] != @player
winy = false if @grid[n][y] != @player
wnd1 = false if @grid[n][n] != @player
wnd2 = false if @grid[@dims-1-n][n] != @player
end
winx || winy || wnd1 || wnd2
end
def inspect # Ignore this garbage - (quick check)
grid = "\n" << ((' [%d]' * @dims) % ((0...@dims).to_a)) << "\n"
sep = '+---'*@dims << "+\n"
grid << sep
@grid.each do |row|
rw = row.map {|e| e || ' '}
grid << '|' << (([' %s '] * @dims).join('|') % rw) << "|\n"
grid << sep
end
grid
end
end
g = TTT.new(4, :O) # select as starter
g.play(2, 3)
g.play(3, 0)
g.play(3, 2)
g.play(3, 0)
g.play(2, 1)
g.play(0, 0)
g.play(0, 3)
g.play(1, 1)
#g.play(1, 2) # would WIN for :X
g.play(1, 3)
g.play(3, 3)
g.play(2, 0)
g.play(2, 2) # WINs for
g.play(0, 1) # doesn't get here
#-------------------------------------------------------------------
<OUTPUT>
O plays: 2, 3
[0] [1] [2] [3]
+---+---+---+---+
> > > >
+---+---+---+---+
> > > >
+---+---+---+---+
> > > O |
+---+---+---+---+
> > > >
+---+---+---+---+
X plays: 3, 0
[0] [1] [2] [3]
+---+---+---+---+
> > > >
+---+---+---+---+
> > > >
+---+---+---+---+
> > > O |
+---+---+---+---+
X | | | |
+---+---+---+---+
O plays: 3, 2
[0] [1] [2] [3]
+---+---+---+---+
> > > >
+---+---+---+---+
> > > >
+---+---+---+---+
> > > O |
+---+---+---+---+
X | | O | |
+---+---+---+---+
X plays: 3, 0
.... square occupied by X
X plays: 2, 1
<---snip--->
X plays: 2, 0
[0] [1] [2] [3]
+---+---+---+---+
O | | | X |
+---+---+---+---+
> O | | X |
+---+---+---+---+
X | X | | O |
+---+---+---+---+
X | | O | O |
+---+---+---+---+
O plays: 2, 2
[0] [1] [2] [3]
+---+---+---+---+
O | | | X |
+---+---+---+---+
> O | | X |
+---+---+---+---+
X | X | O | O |
+---+---+---+---+
X | | O | O |
+---+---+---+---+
O is the WINNER
CBlair1986 wrote:
I'd like to be able to check for a X-in-a-row win on a Y-by-Y board.
Interesting (short line wins).
I just realised, I didn't answer your question, after all.
daz
* PLEASE SNIP AS MUCH AS POSSIBLE ON ANY FOLLOW-UP REPLY *
(e.g. everything)
What a really good idea (putting a snip reminder in each post)--I'll start
doing the same thing, at least on some mail lists.
+ + + S T O P H E R E + + +
I wasn't real clear on the above, is that related to your snip reminder? If
not, what should stop there?
regards,
Randy Kramer
On Sunday 16 October 2005 07:12 am, daz wrote:
But I think (unless I'm missing something), you came pretty close:
Expanding on your explanation, he doesn't have to check the entire row,
column, and both diagonals, just those portions within X of the last move.
Randy Kramer
On Sunday 16 October 2005 07:16 am, daz wrote:
CBlair1986 wrote:
> I'd like to be able to check for a X-in-a-row win on a Y-by-Y board.Interesting (short line wins).
I just realised, I didn't answer your question, after all.
Randy Kramer wrote:
> + + + S T O P H E R E + + +
I wasn't real clear on the above, is that related to your snip reminder?
No, sorry - an unintended ambiguity.
If not, what should stop there?
Original Poster should stop reading because an implementation follows.
My feeling is that, when writing a program like this, more
is learned from "trial and error" than from copying someone
else's algorithm.
daz
On Sunday 16 October 2005 07:12 am, daz wrote:
Randy Kramer wrote:
> CBlair1986 wrote:
> > I'd like to be able to check for a X-in-a-row win
> > on a Y-by-Y board.
>
> Interesting (short line wins).
> I just realised, I didn't answer your question, after all.But I think (unless I'm missing something), you came pretty close:
Expanding on your explanation, he doesn't have to check
the entire row, column, and both diagonals, just those
portions within X of the last move.Randy Kramer
For short line wins, the extra difficulties arising include:
(e.g. 4 from 6)
* X X X O X X
- at the O, reset the counter otherwise it'll count
five within the line as a false win.
* X X X X O X
- at the O, *don't* reset counter otherwise it'll
count to four, reset to 0 and finish with a count
of one. (This forces to check /during/ the count.)
* X O X X X X
- at the O, reset the counter but continue to find the win.
* The current position +/- 4 tends to go out-of-bounds
of the array (OK with Ruby in the +ve direction but
we definitely don't want to be given -ve indices!!)
* Whereas, before, I just checked the two major diagonals
regardless of which square was played, now I "need to"
project in up to 4 directions and stop at the boundaries.
Yuck!
Using a tiny 4x4 grid, all this logic is a real test of stamina 
- We've all been there, right?
8x8 (4 to win) feels a bit more justifiable.
: : : / : : : :
\ : / : : : : :
: X : : : : : :
/ : \ : : : : :
: : : \ : : : :
: : : : \ : : :
: : : : : : : :
: : : : : : : :
Scaling to the OP's 50x50 (10 to win) is accommodated easily 
The game seems more like:
Connect Four - Wikipedia
Play 4 In A Line!
(but not :that: much)
Commented where difficult, here's some code for
newcomers (?) to work with ...
Please rip it to bits - then write something useful
** SNIP AS MUCH AS POSSIBLE FROM ANY FOLLOW-UP REPLY **
(e.g. everything)
Thanks,
~daz
On Sunday 16 October 2005 07:16 am, daz wrote:
#------------------------------------------------------------
class Grid
def initialize(n = 4, nw = 3)
raise 'silly' if nw > n
(puts "\n\n... Get a coffee ..."; sleep 2) if nw > 8
@dims, @nwin = n, nw
@grid = Array.new(n) { Array.new(n) }
@player = 0
end
def each_sq
@dims.times do |v|
@dims.times {|h| yield [v,h] }
end
end
def set(v, h, mk= 0)
@grid[v][h] = mk
end
def diagonals(v, h)
d = [ , ]
dh = [ h-@nwin, h+@nwin ] # [N\West, N/East] hpos
## Start with most northerly vpos and head south
((v+1-@nwin)..(v-1+@nwin)).each do |ev|
# ----> <----
dh[0]+=1; dh[1]-=1 # bump both hpos
## If vpos is out-of-bounds, so are both hpos
(0...@dims) === ev or next
## Check both hpos bounds for this vpos : collect if OK
2.times {|n| (0...@dims) === dh[n] and d[n] << [ev, dh[n]] }
end
# return diagonals (both include current (v,h) position)
d # [[NW\SE], [NE/SW]]
end
Play_marks = ['X', 'O', ':', '\\', '/', '+', '*']
def inspect
@grid.map do |row|
row.map {|e| '%s' % [(e ||= 2) && Play_marks[e]]}.join(' ') << "\n"
end
end
def check_win(v, h)
winx, winy = 0, 0; wnd = [0,0]
d = diagonals(v, h)
@dims.times do |n|
# Accumulate or reset current player's squares
# on the v-vertical or h-horizontal ...
winx = (@grid[v][n] == @player) ? winx+1 : 0
winy = (@grid[n][h] == @player) ? winy+1 : 0
# ... and on the two diagonals which cross at [v,h]
2.times do |dn|
dv, dh = d[dn][n] # next v,h on this diagonal (else nil)
wnd[dn] = (dv && @grid[dv][dh] == @player) ? wnd[dn]+1 : 0
end
# Check for an unbroken line of @nwin length
# before it gets reset ...
(wnd + [winx, winy]).each do |val|
if val == @nwin
set(v, h, @player+5) # mark current pos
return true # win found
end
end unless n < (@nwin-1) # ... no need until @nwin rows
end
false # no win
end
def autoplay(noshow=6)
@moves_avail = (1 << @dims**2)-1 # set bitmap (all ones)
puts "\nDrawing suppressed\n\n" if @dims >= noshow
while @moves_avail > 0
mk = Play_marks[@player]
v,h = ap_rand_move
puts "\nMove: #{mk} - [#{v}, #{h}]\n\n"
set(v, h, @player)
p self unless @dims >= noshow
if check_win(v, h)
if @dims >= noshow
p self
puts "#{Play_marks[@player+5]} marks last move\n\n"
end
puts " ### #{mk} WINs ###\n\n\n"
exit(0)
end
@player = (@player+1) % 2
end
puts " ### TIED GAME ###\n\n\n"
end
def ap_rand_move
move = nil
loop do
move = rand(@dims**2)
mask = 1 << move
unless (@moves_avail & mask).zero?
@moves_avail ^= mask # make unavailable (=0)
break
end
end
move.divmod(@dims) # convert to [v,h] grid pos
end
def show_diags(at_v, at_h)
puts "\nAt: (#{at_v},#{at_h}) ...\n\n"
# find diagonals crossing this square
d1, d2 = diagonals(at_v, at_h)
gt = Grid.new(@dims, @nwin) # a white canvas
d1.each {|v,h| gt.set(v,h, 3) } # '\'
d2.each {|v,h| gt.set(v,h, 4) } # '/'
gt.set(at_v, at_h, 0) # replace with 'X'
p gt # Draw the grid
end
end
g = Grid.new(5, 3) # 5x5 (line of 3 wins)
#p g
g.show_diags(1,0)
g.show_diags(1,3)
g.show_diags(2,3)
# puts 'abort'; abort
#---------------------------------------------------------
=begin
At: (1,0) ...
: / : : :
X : : : :
: \ : : :
: : \ : :
: : : : :
At: (1,3) ...
: : \ : /
: : : X :
: : / : \
: / : : :
: : : : :
At: (2,3) ...
: \ : : :
: : \ : /
: : : X :
: : / : \
: / : : :
=end
#g.each_sq {|v,h| g.show_diags(v,h) }; puts 'abort'; abort
g = Grid.new(4, 3).autoplay # 4x4 (line of 3 wins)
=begin
Move: X - [1, 2]
: : : :
: : X :
: : : :
: : : :
Move: O - [1, 3]
: : : :
: : X O
: : : :
: : : :
Move: X - [3, 2]
: : : :
: : X O
: : : :
: : X :
<-- edit -->
Move: X - [1, 0]
: : O :
X : X O
: O : X
: : X :
Move: O - [2, 2]
: : O :
X : X O
: O O X
: : X :
Move: X - [0, 1]
: X O :
X : X O
: O O X
: : X :
### X WINs ###
=end
Now I understand! Thanks!
Randy Kramer
On Monday 17 October 2005 05:01 pm, daz wrote:
Randy Kramer wrote:
> On Sunday 16 October 2005 07:12 am, daz wrote:
> > + + + S T O P H E R E + + +
> If not, what should stop there?Original Poster should stop reading because an implementation follows.
My feeling is that, when writing a program like this, more
is learned from "trial and error" than from copying someone
else's algorithm.