使用 WPF 的螺旋式井字棋 AI 示例

• 下载演示项目 - 51.37 KB
• 下载源代码 - 54.02 KB

引言

本文介绍了一个在螺旋井字棋游戏中实现 Negamax（一种 AI 游戏搜索算法）的 WPF 实现。Negamax 的实现是通用的，几乎不需要解释，但它是一个很好的上手 WPF 的有趣方式。本文不讨论 Negamax 的细节，而是讨论实现目标所需的操作，这涉及到 WPF 线程以及 `DrawingVisual` 的使用。此外，还有一些明显的改进领域供您探索。为了达到更高的搜索深度，您可以使用剪枝技术，如 Alpha-Beta 剪枝来改进 Negamax。或者，您可以将该算法改编为 3D 井字棋游戏，这可以成为熟悉 WPF 3D 图形的良好动力。

总体结构

幸运的是，该应用程序结构清晰。只有一个窗口，以及一个派生自 `FrameworkElement` 的类，作为 `DrawingVisual` 的表面。这些分别包含在 `MainWindow.xaml` 和 `SpiralBoard.cs` 文件中。除了这两个 UI 文件之外，还有一个包含在 `SpiralAI.cs` 中的 `SpiralAI` 类。

从主窗口，您可以通过 **操作** 菜单打开 **开始新游戏...** 对话框。该对话框允许您选择您的棋子（圆或叉），以及是否希望 AI 在您的每一步之后立即执行移动。此外，**操作** 菜单还有 **提示 AI** 和 **撤销** 选项。**提示 AI** 菜单项指示 AI 在未选择自动移动选项时进行移动。菜单下方是用一些三角函数组成的螺旋井字棋盘。棋盘下方是 `System.Windows.Controls` 命名空间提供的进度条。

应用程序的整体结构遵循 **模型-视图-控制器** 设计模式。 `SpiralBoard` 类与 `MainWindow.xaml` 中的控件一起作为视图，`MainWindow` 类的代码隐藏作为控制器，而 `SpiralAI` 类是模型。在 `MainWindow` 类的代码隐藏中，您可以看到我将事件处理程序划分到对模型进行操作的视图事件处理程序和对视图进行操作的模型事件处理程序。从这里，可以清楚地看到 MVC 模式组件之间的界限。

要理解 MVC 模式在此情况下为何有用，请考虑 `SprialBoard` 和 `SprialAI` 对象需要保持同步。这意味着响应用户执行的移动，移动必须依次在 `SpiralBoard` 和 `SpiralAI` 对象上执行。对我来说，这显得很笨拙。我认为更好的职责分离是改为在 `SpiralBoard` 对象上执行移动，然后触发一个事件，最终更新作为模型的 `SpiralAI` 对象。为了实现这种分离，每当您单击一个有效的移动位置时，`SpiralBoard` 类都会引发一个 `MoveRequestEvent` 路由事件。该事件会冒泡到主窗口并在那里处理。随后，一旦移动得到验证，将调用 `SpiralAI` 和 `SpiralBoard` 对象的相应 `ExecuteMove` 方法。

以下是 `SpiralBoard` 类中定义 `MoveRequestEvent` 路由事件所需的代码。

public static readonly RoutedEvent MoveRequestEvent;

public class MoveRequestRoutedEventArgs : RoutedEventArgs
{
    private int _hub;
    private int _spoke;

    public MoveRequestRoutedEventArgs(RoutedEvent routedEvent, 
        object source, int hub, int spoke)
        : base(routedEvent, source)
    {
        _hub = hub;
        _spoke = spoke;
    }

    public int Hub
    {
        get { return _hub; }
    }

    public int Spoke
    {
        get { return _spoke; }
    }
}

static SpiralBoard()
{
    //register routed event

    SpiralBoard.MoveRequestEvent = EventManager.RegisterRoutedEvent(
        "MoveRequest", RoutingStrategy.Bubble, 
         typeof(RoutedEventHandler), typeof(SpiralBoard));
}

public event RoutedEventHandler MoveRequest
{
    add { AddHandler(SpiralBoard.MoveRequestEvent, value); }
    remove { RemoveHandler(SpiralBoard.MoveRequestEvent, value); }
}

