Randy said:
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