Connect 4: Check for winner

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 beg开发者_如何学JAVAin
    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!

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.

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;

Disclaimer: I haven't studied the algorithm in detail. The comments below are merely my first reactions after staring at the code for less than ten seconds.

I have some very quick remarks. First, I think

TCellState = (csUnoccupied, csPlayerA, csPlayerB)
TBoard = Array[1..7, 1..6] of TCellState;

is nicer. Of course, you can save compatibility with your old code by doing

TCellState = (csUnoccupied = 0, csPlayerA = 1, csPlayerB = -1)

Second,

draw := true;
for s := 1 to 7 do begin
  for z := 1 to 6 do begin
    if Board[s, z] = 0 then draw := false;
  end;
end;

You don't need the begin and end parts:

draw := TRUE;
for s := 1 to 7 do
  for z := 1 to 6 do
    if Board[s, z] = 0 then
      draw := false;

More importantly, as a gain in performance, you should break the loops as soon as you have set drawn to false:

draw := true;
for s := 1 to 7 do
  for z := 1 to 6 do
    if Board[s, z] = 0 then
    begin
      draw := false;
      break;
    end;

This will, however, only break the z loop. To break both loops, the nicest way is to put the entire block above in a local function. Let's call it CheckDraw:

function CheckDraw: boolean;
begin
  result := true;
  for s := 1 to 7 do
    for z := 1 to 6 do
      if Board[s, z] = 0 then
        Exit(false);
end;

Alternatively, you can use label and goto to break out of both loops at once.

Update

I see now that you can just do

for s := 1 to 7 do
  for z := 1 to 6 do
    if Board[s, z] = 0 then
      Exit(0);

and you don't even need to introduce the draw local variable!

End update

Furthermore,

if inRow = 4 then
   result := TRUE
 else
   result := FALSE;

is bad. You should do just

result := inRow = 4;

Finally, In my taste

s := s+sChange;

should be written

inc(s, sChange);

and

inRow := inRow+1

should be

inc(inRow);

Oh, and nil is a pointer, not an integer.

The source code from the Fhourstones Benchmark from John Tromp uses a fascinating algorithm for testing a connect four game for a win. The algorithm uses following bitboard representation of the game:

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42  BOTTOM

There is one bitboard for the red player and one for the yellow player. 0 represents a empty cell, 1 represents a filled cell. The bitboard is stored in an unsigned 64 bit integer variable. The bits 6, 13, 20, 27, 34, 41, >= 48 have to be 0.

The algorithm is:

// return whether 'board' includes a win
bool haswon(unsigned __int64 board)
{
    unsigned __int64 y = board & (board >> 6);
    if (y & (y >> 2 * 6))     // check \ diagonal
        return true;
    y = board & (board >> 7);
    if (y & (y >> 2 * 7))     // check horizontal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8))     // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))         // check vertical
        return true;
    return false;
}

You have to call the function for the bitboard of the player who did the last move