当确定您单击了一个有效位置时，`SpiralBoard` 中的 `MouseLeftButtonUp` 事件会引发 `MoveRequestEvent` 路由事件。

private void Board_MouseLeftButtonUp(object sender, 
    System.Windows.Input.MouseButtonEventArgs e)
{
    Point hit = e.GetPosition(this);
    hit.Offset(-this.Width / 2.0, -this.Width / 2.0);

    for (int hub = 0; hub < HUBS; hub++)
    {
        for (int spoke = 0; spoke < SPOKES; spoke++)
        {
            if (Math.Abs(_positions[hub, spoke].X - hit.X) <= TOLERANCE && 
                Math.Abs(_positions[hub, spoke].Y - hit.Y) <= TOLERANCE)
            {
                RaiseEvent(new MoveRequestRoutedEventArgs(
                    SpiralBoard.MoveRequestEvent, this, hub, spoke));
                break;
            }
        }
    }
}

绘制视觉元素和派生自 FrameworkElement

WPF 2D 图形有 3 类对象：`Shapes`（形状）、`Drawings`（绘图）和 `Visuals`（视觉元素）。`Shapes` 派生自 `FrameworkElement`，并带有 `FrameworkElement` 提供的所有额外功能，如输入事件、组合支持和布局功能。因此，它们既方便又低效。如果您只需要绘制一个圆，并且该圆需要参与布局过程，同时还能引发 `MouseLeftButtonUp` 事件，那么您应该使用 `Shape`。

`Drawings` 比 `Shapes` 更轻量级，因为它们派生自 `Animatable` 而不是 `FrameworkElement`。但是，它们不是独立的。`Drawings` 必须在其他东西的上下文中才能使用，而不仅仅是需要所有内容都发生在某个窗口中的简单要求。例如，您可以使用 `Drawing` 作为 `DrawingImage` 的源。反之，`ImageDrawing` 可以绘制 `Image`。这有点拗口。请仔细注意，始终将第一个词视为第二个词的形容词修饰语。`Drawings` 的第二个用途是在 `DrawingVisual` 的上下文中。

那么 `DrawingVisual` 是什么？`DrawingVisual` 派生自 `Visual`，类似于 `FrameworkElement`。但是，`DrawingVisual` 不提供 `FrameworkElement` 的所有功能，而是主要提供一种获取 `DrawingContext` 并绘制可以在某些宿主容器中显示的内容的机制。当然，宿主容器不会是轻量级的。重要的是，可能包含的数百个 `DrawingVisuals` 将是轻量级的。

`DrawingVisual` 的 `RenderOpen` 方法返回一个 `DrawingContext` 对象的引用，该对象可用于执行绘制操作。`DrawingContext` 类似于 GDI+ 中的 `Graphics` 类或 GDI 中的设备上下文。`DrawingContext` 类包含绘制基本图形的方法，以及绘制上述 `Drawing` 对象的方法。`DrawingVisual` 用法的一个好例子是下面所示的 `DrawBoardVisual` 方法。请注意调用 `Close` 方法的重要性，因为 `DrawingContext` 使用非托管资源。或者，可以使用 `using` 语句来确保正确清理。

private DrawingVisual DrawBoardVisual()
{
    DrawingVisual visual = new DrawingVisual();

    DrawingContext context = visual.RenderOpen();

    //draw bounding box with transparent brush

    context.DrawRectangle(Brushes.Transparent, 
        null, new Rect(0, 0, this.Width, this.Height));

    //translate origin

    context.PushTransform(new TranslateTransform(
        this.Width / 2.0, this.Width / 2.0));

    double diameter, decrement;
    int hub, spoke, adjHub, adjSpoke;
    double radius, radians;

    //draw concentric circles

    diameter = 
        this.Width - Convert.ToInt32(0.1 * Convert.ToDouble(this.Width));
    decrement = diameter / HUBS;
    for (hub = 0; hub < HUBS; hub++)
    {
        diameter = diameter - (hub * decrement);
        context.DrawEllipse(null, _boardPen, 
            new Point(0, 0), diameter / 2.0, diameter / 2.0);
    }

    //draw grid lines

    for (radians = 0; radians < (2 * Math.PI); radians += (Math.PI / 6))
    {
        context.DrawLine(_boardPen, new Point(0, 0), 
            new Point(Convert.ToInt32(Math.Cos(radians) * (this.Width / 2))
            , Convert.ToInt32(Math.Sin(radians) * (this.Width / 2))));
    }

    context.Close();

    ...
}

