Which is the most recommended thread pattern for game AI and how to implement it?

I am new to threading in C# and despite reading much theory about threading it doesn't help me very much in practice.

I want to write AI function (minmax alphabeta) for a checkers game and execute it in a different thread.

There are 4 options for that: regular Tread, Thread Pool, Asynchronous delegate, BackgroundWorker.

BackgroundWorker seems to me ideal for this, it has delegate for finish so I can run the "makemove" function that will actually make the calculated move on the board and for updating progress bar.

I have 3 questions about this:

  1. Is BackgroundWorker really the best solution for this case?

  2. BackgroundWorker is executed in the Thread Pool, What are the benefits from that? It is always said that Thread Pool is good when you have many different threads, and this is not exactly my case.

  3. All the code examples that I saw were too simple and showed how to create just one such thread. In my program, I need to run this function every time it's the computer's turn, so I probably need to kill the previous thread and start a new one. What is the proper way to implement all this?

Any help would be appreciated.

Answers


1) Any and all of those solutions will work; you just have to use somewhat different logic to deal with each one.

2) ThreadPool is also useful when you have a set of things that can be executed on multiple threads (for example, in a Chinese Checkers game, you could run 5 different AI simulations via ThreadPool and it would run optimally on a computer that has two cores whereas using Threads would slow the process down due to context switching). It certainly works for your case - you'd just queue a second AIEvaluation or whatever and it would start executing ASAP.

3) Well, not really. The computer can't really make its move until after running alphabeta (presumably with some cutoff depth :P) so the AI thread would be done with its work anyhow. You could just use ThreadPool/BackgroundWorker each time.

Some general info about BackgroundWorker: it runs when you have "extra" CPU time, so if your main thread is hogging CPU for some reason, it won't do a whole lot. It may be better to use normal ThreadPool.

Let's say your program calls AIAct() when it's the AI's turn on the main thread. Also, let timerTick be a timer of the sort that exists in Windows Forms. Moreover, let there be the classes AIState and GameBoard that encapsulate the functionality needed for alpha-beta.

using System.Threading;

const int CUTOFF_DEPTH = 6;//Maximum plys for alpha-beta
AIState state;

void AIAct()
{
    state = new AIState( this.GameBoard.GetState() );
ThreadPool.QueueUserWorkItem(RunMinimax, state);

    //assume that timerTick is a Timer (Windows Forms Timer) that ticks every 100 ms
    timerTick.Enabled = true;
}

void timerTick_Tick(object sender, EventArgs e)
{
    if (state.IsComplete)
    {
        ExecuteAction(state.Result);
        timerTick.Enabled = false;
        //whatever else you need to do
    }
}

private static void RunMinimax(object args)
{
    AIState state = args as AIState;
    if (state == null)
    {
        //error handling of some sort
        Thread.CurrentThread.Abort();
    }

    //run your minimax function up to max depth of CUTOFF_DEPTH
    state.Result = Minimax( /* */ );
    state.IsComplete = true;
}

private class AIState
{
    public AIState(GameBoard board)
    {
        this.Board = board;
    }

    public readonly GameBoard Board;

    public AIAction Result;
    public volatile bool IsComplete;
}

Need Your Help

How to split an ItemCollection into 2 at a specified index?

c# .net wpf linq itemcollection

This seems like a very basic thing to do, but I can't find any methods to do this. I've checked Intellisense and searched Google with no luck.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.