Posts Tagged ‘minimax algorithm’

I’ve published an Android board game, Wufu (五福), which I played pretty often when I was a child.

I use the minimax algorithm with alpha beta pruning to implement the game engine. It’s pretty straightforward to implement the algorithm. The difficult part is how to sort the legal moves so that evaluate the best moves first, and how to fine-tune the evaluation function.

Computing a move may take a long time, so the computation should be done by a background thread. I wrote a sub-class of AsyncTask to perform the computation. The normal usage of AsyncTask is that you perform the lengthy task in the doInBackground() method and pass the result to the activity in the onPostExecute() method. The tricky thing of using AsyncTask is that when the onPostExecute() method is called the activity may get destroyed because of, e.g. the change of the phone orientation. Your application will crash if you call a method on the destroyed activity.

I solved this problem by using a mid-man, a custom Application object, between the AsyncTask and the activity. The activity registers itself to the concrete Application object in onResume() and unregisters in onPause(). When the lengthy computation is done, in other words, when the onPostExecute() method of the concrete AsyncTask is called, we call a method on the Application object, which will call a method on the activity directly if one is currently registered, otherwise, we store the computed result somewhere in the Application object. Each time the onResume() method of the activity is called, it checks if there is an stored computation result in the Application object.

Another thing is the simulation of a player removing multiple pieces from the board. You want to remove the pieces one by one so that it is easier for the player knows which pieces are removed. I used a Handler and wrote a class, MoveAnimator, that implements the Runnable interface. MoveAnimator maintains a small state machine has the states, Waiting, Running, Paused, and Done, with Waiting as the initial state. When the play() method of MoveAnimator is called, it sets the state to Running and calls the following two methods:

m_handler.postDelayed(this, INTERVAL); // Add MoveAnimator to the message queue.

Note that m_handler is an instance of android.os.Handler.

In the run() method of MoveAnimator, if the state is Running and it is not done, then we get next move and animate it. If there are still remaining moves, we call the postDelayed() method on the Handler to add the MoveAnimator to the message queue.

m_handler.postDelayed(this, INTERVAL);

The onPause() method of MoveAnimator is called to change the current state to Paused when the onPause() method of the Activity is called. Similarly, the onResume() method of MoveAnimator is called to change the current state to Running when the onResume() method of the Activity is called. That way, the animation can continue even after the phone orientation is changed.


Read Full Post »