ConnectFour

HomePage | RecentChanges | Preferences

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 October 10, 2014 1:15 pm by WendySmoak (diff)
Search: