Algorithms 101: Directional Search Algorithm for Gomoku

•

admin

In this blog, we will explore the implementation and optimization of a directional search algorithm to determine the win condition in a game like Gomoku (五子棋). Gomoku is a traditional board game where two players take turns placing black or white stones on a grid, with the objective of aligning five or more stones of the same color in a row. We will walk through the algorithm step by step, explain the logic behind the code, and provide tips and related LeetCode problems for further practice.

在本博客中，我们将探讨如何实现和优化一个方向搜索算法，以确定在五子棋等游戏中的获胜条件。五子棋是一种传统的棋盘游戏，两个玩家轮流在网格上放置黑或白的棋子，目标是将五颗或更多相同颜色的棋子排列成一行。我们将逐步解析算法，解释代码背后的逻辑，并提供提示和相关的LeetCode问题供进一步练习。

Understanding the Algorithm

Algorithm Overview

English:
The algorithm implemented in this code is a directional search algorithm to determine if a given move results in a win condition in Gomoku. The core idea is to check all possible directions (horizontal, vertical, and diagonal) for consecutive pieces of the same color.

Chinese:
此代码中实现的算法是一种方向搜索算法，用于确定在五子棋中给定的移动是否导致获胜条件。算法的核心思想是检查所有可能的方向（水平、垂直和对角线），看是否有连续的相同颜色的棋子。

Key Steps in the Algorithm:

  1. Directional Movement:

    • English: Moving from the initial point in both directions along a line (e.g., left-right, up-down, or diagonal) and counting the number of consecutive pieces of the same color.
    • Chinese: 从初始点沿一条线的两个方向移动（如左-右，上-下或对角线），并计算连续的相同颜色的棋子数量。

  2. Validation Check:

    • English: For each direction, the algorithm checks if the current move stays within the board’s boundaries and matches the player’s color.
    • Chinese: 对于每个方向，算法检查当前移动是否在棋盘范围内并且颜色匹配。

  3. Early Termination:

    • English: The search stops early if no more consecutive pieces of the same color can be found in both directions.
    • Chinese: 如果在两个方向上找不到更多的连续相同颜色的棋子，搜索会提前停止。

  4. Win Condition:

    • English: If five or more consecutive pieces are found in any direction, the player is declared the winner.
    • Chinese: 如果在任一方向上找到五个或更多连续的棋子，则玩家被判为获胜。

Initial Implementation

Let’s start by looking at the initial implementation of the algorithm:

def isValid(board, point, color):
    ROWS = len(board)
    COLS = len(board[0])
    i, j = point
    return i >= 0 and i < ROWS and j >= 0 and j < COLS and board[i][j] == color

def moveUp(point):
    i, j = point
    return i - 1, j

def moveDown(point):
    i, j = point
    return i + 1, j

def moveLeft(point):
    i, j = point
    return i, j - 1

def moveRight(point):
    i, j = point
    return i, j + 1

def moveUpLeft(point):
    i, j = point
    return i - 1, j - 1

def moveUpRight(point):
    i, j = point
    return i - 1, j + 1

def moveDownLeft(point):
    i, j = point
    return i + 1, j - 1

def moveDownRight(point):
    i, j = point
    return i + 1, j + 1

def createJudgement(p1Movement, p2Movement):
    def judgement(board, point, color):
        count = 1
        p1 = p1Movement(point)
        p2 = p2Movement(point)

        while True:
            p1Changed = False
            p2Changed = False

            if isValid(board, p1, color):
                count += 1
                p1 = p1Movement(p1)
                p1Changed = True

            if isValid(board, p2, color):
                count += 1
                p2 = p2Movement(p2)
                p2Changed = True

            if not p1Changed and not p2Changed:
                break

        return count >= 5

    return judgement

# Example of using the judgement functions to check for a win condition
def checkWin(board, point, color):
    directions = [
        createJudgement(moveUp, moveDown),         # Vertical check
        createJudgement(moveLeft, moveRight),      # Horizontal check
        createJudgement(moveUpLeft, moveDownRight),# Diagonal (\) check
        createJudgement(moveUpRight, moveDownLeft) # Diagonal (/) check
    ]

    for judgement in directions:
        if judgement(board, point, color):
            return True
    return False

Explanation:
The above code checks for winning conditions by moving in different directions from a given point on the board. It ensures that a player wins if they can place five or more stones in a row, column, or diagonal.

解释:
上面的代码通过从棋盘上的给定点沿不同方向移动来检查获胜条件。它确保如果玩家能够在一行、一列或对角线中放置五个或更多的棋子，则判定该玩家获胜。

Optimizing the Code

The initial implementation works, but it can be optimized to reduce redundancy and improve readability. Here’s an optimized version of the code:

def isValid(board, point, color):
    ROWS, COLS = len(board), len(board[0])
    i, j = point
    return 0 <= i < ROWS and 0 <= j < COLS and board[i][j] == color

def move(point, direction):
    i, j = point
    di, dj = direction
    return i + di, j + dj

def createJudgement(directions):
    def judgement(board, point, color):
        count = 1

        for direction in directions:
            next_point = move(point, direction)
            while isValid(board, next_point, color):
                count += 1
                next_point = move(next_point, direction)

        return count >= 5

    return judgement

# Example of using the judgement functions to check for a win condition
def checkWin(board, point, color):
    directions = [
        [(0, 1), (0, -1)],   # Horizontal check (right, left)
        [(1, 0), (-1, 0)],   # Vertical check (down, up)
        [(1, 1), (-1, -1)],  # Diagonal (\) check (down-right, up-left)
        [(1, -1), (-1, 1)]   # Diagonal (/) check (down-left, up-right)
    ]

    for dir_pair in directions:
        if createJudgement(dir_pair)(board, point, color):
            return True
    return False

