当前位置： 文江博客话题详情

连接4：检查获胜者

发布于 2024-10-19 11:36:05 字数 2168 浏览 1 评论 0原文

在Delphi中，我有一个数组形式的Connect 4棋盘表示（7列x 6行）：

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

每个元素可以有三种不同的状态：

  • 1 = 玩家1的棋子
  • 0 = 空
  • -1 = 玩家2的棋子

现在我需要一个函数它检查是否有获胜者或平局：

function CheckForWinner(): SmallInt;

...其中 1 表示玩家 1 获胜，0 表示平局，-1 表示玩家 2 获胜，“nil”表示尚未结束的游戏。

我的草案如下 - 分为两个单一功能：

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;

您认为这种方法怎么样？您有更好（更快/更短）的解决方案吗？

非常感谢！

原文

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!

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（4）

忘羡 2024-10-26 11:36:05

我没有读你的代码。我只是选择用一张白纸自己写一些。

这是我的版本：

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;

一大堆代码。使用暴力方法，对于 Connect 4 来说性能并不重要。不喜欢四个相同的 if Result<>stNone then exit; 行，但您肯定可以想到一种更简洁的方法。代码尚未运行。可能根本就行不通！！这正是我的大脑试图解决问题的方式。

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.

回复 原文
我为君王 2024-10-26 11:36:05

检查获胜者的方式与您的方式非常相似，只是代码少了一点。
我认为您不需要检查所有字段来确定游戏是否完成。当您在游戏中掉落棋子时，只需增加一个计数器即可。如果计数器达到 42 并且尚未分出胜负，则游戏为平局。

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;

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;
回复 原文
柠栀 2024-10-26 11:36:05

免责声明：我没有详细研究该算法。下面的评论只是我盯着代码不到十秒后的第一反应。

我有一些非常简短的评论。首先，我认为

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

更好。当然，您可以通过执行以下操作来保存与旧代码的兼容性

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

其次，

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;

您不需要 begin 和 end 部分：

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

更重要的是，作为性能的提高，您一旦将 drawn 设置为 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;

但是，这只会中断 z 循环。要打破这两个循环，最好的方法是将上面的整个块放在本地函数中。我们将其称为 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;

或者，您可以使用 label 和 goto 一次性跳出两个循环。

更新

我现在知道你可以这样做

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

，甚至不需要引入 draw 局部变量！

结束更新

此外，

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

很糟糕。你应该做的只是

result := inRow = 4;

最后，按照我的口味

s := s+sChange;

应该这样写

inc(s, sChange);

，

inRow := inRow+1

应该是

inc(inRow);

哦，并且nil是一个指针，而不是一个整数。

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.

回复 原文
落在眉间の轻吻 2024-10-26 11:36:05

John Tromp 的 Fhourstones Benchmark 源代码使用了一种有趣的算法来测试四连胜游戏的获胜情况。该算法使用以下游戏位板表示：

.  .  .  .  .  .  .  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

红色玩家有一个位板，黄色玩家有一个位板。 0 代表空单元格，1 代表已填充单元格。位板存储在无符号 64 位整数变量中。位 6, 13, 20, 27, 34, 41, >= 48 必须为 0。

算法是：

// 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;
}

你必须调用最后一步棋的玩家的位板的函数

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

回复 原文
~没有更多了~

关于作者

贱贱哒

暂无简介

0 文章
0 评论
520 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

烙印

文章 0 评论 0

singlesman

文章 0 评论 0

给自己一个微笑

文章 0 评论 0

独孤求败

文章 0 评论 0

晨钟暮鼓

文章 0 评论 0

我是自愿种绣球花的

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文