`DrawingVisual` 的输出需要显示在宿主容器中。派生自 `FrameworkElement` 的类是一个不错的选择，因为它在窗口内提供了布局功能，并且还支持输入事件。为了在派生自 `FrameworkElement` 的类中包含 `DrawingVisuals`，需要维护一个 `VisualCollection` 成员，其中包含该元素的所有 `DrawingVisuals`。此外，还需要像下面那样重写 `VisualChildrenCount` 属性和 `GetVisualChild` 方法。

private VisualCollection _visuals;

protected override int VisualChildrenCount
{
    get { return _visuals.Count; }
}

protected override Visual GetVisualChild(int index)
{
    if (index < 0 || index > _visuals.Count)
    {
        throw new ArgumentOutOfRangeException();
    }

    return _visuals[index];
}

我猜 `VisualCollection` 是保留模式图形层运行的核心。`Controls`、`FrameworkElement`、`DrawingVisual` 等都派生自 `Visual` 类，该类定义了 `VisualChildrenCount` 属性和 `GetVisualChild` 方法。通过检查顶层窗口的 `Visual` 子项并递归地遍历其子项的 `Visual` 子项，可以看出应用程序的视觉树是如何确定的。因此，保留模式图形层会了解到为了在屏幕上绘制需要维护什么。

关于 WPF 线程

有些资料声称 WPF 设计得非常好，以至于您可能永远不需要使用像线程这样晦涩的概念。那些资料没有意义。理解 WPF 线程对于理解 WPF 至关重要。如果您是专业程序员，那么理解您正在处理的任何内容中的线程都将使您受益。

WPF 应用程序包含一个 UI 线程和一个渲染线程。UI 线程与应用程序实例创建的第一个窗口相关联。在 Win32 级别，每当一个线程创建一个窗口时，都会动态地将一个消息队列与创建线程相关联。然后，创建线程通常被称为 UI 线程。这并不是 WPF 特有的。该线程不会自动开始处理消息队列；这是您需要做的事情。在 WPF 中，会创建一个 `System.Windows.Threading.Dispatcher` 类的实例，并调用 `Run` 方法以启动消息队列的处理。在某个时刻，该 `Dispatcher` 实例会与窗口的 `Dispatcher` 属性关联。这种关联会为应用程序中的所有其他派生自 `DispatcherObject` 的类元素做出。

我对渲染线程的理解不太确定。渲染线程不拥有窗口或消息队列。它负责与 DirectX 进行实际通信以完成渲染。与 UI 线程的线程冲突不存在，因为是 UI 线程控制着渲染线程。为什么渲染线程会是一个单独的线程？我猜测这与 DirectX 设备如何管理以及 DirectX 的总体要求有关。我还看到过提到这是为了让 UI 线程存在于与位于客户端计算机上的渲染线程分离的服务器上。我想这在很多情况下都很有用。可以在 Google 搜索中找到更多信息，但信息似乎有限。

回到实际。WPF 的设计足够好，可以防止非 UI 线程访问 UI 元素。为了让非 UI 线程与 UI 线程中创建的元素交互，您必须对 UI 线程中的任何派生自 `DispatcherObject` 的类调用其 `Dispatcher` 属性的 `Invoke` 或 `BeginInvoke`。什么是派生自 `DispatcherObject` 的类？所有控件最终都通过 `DependencyObject` 派生自 `DispatcherObject`。许多其他类也最终继承自 `DispatcherObject`。UI 线程中的每个 `DispatcherObject` 都包含对同一个 `Dispatcher` 的引用，因此您可以对其中任何一个调用 `*Invoke`。但是，最好使用主窗口的 `Dispatcher` 属性。

调用 `*Invoke` 的要求类似于 .NET 2.0 中的 Windows Forms 编程。然而，在 WPF 中，正在发生的事情在语义上更清晰。在 .NET 2.0 中，您调用 `Control.*Invoke`，并且对架构的概念并不明确。在 WPF 中，您调用 `DispatcherObject.Dispatcher.*Invoke`，并且对架构的概念是明确的：存在一个 `Dispatcher`。

在螺旋井字棋中的应用

Negamax 搜索是一个耗时长的过程。如果它在 UI 线程的上下文中运行，UI 将在持续时间内无响应。这可能非常烦人。因此，这里我只需稍加想象，就找到了使用线程的理由。当 AI 需要执行移动时，会调用 `ExecuteAIMove` 函数。在这里，使用匿名委托来定义 Negamax 搜索进行的线程。在此线程中，另一个匿名委托定义了一个回调，该回调将在 UI 线程上调用。第二个匿名委托是内联定义在当前 `Dispatcher` 的 `BeginInvoke` 调用中的。如果匿名委托对您来说是新的，下面的代码乍一看可能会有点令人困惑。但是，我认为熟悉之后您会欣赏它的简洁性。替代方法需要为线程体定义一个单独的函数，为回调体定义第二个函数，并创建一个基于回调的委托传递给 `BeginInvoke` 函数。而不是将这类代码分散在应用程序中，而是将其包含在一个函数中。

private void ExecuteAIMove(bool sleep)
{
    //set menu items
    _start.IsEnabled = false;
    _prompt.IsEnabled = false;
    _undo.IsEnabled = false;

    _progressBar.Value = 0.0;

    Thread thread = new Thread(delegate()
    {
        if(sleep)
            Thread.Sleep(ANIMATION_TIME);

        SpiralAIMove move = _spiralAI.NegamaxSearch(_aiPiece, SEARCH_DEPTH);
        Dispatcher.BeginInvoke(DispatcherPriority.Normal,
            (DispatcherOperationCallback)delegate(object arg)
        {
            _spiralAI.ExecuteMove(move.Hub, move.Spoke, _aiPiece);
            return null;
        }, null);
    });

    thread.Start();
}

一旦您理解了以上段落，还有另一个需要注意的细节：进度条。请注意，在 Negamax 搜索执行期间，`SpiralAIProgress` 事件会由 `SpiralAI` 对象定期引发。此事件用于更新 UI 线程中的进度条。但是，Negamax 搜索是在非 UI 线程上执行的，因此 `SpiralAIProgress` 的处理程序也在非 UI 线程上执行。与上面类似，使用匿名委托作为回调，调用主窗口 `Dispatcher` 的 `BeginInvoke`。

private void SpiralAI_Progress(object sender, EventArgs e)
{
    Dispatcher.BeginInvoke(DispatcherPriority.Normal,
        (DispatcherOperationCallback)delegate(object arg)
    { 
        _progressBar.Value++;
        return null;
    }, null);
}

Negamax 搜索算法

广义上讲，在 AI 中有不同种类的代理，并且有一个称为搜索的子领域。代理具有传感器和执行器，并在各种环境中运行。有逻辑代理、决策理论代理和效用代理等。效用代理根据由某个评估函数确定的环境状态的效用分配进行操作。在螺旋井字棋的情况下，环境就是棋盘。对于棋盘的每个状态，都会相对于占用者分配一个效用值。评估是最需要创造力的地方。显然，获胜状态应分配最高可能的效用值。评估函数的其他方面则不那么明显。

螺旋井字棋效用代理通过棋盘的状态空间进行搜索。它根据希望在游戏中进一步发展的目标来确定其下一步移动，同时考虑竞争对手。Negamax 实际上是 Minimax 的一种更易于实现的变体，而 Minimax 本身在纸面上更容易理解。这样想：“如果我移到那里，他很可能会移到那里，如果我作为回应移到那里，他很可能会移到那里。所以，我想我最好移到这里。”如果搜索深度超过此，没有剪枝搜索树的情况下会花费太长时间。我实现的也是通用的 Negamax 搜索算法。如前所述，这可以用作探索 AI 搜索算法的良好起点。下一步将是实现 Alpha-Beta 剪枝。

历史

• 2007 年 7 月 31 日 -- 发布原始版本