Optimizations:

  1. Consolidating Movement Logic:
    We combined all directional movements into a single move function that takes the direction as a parameter. This eliminates the need for multiple movement functions.

  2. Simplifying Direction Checks:
    We use tuples to represent directions, making the code more concise and easier to manage.

  3. Reduced Redundancy:
    The loop in checkWin checks each pair of opposite directions together, reducing the amount of repeated code.

优化:

  1. 合并移动逻辑:
    我们将所有方向的移动合并为一个 move 函数，该函数将方向作为参数传递。这消除了多个移动函数的需求。

  2. 简化方向检查:
    我们使用元组来表示方向，使代码更简洁且易于管理。

  3. 减少冗余:
    checkWin 中的循环一起检查每对相反方向，从而减少了重复代码的数量。

Tips for Understanding the Algorithm

  1. Understand the Directions:

    • Horizontal Check: Checks left-right direction.
    • Vertical Check: Checks up-down direction.
    • Diagonal Checks: There are two diagonal checks—one from top-left to bottom-right and the other from top-right to bottom-left.

    Chinese:

    • 水平检查: 检查左右方向。
    • 垂直检查: 检查上下方向。
    • 对角线检查: 有两个对角线检查，一个是从左上到右下，另一个是从右上到左下。

  2. Boundary Conditions:
    Ensure that you correctly handle the boundaries of the board to avoid accessing invalid indices. The isValid function does this by checking if the row and column indices are within valid ranges.

    Chinese:
    确保正确处理棋盘的边

界，以避免访问无效的索引。isValid 函数通过检查行和列的索引是否在有效范围内来处理这个问题。

  1. Early Exit:
    The algorithm benefits from early exits when no more valid moves are found in a direction, improving efficiency by avoiding unnecessary checks.

    Chinese:
    算法通过在方向上找不到更多有效移动时提前退出来提高效率，从而避免不必要的检查。

LeetCode Examples for Practice

To solidify your understanding of directional search algorithms, here are some related LeetCode problems for practice:

  1. LeetCode 79: Word Search

    • Problem: Search for a word in a 2D grid.
    • Link: LeetCode 79 – Word Search
    • Concept: Similar to checking for consecutive pieces in a board game, this problem requires directional search and boundary checks.

    Chinese:

    • 问题: 在二维网格中搜索单词。
    • 链接: LeetCode 79 – 单词搜索
    • 概念: 类似于检查棋盘游戏中的连续棋子，此问题需要方向搜索和边界检查。

  2. LeetCode 130: Surrounded Regions

    • Problem: Flip ‘O’s that are surrounded by ‘X’s on a 2D board.
    • Link: LeetCode 130 – Surrounded Regions
    • Concept: The problem involves moving in different directions and checking boundaries, similar to the directional checks in Gomoku.

    Chinese:

    • 问题: 翻转被 ‘X’ 围住的 ‘O’。
    • 链接: LeetCode 130 – 被围绕的区域
    • 概念: 此问题涉及在不同方向上移动并检查边界，类似于五子棋中的方向检查。

  3. LeetCode 200: Number of Islands

    • Problem: Count the number of islands in a 2D grid.
    • Link: LeetCode 200 – Number of Islands
    • Concept: Uses depth-first search (DFS) in all four directions, making it similar to the directional search algorithm used in Gomoku.

    Chinese:

    • 问题: 计算二维网格中的岛屿数量。
    • 链接: LeetCode 200 – 岛屿数量
    • 概念: 使用四个方向的深度优先搜索 (DFS)，类似于五子棋中的方向搜索算法。

  4. LeetCode 212: Word Search II

    • Problem: Find multiple words in a 2D grid.
    • Link: LeetCode 212 – Word Search II
    • Concept: Extends the word search problem to multiple words, involving searching in all possible directions, similar to Gomoku’s directional search.

    Chinese:

    • 问题: 在二维网格中查找多个单词。
    • 链接: LeetCode 212 – 单词搜索 II
    • 概念: 将单词搜索扩展为多个单词，涉及在所有可能方向上搜索，类似于五子棋的方向搜索。

  5. LeetCode 48: Rotate Image

    • Problem: Rotate a matrix.
    • Link: LeetCode 48 – Rotate Image
    • Concept: Focuses on rotating a matrix but helps in understanding how to manipulate and traverse a 2D grid, reinforcing concepts used in directional searches.

    Chinese:

    • 问题: 旋转矩阵。
    • 链接: LeetCode 48 – 旋转图像
    • 概念: 虽然此问题侧重于旋转矩阵，但理解如何操作和遍历二维网格有助于加强方向搜索中使用的概念。

Conclusion

In this blog, we’ve explored the implementation of a directional search algorithm to determine win conditions in Gomoku, optimized the code for better readability and efficiency, and provided related LeetCode problems for further practice. By understanding the core concepts of directional movement, boundary conditions, and early exits, you’ll be well-equipped to tackle similar grid-based problems in coding interviews and competitive programming.

在本博客中，我们探讨了如何实现一个方向搜索算法来确定五子棋的获胜条件，优化了代码以提高可读性和效率，并提供了相关的LeetCode问题供进一步练习。通过理解方向移动、边界条件和提前退出的核心概念，您将能够轻松应对编程面试和竞赛编程中的类似网格问题。

This structured approach will help readers understand the algorithm, see the importance of optimization, and practice with similar problems, making it a comprehensive learning experience.

这种结构化的方法将帮助读者理解算法，看到优化的重要性，并通过类似问题进行练习，从而成为一个全面的学习体验。

Post Views: 50
, , ,

•

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *