Introduction
This article presents a WPF implementation of Negamax, an AI game search algorithm, in the context of a Spiral Tic-Tac-Toe game. The implementation of Negamax is vanilla and requires little explanation, but it does serve well as a fun way to get familiar with WPF. Rather than discussing the details of Negamax, this article discusses what needs to be done to reach the goal, which involves going over WPF threading as well as the use of DrawingVisuals. Additionally, there remain clear areas of improvement you may choose to explore. In order to reach a greater search depth, you can improve Negamax with a search tree pruning technique such as alpha-beta pruning. Alternatively, you can adapt the algorithm to a 3D tic-tac-toe game, which can serve as a good motivation for getting familiar with WPF 3D graphics.
General Structure
Thankfully, the application is uncluttered. There is a single window, along with a single FrameworkElement derived class that serves as the DrawingVisual surface. These are contained in the MainWindow.xaml and SpiralBoard.cs files, respectively. In addition to the two UI files, there is a SpiralAI class contained in SpiralAI.cs.
From the main window, you can bring up the Start New Game ... dialog through the Actions menu. The dialog allows you to choose your piece, circle or cross, and choose whether or not you want the AI to execute a move immediately following each of your moves. Additionally, the Actions menu has Prompt AI and Undo items. The Prompt AI menu item directs the AI to make a move when the auto move option is not selected. Under the menu is the Spiral Tic-Tac-Toe board put together using some trigonometry. Under the board is the progress bar provided by the System.Windows.Controls namespace.
The general structure of the application follows the Model View Controller design pattern. The SpiralBoard class together with the controls contained within MainWindow.xaml serves as the view, the code behind for the MainWindow class serves as the controller, and the SpiralAI class is the model. Within the code behind for the MainWindow class you can see that I have regioned off event handlers into view event handlers that operate on the model and model event handlers that operate on the view. From this, it is clear to see the lines of delineation between the components of the MVC pattern.
To see why the MVC pattern is helpful in this situation, consider that the SprialBoard and the SprialAI objects have to be kept in sync. That would mean that in response to the user executing a move the move would have to be executed on both the SpiralBoard and the SpiralAI objects in turn. To me, this seemed clunky. I felt that it would be a better separation of responsibilities to instead execute the move on the SpiralBoard object and have that fire off an event that would ultimately update the SpiralAI object serving as the model. To effect this separation, the SpiralBoard class raises a MoveRequestEvent routed event whenever you click on a valid spot to move. This event bubbles up to the main window and is handled there. Subsequently, once the move has been verified, the respective ExecuteMove methods of the SpiralAI and SpiralBoard objects are called.
Here is the code necessary for defining the MoveRequestEvent routed event in the SpiralBoard class.
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()
{
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); }
}
The MoveRequestEvent routed event is raised from the MouseLeftButtonUp event for SpiralBoard when it is determined that you have clicked on a valid position.
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;
}
}
}
}
Drawing Visuals and Deriving from FrameworkElement
There are 3 categories of things when it comes to WPF 2D graphics: Shapes, Drawings and Visuals. Shapes are derived from FrameworkElement and come with all the extra baggage provided by FrameworkElement such as input events, compositional support and layout functionality. For this reason, they are convenient as well as inefficient. If all you need is to draw a circle and have that circle participate in the layout process, in addition to being able to raise a MouseLeftButtonUp event, then you should use a Shape.
Drawings are more lightweight than Shapes since they derive from Animatable rather than FrameworkElement. However, they are not self-contained objects. Drawings have to be used in the context of something else beyond the simple requirement that everything happens within a window of some kind. For instance, you can use a Drawing as the source of a DrawingImage. Conversely, an ImageDrawing can draw an Image. That is a mouthful. Pay close attention and always regard the first word as the adjective modifier of the second. The second place that Drawings can be used is within the context of a DrawingVisual.
So what is DrawingVisual? DrawingVisual is derived from Visual, similar to FrameworkElement. However, DrawingVisual, rather than providing all of the functionality of FrameworkElement, primarily provides a means to obtain DrawingContext and draw something capable of being displayed in some host container. Of course, the host container will not be lightweight. The important thing is that the potentially hundreds of DrawingVisuals contained will be lightweight.
The RenderOpen method of DrawingVisual returns a reference to a DrawingContext object that can be used for performing draw operations. DrawingContext is similar to the Graphics class in GDI+ or the device context in GDI. The DrawingContext class contains methods for drawing primitives, in addition to methods for drawing the Drawing objects described above. A good example of DrawingVisual usage is in the DrawBoardVisual method shown below. Notice the importance of calling the Close method because DrawingContext utilizes unmanaged resources. Alternatively, a using construct can be employed to ensure proper clean-up.
private DrawingVisual DrawBoardVisual()
{
DrawingVisual visual = new DrawingVisual();
DrawingContext context = visual.RenderOpen();
context.DrawRectangle(Brushes.Transparent,
null, new Rect(0, 0, this.Width, this.Height));
context.PushTransform(new TranslateTransform(
this.Width / 2.0, this.Width / 2.0));
double diameter, decrement;
int hub, spoke, adjHub, adjSpoke;
double radius, radians;
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);
}
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();
...
}
The output of DrawingVisual needs to be shown within a host container. Deriving a class from FrameworkElement serves as a good option since it provides layout functionality within a window and also provides support for input events. In order to include DrawingVisuals within a FrameworkElement derived class, it is necessary to maintain a VisualCollection member that includes all of the DrawingVisuals for the element. In addition, it is necessary to override the VisualChildrenCount property and the GetVisualChild method as shown below.
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];
}
It is my hunch that VisualCollection is at the heart of how the retained-mode graphics layer operates. Controls, FrameworkElement, DrawingVisual and more all derive from the Visual class, which defines the VisualChildrenCount property and the GetVisualChild method. It can be seen how the visual tree for the application can be determined by examining the Visual children of the top level window and iterating recursively on the Visual children of its children. From this, the retained-mode graphics layer is made aware of what needs to be maintained for drawing to the screen.
Words on WPF Threading
Some sources claim WPF is so well-designed that it is unlikely you would ever need to use something as arcane as threads. Those sources do not make sense. It is important to understand WPF threading in order to understand WPF. If you are a professional programmer, you will benefit from understanding threading in whatever it is you are working with.
A WPF application consists of a UI thread and a render thread. The UI thread is associated with the first window created by the application instance. At the Win32 level, whenever a thread creates a window, a message queue is dynamically associated with the creating thread. The creating thread is then referred to more generally as a UI thread. This is not specific to WPF. The thread does not automatically begin pumping the message queue; that is something you have to do. In the case of WPF, an instance of the System.Windows.Threading.Dispatcher class is created and the Run method is called in order to initiate processing of the message queue. At some point, this Dispatcher instance is associated with the windows Dispatcher property. This association is made for all other DispatcherObject derived class elements within the application.
My understanding of the render thread is less certain. The render thread does not own a window or a message queue. It is responsible for the actual communication with DirectX in order to carry out the rendering. Threading conflicts with the UI thread do not exist, since it is the UI thread that controls the render thread. Why is the render thread a separate thread at all? My guess is that it has a lot to do with how the DirectX device is managed and the requirements of DirectX in general. I have also seen it mentioned that this was done in order for the UI thread to exist on a separate server from the render thread residing on a client machine. I guess this can be useful for any number of reasons. More information can be found in a Google search, but information appears limited.
Back to earth. WPF is designed well enough to prevent non-UI threads from accessing UI elements. In order to have a non-UI thread interact with elements created within the UI thread, you must call either Invoke or BeginInvoke on the Dispatcher property of any of the DispatcherObject derived classes within the UI thread. What is a DispatcherObject derived class? All controls are ultimately derived from DispatcherObject through DependencyObject. A bunch of other classes also ultimately inherit from DispatcherObject. Every DispatcherObject within the UI thread contains a reference to the same Dispatcher, so you can call *Invoke on any of them. However, it is probably in good taste to use the main windows Dispatcher property.
The requirement to call *Invoke is similar to .NET. 2.0 Windows Forms programming. However, in WPF it is more semantically clear what is happening. In .NET 2.0, you call Control.*Invoke and a notion of the architecture is not explicit. In WPF, you call DispatcherObject.Dispatcher.*Invoke and a notion of the architecture is explicit: there is a Dispatcher.
How it Applies to Spiral Tic-Tac-Toe
The Negamax search is a long-running process. If it were to run in the context of the UI thread the UI would be unresponsive for the duration. This can be quite annoying. So here, with very little imagination, I have found a reason to use threads. When it is time for the AI to execute a move the ExecuteAIMove function is called. Here, an anonymous delegate is used to define the thread in which the Negamax search takes places. From within this thread, another anonymous delegate defines a callback to be invoked on the UI thread. This second anonymous delegate is defined inline to the BeginInvoke call on the current Dispatcher. If anonymous delegates are new to you the code shown below may be a bit confusing at first sight. However, I think with familiarity will come an appreciation for the compactness. The alternative would require defining a separate function for the thread body, defining a second function for the body of the callback, and creating a delegate based on the callback to be passed to the BeginInvoke function. Instead of having that kind of code distributed across the application, it is contained within a single function.
private void ExecuteAIMove(bool sleep)
{
_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();
}
Once you are done understanding the above paragraph, there is one more caveat to take note of: the progress bar. Notice that during the execution of the Negamax search, the SpiralAIProgress event is raised by the SpiralAI object periodically. This event is used for updating the progress bar that exists in the UI thread. However, the Negamax search is executing on a non-UI thread and hence the handler for the SpiralAIProgress is also executed on a non-UI thread. Similar to the above, BeginInvoke on the Dispatcher of the main window is called using an anonymous delegate for the callback.
private void SpiralAI_Progress(object sender, EventArgs e)
{
Dispatcher.BeginInvoke(DispatcherPriority.Normal,
(DispatcherOperationCallback)delegate(object arg)
{
_progressBar.Value++;
return null;
}, null);
}
The Negamax Search Algorithm
Broadly speaking, in AI there are different kinds of agents and there is a subfield known simply as search. Agents have sensors and actuators and operate in various environments. There are logical agents, decision-theoretic agents and utility agents, among others. Utility agents operate based on utility assignments to states of the environment determined by some evaluation function. In the case of Spiral Tic-Tac-Toe, the environment is the board. To each state of the board, a utility value is assigned relative to an occupier. The evaluation is where creativity is needed the most. Obviously, a winning state should be assigned the highest utility value possible. The other aspects of the evaluation function are less obvious.
The Spiral Tic-Tac-Toe utility agent performs a search through the state space of the board. It determines its next moved based upon where it hopes to be further in the game, taking into consideration a competitor. Negamax is actually an easier-to-implement adaptation of Minimax, which in turn is easier to understand on paper. Think of it this way, "If I move there, he will most likely move there and if I move there in response, he will most likely move there. So, I guess I'd better move here." Searching at any greater depth than that takes too long in the absence of pruning the search tree. What I have implemented is the vanilla Negamax search algorithm. As previously stated, this can be used as a good launching point for exploring AI search algorithms yourself. The next step would be to implement alpha-beta pruning.
History
- 31 July, 2007 -- Original version posted
