在连接四中检查胜负

Question

我做了一个简单的连接四个游戏，我最终将通过创建一个AI，玩家可以玩游戏扩展。鉴于人工智能算法相当复杂，我发现自己希望降低算法的复杂性，我的双赢检查，以最大限度地提高性能，一旦整个事情是建立。

目前，我的棋盘检查板上的所有空格是否获胜。我的双赢检查被分为3种不同的功能-一个用于水平检查，另一个垂直，还有另一个对角线.每个算法本质上都是相同的；为了您的理解，我复制了下面的WinChecker类。正如您所看到的，win检查方法都非常相似，只更改了2或3行代码。

问题是，由于它是目前的设计，每次球员放置一块，我的程序检查大约200个可能的组合在董事会上的胜利。如果我要使用同样的算法来帮助AI推断什么移动，我应该发现自己与一个缓慢的人工智能。然而，即使我有足够的处理能力来快速解决这些问题，我也想学习一些算法，使我的程序尽可能高效。

如何改进我的双赢检查算法，以达到更好或最大的计算效率？

任何关于我的代码的其他评论也是欢迎的。

如果看到更多的程序将帮助您分析代码，则整个项目都是可用的论吉乌布。

class WinChecker:

    def __init__(self, game, board):
        self.game = game
        self.board = board

    def check_for_win(self):
        results = []
        results.append(self.check_win_horizontally())
        results.append(self.check_win_vertically())
        results.append(self.check_win_diagonally())
        try:
            win = results.index(True)
            # if the above statement does not generate a ValueError, then a win exists
            return True
        except ValueError:
            return False

    def check_win_horizontally(self):
        win = False

        for i in range(self.board.rows):
            row = i
            cols = [0, 1, 2, 3]
            while not win:
                try:
                    # seq will represent the current 4 squares being examined
                    seq = []
                    for i in range(len(cols)):
                        # append current 4 squares to seq list
                        seq.append(self.board.board[row][cols[i]])
                    if self.check_equal(seq):
                        return True
                    else:
                        # increment each value in cols, this is how the horizontal
                        # win checking progresses from left to right
                        for i in range(len(cols)):
                            cols[i] += 1
                        continue
                except IndexError:
                    # we've hit the end of this row, break the loop and move to the next row
                    break
        return win

    def check_win_vertically(self):
        win = False

        for i in range(self.board.cols):
            col = i
            rows = [0, 1, 2, 3]
            while not win:
                try:
                    # seq will represent the current 4 squares being examined
                    seq = []
                    for i in range(len(rows)):
                        # append current 4 squares to seq list
                        seq.append(self.board.board[rows[i]][col])
                    if self.check_equal(seq):
                        return True
                    else:
                        # increment each value in rows, this is how the horizontal
                        # win checking progresses from top to bottom
                        for i in range(len(rows)):
                            rows[i] += 1
                        continue
                except IndexError:
                    # we've hit the end of this col, break the loop and move to the next col
                    break

        return win

    def check_win_diagonally(self):
        win = False

        for i in range(self.board.cols):
            col = i
            cols = [col, col+1, col+2, col+3]
            rows = [0, 1, 2, 3]
            while not win:
                try:
                    # seq will represent the current 4 squares being examined
                    seq = []
                    for i in range(len(rows)):
                        # append current 4 squares to seq list
                        seq.append(self.board.board[rows[i]][cols[i]])
                    if self.check_equal(seq):
                        return True
                    else:
                        # increment each value in rows, this is how the diagonal
                        # win checking progresses from top to bottom
                        for i in range(len(rows)):
                            rows[i] += 1
                        continue
                except IndexError:
                    # we've hit the end of this col, break the loop and move to the next col
                    break

        return win

    def check_equal(self, lst):
        return lst[1:] == lst[:-1] if lst[0] != self.board.NONE else False

Answer 1

与其每次检查整个棋盘，不如编写一个函数，检查在给定字段上放置一块是否会导致胜利。然后，这可以用于检查最后一个实际播放的作品是否是一个获胜的作品，或者在实现AI时，这是否是一个放置它的好地方。

对于AI版本来说，一个简单的方法是让win函数返回在这一行中放置了多少个特定类型的片段，以及是否有空间放置剩下的部分。这是一个函数，它可以返回你的同类中有多少块(如果它的4块你赢了)，以及有多少可用的空间在4块以内。

最后，在考虑下一步的移动时，您不需要检查所有的位置，因为碎片会下降到底部，所以您只需要检查每个列的一个。

Answer 2

实际上，您只需要一个函数：

def does_square_contain_win(i, j)

在每个广场，检查4个面具：

   (i,j)
   ▼  
---*--- ---*--- ---**** ---*---
----*-- --*---- ------- ---*---
-----*- -*----- ------- ---*---
------* *------ ------- ---*---

• right_diag：[[i,j], [i-1,j+1], [i-2,j+2], [i-3,j+3]]
• left_diag：[[i,j], [i-1,j-1], [i-2,j-2], [i-3,j-3]]
• 右：[[i,j], [i,j+1], [i,j+2], [i,j+3]]
• 下降：[[i,j], [i-1,j], [i-2,j], [i-3,j]]

为此，编写一个帮助函数，从掩码中选择值，给出一个起始单元格(i,j)，并告诉您它们是否都包含相同的颜色芯片。如果掩码包含任何超出绑定的索引，它将自动返回false。

您的主要功能--告诉您是否存在win --简单地循环每个板元素并在其上调用does_square_contain_win。整个实现应该是10-15行代码。

Answer 3

这可能是不值得的，因为董事会是小的，而4本身是一个很小的数字，但就效率而言，你想要最小化重复的检查。考虑一下检查单个行是否获胜的另一种方法：

def is_row_a_winner(self, row):
    consecutive_items = 0
    last_seen_item = None
    for item in self.board.board[row]:
        if item == self.board.NONE:
            consecutive_items = 0
        elif item == last_seen_item:
            consecutive_items += 1
        else:
            consecutive_items = 1
        last_seen_item = item
        if consecutive_items == 4:
            return True
    return False

这只是检查一行的每个位置一次，而不是4次，所以算法本身就更高效。

如果您不想逐行扫描，而是希望从上次输入的位置进行扫描，则可以使用以下内容：

def is_position_a_winner_row(self, row, col):
    item = self.board.board[row][col]
    cols = len(self.board.board[0])
    if item == self.board.NONE:
        return False
    consecutive_equals = 1
    for delta in (+1, -1):
        next_col = col + delta
        while 0 <= next_col < cols:
            if self.board.board[row][next_col] == item:
                consecutive_equals += 1
            else:
                break
            next_col += delta
            if consecutive_equals == 4:
                return True
    return False

为了避免重复，我们可以将抽象提高一步，并让单个函数有效地检查来自单个位置的win：

def is_position_a_winner(self, row, col):
    item = self.board.board[row][col]
    rows = len(self.board.board)
    cols = len(self.board.board[0])
    if item == self.board.NONE:
        return False
    for delta_row, delta_col in [(1, 0), (0, 1), (1, 1), (1, -1)]:
        consecutive_items = 1
        for delta in (1, -1):
            delta_row *= delta
            delta_col *= delta
            next_row = row + delta_row
            next_col = col + delta_col
            while 0 <= next_row < rows and 0 <= next_col < cols:
                if self.board.board[next_row][next_col] == item:
                    consecutive_items += 1
                 else:
                     break
                 if consecutive_items == 4:
                     return True
                 next_row += delta_row
                 next_col += delta_col
    return False

您必须完成时间安排，但正如我最初所说的，使用Python内置方法(例如list[:-1] == list[1:] )的速度很有可能比我在这里描述的更快，尽管这种方法在算法上效率较低。但那是一个完全不同的故事。