Connect 4: check the winner

Question

In Delphi, I have a Connect 4 view (7 columns x 6 rows) as 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 pc.
• 0 = empty
• -1 = player 2 parts

Now I need a function that checks if there is a winner or a draw:

 function CheckForWinner(): SmallInt; 

... where 1 is the victory of player 1, 0 is a draw, -1 is victory of player 2, and “zero” is a game that has not yet ended.

My project is as follows: divide into two separate 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

Checking the winner is the same as you, with only less code. I think you won’t need to check all the fields to determine if the game is complete. Just increase the counter when throwing a piece in the game. A 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; 

Answer 2

I have not read your code. I just decided to write someone with a clean list.

Here is 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; 

A big long bunch of code. It uses brute force, not that performance matters for Connect 4. I don’t like four identical lines if Result<>stNone then exit; but you can, of course, think of a cleaner way. The code has not been run. It may not even work! Just my brain was trying to solve the problem.

Answer 3

Disclaimer: I have not studied the algorithm in detail. The comments below are just my first reactions after you looked at the code for less than ten seconds.

I have very quick comments. Firstly i think

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

it is better. Of course, you can keep compatibility with old code by doing

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

Secondly,

 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 do not 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 performance boost, you should break the loops as soon as you 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, however, leads to a rupture of the cycle z . To break both loops, the best way is to place the whole block above in a local function. Let me 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 two loops at the same time.

Update

Now I see 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 enter a local draw variable!

Final update

Besides,

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

Bad. You should only do

 result := inRow = 4; 

Finally, in my opinion

 s := s+sChange; 

should be written

 inc(s, sChange); 

and

 inRow := inRow+1 

it should be

 inc(inRow); 

Oh and nil is a pointer, not an integer.

Answer 4

John Tromp's Fhourstones Benchmark source code uses a fun four-game testing algorithm to win. The algorithm uses the following board representation:

 . . . . . . . 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 battle for the red player and one for the yellow player. 0 represents an empty cell, 1 represents a filled cell. The bit part is stored in an unsigned 64-bit integer variable. Bits 6, 13, 20, 27, 34, 41,> = 48 must be 0.

Algorithm:

 // 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 must call the function for the player bit that made the last move