|
|
|
|
|
|
|
|
We learn to write an application with XForms by simulating a game with 2 players and 2 actions.
by Thor Sigvaldason
Last month we began this series on XForms by explaining how to install the forms library and include file. We also took a stab at programming with XForms by writing a couple of simple programs. In this month's article, we're going to write a fully fledged application. We'll start with an explanation of the project, and then see how to implement it with XForms.
Our task is to implement a game theory simulator. If you don't happen to have a doctorate in mathematics, you might want to have a look at A Primer on Game Theory which appears on page 52 of this magazine. We're attacking a non-trivial programming task in order to get a handle on how to do ``real-world'' programming with XForms. It's not important that you understand every nuance of game theory, since our main goal is to figure out XForms.
In a formal game, there are two main entities we have to consider: players and payoffs. So our simulator should allow us to set relevant values for these elements. Players, for example, are defined by actions and strategies. Similarly, payoffs are just a set of values that players receive when they play the game. As a great simplifier, we'll assume there are only two types of players and only two possible actions. This reduces the dimensionality of our programming problem. A good exercise for readers would be to try and relax the two strategy limitation, but make sure you understand the initial program fairly well before trying to modify it.
Since we're creating a graphical application, we'll want a point-and-click interface for setting up our players. The method adopted is to think of players as having a finite number of states. In every state, there is an action to be taken. Since we've limited ourselves to just two possible actions, let's call these A and B. Our simulator will be used for repeated games, so we want to be able to design players who can change their actions. That is, move to another state which tells them to play a different action. There are only two types of players, Column Players and Row Players, and two actions, so the choice of which action to play can be affected only by what the other player did.
Let's say you want to design a player who always plays action A. That's simple; just set the action in each state to A. A more complicated example would be to design a player who plays A if the other player chose A last period, but B if the other player chose B. This is easier to see with a diagram:
Here we see that the transitions from state to state can be made contingent on the behavior of other players. So to implement an interface for designing players, we have to be able to specify the action in each state and the transitions to perform, i.e., which state to jump to, given the behavior of the other player. We cannot make one player's choices contingent on what the other player does in the current period. This would violate one of the tenets of standard game theory: simultaneous choice of action. Here we show only two states, but we'll allow for more complicated player strategies in the actual program.
We'll also want several players of each type to exist and to be randomly matched against players of the other type. This sounds more difficult than it is, since we still have to design only two types of players. The population of Row Players, for example, should differ only in what state they are currently in, not in the overall design of their strategy.
Like player design, we'll want an easy way for the user to set and edit payoffs. This is a little simpler, since we just need a graphical representation of the payoff table and a method for letting the user change these values. We'll want both of these features to appear in their own windows so we can pop them up when we need them.
Once the user has specified player strategies and payoffs, we'll also need a way to actually run the simulation. This routine should match the players, allocate their payoffs, and handle the transitions from state to state. It should also let us set how long the game should run, and give us some nice visual feedback on the progress of play.
All of this input, interaction and editing may seem very complicated. It would probably require a fairly cumbersome set of menus or a command language, if we were going to program this project on a simple terminal window. But with XForms, we can easily create windows, input fields and other graphical elements required to implement our game theory simulator. If this is all a little hazy, it may be a good idea to play with the running program a little (see below), and then come back to this section.
Let's just plunge right in. We'll get an example up and running right away, and then use the rest of this article to explain how it works. The program is called xgtsim and the C source code can be found in Listing 1.1 Although you're welcome to type it in, it's also available on the web site for this series (see http://a42.com/~thor/xforms, Listing 1). It should compile with the command:
gcc -lX11 -lforms -lm xgtsim.c -o xgtsimFrom within the X Window System, you should be able to run the program by typing ./xgtsim in an xterm window. If you have problems, you may want to go back and review last month's article on installing XForms. With all possible windows open, the running program should look something like Figure 2.
If you want to play around with the program before continuing with the rest of this article, one useful exercise would be to set up a prisoner's dilemma. Just use the payoff editor to set values the same as they appear in the primer, and then try some different player strategies. In particular, try and figure out what happens when two Tit-for-Tat strategies come up against each other. Does it matter what initial strategies they play?
Last month, we saw that the basic steps to designing an XForms program are as follows:
We use this approach in xgtsim. Like all C programs, execution begins in the main() routine, which is at the very end of the source code. First we call fl_initialize() to set up XForms, and allow it to parse command line arguments. Next, we call set_defaults() which seeds the random number generator, and sets some default values for our payoffs and player design variables: payoffs[][][], state_actions[][] and state_transitions[][][].
A call to create_forms() is then made, which sets up all of our windows, graphic elements and callbacks. We'll go into more detail shortly, but let's look at how this works for the simplest case: quitting the program. Within the create_forms() code, we use main_window (a variable of type FL_FORM) to create a window which will be shown when the program starts up. This window has four buttons on it, called Players, Payoffs, Run and Quit. Notice that the Quit button is set to call the function quit_xgtsim() with the command:
fl_set_object_callback(obj, quit_xgtsim, 1);This means whenever the mouse is clicked on the button labeled Quit, the quit routine will be called. This function, in turn, simply calls fl_finish() and then exits.
To return to the flow of the main() function, after setting up all of our windows, buttons and so on with create_forms(), we then make our main_window appear with a call to fl_show_form(). Then we turn control over to the user by calling fl_do_forms().
It's crucial to understand that setting up our forms in create_forms() does more than just decide how graphics should be laid out on the screen. By setting callbacks to link button pushes and data inputs with specific actions, we've actually set up the whole flow of the program. When the user pushes the Payoffs button, it is XForms (via fl_do_forms()) which calls the relevant routine to make the Payoffs window appear, and to handle subsequent interaction with that window. In fact, if we've set all our callbacks correctly, execution never returns to main(). The fl_do_forms() routine returns only if the user activates an object which does not have a callback associated with it.
Since create_forms() is so important, lets look at it in more detail. We use and re-use a generic pointer called *obj, which is of type FL_OBJECT, to create many of our graphical elements. This can be a little confusing, but we'll clarify things as we go.
The first form created in create_forms() is main_window. This is a global pointer variable which we declare early in the source code. We tell XForms it is a window which should be 290 pixels wide and 50 pixels high with the assignment:
main_window = fl_bgn_form(FL_NO_BOX, 290, 50);In the following nine lines of code, we create four buttons which will be used to pop up windows for user interaction and to quit the program. Each time we need a new graphical element, we just use obj, which saves memory and keeps things simple. Just remember that whenever we reassign obj, all subsequent functions passing obj as a value will affect the most recent assignment. The Players, Payoffs and Run buttons are all linked by a callback to a routine called display_forms(), but they are set to call that routine with the values 1, 2 and 3 respectively. The display_forms() routine, in turn, uses these values to decide which window to display. After creating the Quit button, we tell XForms we're done adding elements to this form by calling fl_end_form().
We then go on to create the player_window, payoff_window and run_window. These all follow the same general pattern; declare the dimensions of the window with fl_bgn_form(), add as many objects as we want (assigning callbacks as we go), and then finish with fl_end_form(). We'll look at the run_window in detail, since it's the simplest. Once you have it figured out, you'll probably want to look over the other two on your own.
Since we want visual feedback from the game, we create two charts in the run_window. We make these into line charts by specifying FL_LINE_CHART, and we set the dimensions by including 4 integer values. The first two values represent where the upper left corner of our chart should appear, with 0,0 being the very top left corner of the form the object is being created on. The next values describe the width and height of the object. Finally, we supply a string to give the chart a label:
column_chart = fl_add_chart(FL_LINE_CHART, 10, 30, 190, 90, "Column Players");You may be wondering why we assign this function call to a variable called column_chart instead of using our generic obj variable. This is done because column_chart is declared as a global variable, which is accessible to all the routines in xgtsim. In particular, when the game is actually being run, the play_the_game() routine uses this global variable to add values to the chart we just created--look for the function fl_add_chart_value().
With the label "Column Players" assigned to our chart, the default behavior is for it to appear below the chart. We move it to the top left corner with the call to fl_set_object_lalign(). Then we limit the number of items which can be displayed with fl_set_chart_maxnumb(). We then create an almost identical chart to display information about Row Players.
In addition to chart feedback, we create two browsers to display numerical data. This is accomplished with calls to fl_add_browser(). Browsers are very useful objects in XForms, and they can be used in many different ways. Our implementation here is very simple, but you can learn more about them in the XForms documentation.
To allow the user to set the number of iterations the game should run, we create a counter, and set lots of options. First we align the label to appear on the left, then set the precision to 0. This just means we want our counter to hold integer data, since you can't really perform half an iteration. A standard counter appears on the screen with two sets of arrows. Whenever they are pushed, they change the value of the numerical data the counter is holding. We set bounds on this data with a call to fl_set_counter_bounds(), and then make one set of buttons change the value by 1 and the other set change the value by 100 by setting the counter step rates. We also set the starting value in the counter to a default value (stored in numb_iterations), and then record a callback. Whenever the counter object is changed, the routine set_iterations() is called which sets the variable numb_iterations.
The run window also contains two buttons, one to start the game running and one to stop it. Notice that we create these two buttons in exactly the same place on the form, so that they are on top of each other. Before finishing, though, we hide the stop_button to ensure the go_button is visible. When the go_button is pushed, it calls play_the_game(), which hides the go_button and makes the stop_button appear. The ability to call fl_hide_object() and fl_show_object() makes form design in XForms very flexible, since you can design windows where objects appear and disappear according to any number of conditions. When an object is hidden, it is impossible for the user to activate it.
Once fl_end_form() is called, we are nearly done with this window. Immediately afterwards though, we call:
fl_set_form_atclose(run_window, close_forms, 0);This tells XForms what routine to run when the window manager sends the close window signal. On most window managers, this signal is sent when the user clicks on a close icon in the title bar of the window in question. This is like a callback, but the format is slightly different. In a normal callback, the declaration is of the form:
fl_set_object_callback(the_object, the_function, an_argument);The function pointed to by the_function must accept two arguments, an FL_OBJECT pointer and a long, as in:
the_function(FL_OBJECT *obj, long an_argument);This function must return void. When the window close signal is sent, however, it applies to an entire window/form, not a particular object on that form. So the first argument to fl_set_form_atclose() must be a pointer of type FL_FORM, as in:
close_forms(FL_FORM *form, void *an_argument);This function must return an integer, and in particular, it should return FL_OK if you want the window to actually close, and FL_IGNORE if you want the window to remain visible.
Having looked at main() and create_forms(), the rest of the source code is fairly easy to follow. The most complicated part is how the player_window uses the row_or_column variable to edit both types of players on a single form. The general idea is as follows. The global variables state_actions[][] and state_transitions[][][] hold all the data on the current state of both types of players, i.e., Column Players and Row Players. On the Player window, there are two buttons allowing the user to choose which type of player they want to edit. Whenever these are pushed, the Player window must be updated to reflect the state of these variables. This is done by the set_row_or_column() routine, which reads values from state_actions[][] and state_transitions[][][] into the relevant objects on the Player window, which are action_choices[] and transition_inputs[][].
With the window updated to reflect the current state of the relevant set of players, the user can now edit these values. This is accomplished via the set_player_values() function, which is called whenever any of these on-screen objects are changed. We do not bother trying to figure out which object is changed, but simply read all values on the Player window into state_actions[][] and state_transitions[][][].
The only remaining subtleties in the program are the use of the abort_flag variable and the call to fl_check_forms() in the iteration loop of play_the_game(). When the Go button is activated in the Run window, play_the_game() is called. One of the first things done in that routine is to set abort_flag to zero. Players are matched, payoffs made and the charts on the Run window are updated. At the bottom of the iteration loop, we check to see if abort_flag has been changed from 0 to 1, and if it has, we stop the run. You may be confused as to how this flag's value could have possibly changed within this algorithm.
The key lies in the call to fl_check_forms(). This is a non-blocking routine that works just like fl_do_forms(), except that it exits immediately if no objects were activated. This exacts a small performance penalty, since the program is effectively monitoring all its objects while the game is running, but it is well worth it. Since we set a callback to the Stop button to change abort_flag to one (via stop_the_game()), clicking on the Stop button will cause the current game to be aborted.
This has the added benefit of allowing us to modify all our data while the simulation is running. For example, we can alter payoff values and immediately see how this changes the unfolding game via the visual feedback in the Run window. Similarly, we can change player strategies on the fly, and watch how this affects their performance. This probing and runtime editing of parameters is often very difficult to achieve with standard C running on a console, but with a few global variables, a little sensible design and a call to fl_check_forms(), XForms makes it almost trivial.
If you've managed to pour over xgtsim and get a good feel for what's going on, you may want to try altering the source code to test your understanding. One thing to attempt would be adding an extra button to the Main window that randomizes all the current variables. That is, suppose the user has set payoffs and strategies, but wants to scramble these values. You'll not only have to add the button and set up the callback, but you'll have to update any currently displayed windows to reflect these changes.
The charts in the Run window currently provide only average feedback on the two types of players. Try adding more charts or other elements to display information on the best and worst players in each category.
If you're feeling really ambitious, then try altering xgtsim to allow for more actions and more complicated strategies. This can get very complicated, since elements like the payoff matrix will have to grow and shrink depending on how many actions are currently possible. This can be accomplished by dynamically creating new objects and forms, something we haven't covered so far.
In playing with xgtsim, you may find a set of strategies and payoffs that generate interesting results. Currently there's no way to save this state of the game, because we have no file-based input and output. We'll be adding that next month, by using XForms pre-built file requester routine. It's just part of a whole set of ``goodies'' that XForms includes, and we'll be looking at most of them.
We'll also spiff up our application with some pixmaps, learn how to set gravity parameters to control window resizing, and look at a few other interesting features of XForms.
Thor Sigvaldason is the author of the statistics program xldlas which uses the XForms library (see LJ #34, February, 1997). He is trying to finish a PhD in economics, and can be reached at thor@netcom.ca.
