ConnectFour

HomePage | RecentChanges | Preferences

Difference (from prior major revision) (no other diffs)

Changed: 1,134c1

Connect Four




After coding tic-tac-toe for my HackerSchool application, I decided to try Connect Four.

One of the things I didn't like about my tic-tac-toe implementation was the brute-force method of checking for a win or a tie. Because there were only 9 squares, I simply checked all the rows, columns, and diagonals to see if the player had won. The Connect Four board is 7 x 6 with 42 squares, so manually checking all the possibilities would be impractical.

I also vaguely recalled from my long ago Data Structures and Algorithms class that you can use a simple array to represent grids and trees by calculating the index in different ways, and wanted to try that, rather than the array-of-arrays I used for tic-tac-toe.

After rather more work than I really want to admit to, I came up with:


rows, cols = 6, 7
board = Array.new(rows*cols)

#display the board, visualizing single array as rows and columns
(0...rows).each { |row|
(0...cols).each { |col|
print row.to_s + " " + col.to_s + " "
print "(" + (cols*row + col).to_s + ") " # index into board array
}
puts
}


which displays the row and column of each position, along with the index into the board array:


$ ruby connect-four.rb
0 0 (0) 0 1 (1) 0 2 (2) 0 3 (3) 0 4 (4) 0 5 (5) 0 6 (6)
1 0 (7) 1 1 (8) 1 2 (9) 1 3 (10) 1 4 (11) 1 5 (12) 1 6 (13)
2 0 (14) 2 1 (15) 2 2 (16) 2 3 (17) 2 4 (18) 2 5 (19) 2 6 (20)
3 0 (21) 3 1 (22) 3 2 (23) 3 3 (24) 3 4 (25) 3 5 (26) 3 6 (27)
4 0 (28) 4 1 (29) 4 2 (30) 4 3 (31) 4 4 (32) 4 5 (33) 4 6 (34)
5 0 (35) 5 1 (36) 5 2 (37) 5 3 (38) 5 4 (39) 5 5 (40) 5 6 (41)


So now if I know the row and column I want, I can calculate the index into the array with cols*row which gives me the offset to the first position in that row, plus col to move over to the correct column.

The next bits were very similar to tic-tac-toe -- loop and alternate between the players, complain and re-prompt if they pick a column that's full, and detect a tie.

Now I'm up to the point where I knew I'd get stuck: detecting four adjacent spots with the same letter.

The code is here: https://github.com/wsmoak/hackerschool/blob/master/connect-four.rb

Ah ha! Repeated rambling pleas to the Google finally turned up A* Pathfinding. http://www.policyalmanac.org/games/aStarTutorial.htm

Update 2010-10-09

I started writing a message to devchix this morning and realized that I *don't* have to check the entire board, I only have to check paths of length 4 starting where the last piece was placed! I sent it anyway, even though it's not the typical sort of message for that group. Either it will be a fun discussion, or I'll learn not to do that again.

Here is some exploratory code around finding the neighbors of the last move:

def index (row, col)
if (0...$rows).member? row
if (0...$cols).member? col
$cols*row + col
end
end
end

r,c = $last_move[:row], $last_move[:col]
puts "Last Move was " + r.to_s + " " + c.to_s
neighbors = [index(r-1,c-1), index(r-1,c), index(r-1,c+1),
index(r,c-1), index(r,c+1),
index(r+1,c-1), index(r+1,c), index(r+1,c+1) ]
puts "neighbors are: " + neighbors.compact.to_s


That eventually turned into this, which is horribly ugly and very, very wrong. Because it traverses the path without keeping track of where it has been, it declares a winner when it finds two adjacent squares. It just moves back and forth until it counts to four! If you start with a partially completed board, it will also allow things like an L-shaped path, or a zig-zag, or any combination thereof. So, tomorrow this will be deleted and I'll start over.


level1 = neighbors(r,c)
for x in level1
puts "Checking whether " + x.to_s + " " + $board[ x[:pos]].to_s + " matches " + $board[index(r,c)].to_s
if $board[ x[:pos] ] && ( $board[ x[:pos]] == $board[index(r,c)] ) then
puts "Level 1 Match!"
level2 = neighbors( x[:row], x[:col] )
puts "Now look at..." + level2.inspect
for y in level2
if $board[ y[:pos] ] && ( $board[ y[:pos]] == $board[index(r,c)] ) then
puts "Level 2 Match!"
level3 = neighbors( y[:row], y[:col] )
puts "Now look at... " + level3.inspect
for z in level3
if $board[ z[:pos]] && ( $board[ z[:pos]] == $board[index(r,c)] ) then
puts "Level 3 Match! -- WINNER IS " + $board[index(r,c)].to_s
exit
end
end
end
end
end


2014-10-10

Success! Now we only move in STRAIGHT lines:


# look right, left, up, down or diagonally (direction of +1 or -1) and count the number of matching squares
def find_match(r, c, row_dir, col_dir)
count = 0
match = true
row = r
col = c
while match do
col += col_dir # move right or left
row += row_dir # move up or down
square = position(row,col)
if square && $board[square[:pos]] == $board[index(r,c)] then
count += 1
else
match = false
end
end
return count
end


and it gets called like this:


#from the last move, look to the left and right and count matches
count = 1 # self
count += find_match(r,c,0,1) # to the right
count += find_match(r,c,0,-1) # to the left
if count >= 4 then
puts "Winner is " + $board[index(r,c)].to_s
exit
end


The code is (still) at https://github.com/wsmoak/hackerschool/blob/master/connect-four.rb




HomePage | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited December 21, 2019 2:52 pm by 78-93-98-198.dsl.wavetel.us (diff)
Search: