# Tic-tac-toe checking

Discussion in 'Ruby' started by CBlair1986, Oct 16, 2005.

1. ### CBlair1986Guest

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, Oct 16, 2005

2. ### dazGuest

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.

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[x][y]
puts "... square occupied by #@player"
return
else
@grid[x][y] = @player
end
puts inspect

if check_win(x, y)
puts "\n #@player is the WINNER"
exit
end
@player = (@player == :O ? :X : :O)
end

def check_win(x, y)
winx, winy = true, true
wnd1, wnd2 = true, true
@dims.times do |n|
winx = false if @grid[x][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 :O 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 :O
g.play(0, 1) # doesn't get here

#-------------------------------------------------------------------
<OUTPUT>

O plays: 2, 3

   
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | O |
+---+---+---+---+
| | | | |
+---+---+---+---+

X plays: 3, 0

   
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | O |
+---+---+---+---+
| X | | | |
+---+---+---+---+

O plays: 3, 2

   
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | O |
+---+---+---+---+
| X | | O | |
+---+---+---+---+

X plays: 3, 0
.... square occupied by X

X plays: 2, 1

<---snip--->

X plays: 2, 0

   
+---+---+---+---+
| O | | | X |
+---+---+---+---+
| | O | | X |
+---+---+---+---+
| X | X | | O |
+---+---+---+---+
| X | | O | O |
+---+---+---+---+

O plays: 2, 2

   
+---+---+---+---+
| O | | | X |
+---+---+---+---+
| | O | | X |
+---+---+---+---+
| X | X | O | O |
+---+---+---+---+
| X | | O | O |
+---+---+---+---+

O is the WINNER

daz, Oct 16, 2005

3. ### dazGuest

Interesting (short line wins).

:-(

daz

daz, Oct 16, 2005
4. ### Randy KramerGuest

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.
I wasn't real clear on the above, is that related to your snip reminder? If
not, what should stop there?

regards,
Randy Kramer

Randy Kramer, Oct 16, 2005
5. ### Randy KramerGuest

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

Randy Kramer, Oct 16, 2005
6. ### dazGuest

No, sorry - an unintended ambiguity.
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

daz, Oct 17, 2005
7. ### Randy KramerGuest

Now I understand! Thanks!

Randy Kramer

Randy Kramer, Oct 18, 2005
8. ### dazGuest

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:
http://en.wikipedia.org/wiki/Connect_Four
http://www.mathsisfun.com/games/connect4.html

(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

#------------------------------------------------------------
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

((v+1-@nwin)..(v-1+@nwin)).each do |ev|
# ----> <----
dh+=1; dh-=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)
@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

daz, Oct 19, 2005