Tic-tac-toe checking

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

  1. CBlair1986

    CBlair1986 Guest

    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
    #1
    1. Advertisements

  2. CBlair1986

    daz Guest


    Hmm, the question seems quick enough :p

    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

    [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
     
    daz, Oct 16, 2005
    #2
    1. Advertisements

  3. CBlair1986

    daz Guest

    Interesting (short line wins).
    I just realised, I didn't answer your question, after all.

    :-(

    daz
     
    daz, Oct 16, 2005
    #3
  4. CBlair1986

    Randy Kramer Guest

    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
    #4
  5. CBlair1986

    Randy Kramer Guest

    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
    #5
  6. CBlair1986

    daz Guest

    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
    #6
  7. CBlair1986

    Randy Kramer Guest

    Now I understand! Thanks!

    Randy Kramer
     
    Randy Kramer, Oct 18, 2005
    #7
  8. CBlair1986

    daz Guest


    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

    ## 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
     
    daz, Oct 19, 2005
    #8
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.