Connect 4: Check for winner

Question

In Delphi, I have a Connect 4 board representation (7 columns x 6 lines) in form of an array:

TBoard = Array[1..7, 1..6] of SmallInt;
Board: TBoard; // instance ob TBoard

Each element can have three different states:

• 1 = player 1's pieces
• 0 = empty
• -1 = player 2's pieces

Now I need a function which checks if there's a winner or a draw:

function CheckForWinner(): SmallInt;

... where 1 is player 1's win, 0 is a draw, -1 is player 2's win and "nil" is for a game which has not ended yet.

My draft is as follows - split into two single functions:

function CheckForWinner(): SmallInt;
var playerToCheck: ShortInt;
    s, z: Byte;
    draw: Boolean;
begin
  draw := TRUE;
  for s := 1 to 7 do begin
    for z := 1 to 6 do begin
      if Board[s, z] = 0 then draw := FALSE; // if there are empty fields then it is no draw
    end;
  end;
  if draw then begin
    result := 0;
  end
  else begin
    playerToCheck := Board[lastPieceX, lastPieceY]; // only for last-moving player
    if searchRow(playerToCheck, +1, 0, lastPieceX, lastPieceY) then // search right/left
      result := playerToCheck
    else if searchRow(playerToCheck, 0, +1, lastPieceX, lastPieceY) then // search up/down
      result := playerToCheck
    else if searchRow(playerToCheck, +1, +1, lastPieceX, lastPieceY) then // search right-down/left-up
      result := playerToCheck
    else if searchRow(playerToCheck, +1, -1, lastPieceX, lastPieceY) then // search right-up/left-down
      result := playerToCheck;
    else
      result := nil;
    end;
  end;
end;

function searchRow(player: SmallInt; sChange, zChange: ShortInt; startS, startZ: Byte): Boolean;
var inRow, s, z: SmallInt;
begin
  inRow := 0;
  s := startS;
  z := startZ;
  while (Board[s, z] = player) AND (inRow < 4) AND (s >= 1) AND (s <= 7) AND (z >= 1) AND (z <= 6) do begin
    s := s+sChange;
    z := z+zChange;
    inRow := inRow+1;
  end;
  s := startS-sChange;
  z := startZ-zChange;
  while (Board[s, z] = player) AND (inRow < 4) AND (s >= 1) AND (s <= 7) AND (z >= 1) AND (z <= 6) do begin
    s := s-sChange;
    z := z-zChange;
    inRow := inRow+1;
  end;
  if inRow = 4 then
    result := TRUE
  else
    result := FALSE;
end;

What do you think of this approach? Do you have a better (faster / shorter) solution?

Thank you very much!

Answer 1

I didn't read your code. I just elected to write some myself with a blank slate.

Here's my version:

const
  RowCount = 6;
  ColCount = 7;

type
  TState = (stNone, stA, stB);
  TBoard = array [1..RowCount] of array [1..ColCount] of TState;

function ValidLocation(Row, Col: Integer): Boolean;
begin
  Result := InRange(Row, 1, RowCount) and InRange(Col, 1, ColCount);
end;

procedure Check(
  const Board: TBoard;
  const StartRow, StartCol: Integer;
  const RowDelta, ColDelta: Integer;
  out Winner: TState
);
var
  Row, Col, Count: Integer;
  State: TState;
begin
  Winner := stNone;
  Row := StartRow;
  Col := StartCol;
  State := Board[Row, Col];
  if State=stNone then
    exit;
  Count := 0;
  while ValidLocation(Row, Col) and (Board[Row, Col]=State) do begin
    inc(Count);
    if Count=4 then begin
      Winner := State;
      exit;
    end;
    inc(Row, RowDelta);
    inc(Col, ColDelta);
  end;
end;

function Winner(const Board: TBoard): TState;
var
  Row, Col: Integer;
begin
  for Row := 1 to RowCount do begin
    for Col := 1 to ColCount do begin
      Check(Board, Row, Col, 0, 1, Result);//check row
      if Result<>stNone then
        exit;
      Check(Board, Row, Col, 1, 0, Result);//check column
      if Result<>stNone then 
        exit;
      Check(Board, Row, Col, 1, 1, Result);//check diagonal
      if Result<>stNone then 
        exit;
      Check(Board, Row, Col, 1, -1, Result);//check other diagonal
      if Result<>stNone then 
        exit;
    end;
  end;
  Result := stNone;
end;

Big long pile of code. Uses brute force approach, not that performance matters for Connect 4. Don't like the four identical if Result<>stNone then exit; lines, but you can surely think of a cleaner way. Code has not been run. It might not even work!! Just the way my brain attempted to solve the problem.

Answer 2

Checking for a winner in very much the same way as you do, only with a little less code. I think you wouldn't need to check all fields to determine if the game is done. Just increase a counter when you drop a piece in the game. The game is a draw if the counter reaches 42 and there is no winner yet.

function CheckRow(x, y, xd, yd: Integer): Boolean;
var
  c: Integer;

  function RowLength(x, y, xd, yd: Integer): Integer;
  begin
    Result := 0;
    repeat
      Inc(Result);
      Inc(x, xd);
      Inc(y, yd);
    until not ((x in [1..7]) and (y in [1..6]) and (Board[x, y] = c));
  end;

begin
  c := Board[x, y];

  Result := 4 <= RowLength(x, y, xd, yd) + RowLength(x, y, xd*-1, yd*-1) - 1;
end;

function CheckForWinner(x, y: Integer): Integer;
begin
  Result := 0;
  if CheckRow(x, y, 0, 1) or CheckRow(x, y, 1, 1) or
     CheckRow(x, y, 1, 0) or CheckRow(x, y, 1, -1) then
    Result := Board[x,y];
end;