From: daz <dooby@...10.karoo.co.uk>
Date: 2005-10-20T03:49:42+09:00
Subject: "Connect Four" (was Re: Tic-tac-toe checking)


Randy Kramer wrote:
> 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.
>
> 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:
  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