Learning by Doing: Programming Razz Simulator

Posted in kerneltrap.org on February 5, 2010 – 9:54am

As a final assignment in my Languages for Scientific Computing class, I develop a Razz Simulator. Basically Razz is the inverse of Poker in which you try to come up with the worst hand as described here. The game is well explained in the slide for the first and second lectures and in the sixth assignment found here. The first problem on Razz was at the end of the first assignment: given A, 2 and 3 to start with, what is the probability of getting a hand with rank exactly 7? Well, no one answered that correctly until the professor showed an elaborate calculation in Mathematica that resulted in 0.143008. One important message is that people don’t do such an elaborate calculation in reality. Rather they use a simulation (i.e., play as many Razz games as possible with the given starting cards and count the number of times you score 7). So, the last assignment is about developing the simulator that can simulates as many games as possible in the shortest time possible. The most interesting thing about the assignment is that the program is neat enough to show some interesting software engineering principles in action beside telling you that Razz is not as simple as it seems to be.

I start developing my program by having two classes: Card and Razz. Card serves as the infrastructure of dealing with card shuffling, card dealing, a hand of cards and the like. It is interesting to see that I employ opaque objects in the API of Card. For example, instead of using struct card, I use typedef struct card_impl card to hide the actual data structure. Well, as can be seen in the Linux development, typedef is frowned upon. But, it is okay if you know what you are doing because the use of the opaque object trully enables me to do quick optimization effort without major restructurization because Razz really should know nothing about how Card works. Razz uses Card to perform the simulation of Razz games and come up with the probability. The first milestone for the development is when the simulation comes up with the right probability for solving the first Razz problem given at the end of the first assignment: 0.1431. The simulation could simulate 1M games in about 45 seconds when compiled with the highest optimization level of GCC. You should see the content of card.c and see the implementation of the opaque data structures that will soon change, especially data structure for the card deck.

The next natural step is to make it faster. I do it by changing heavily the way card deck works. Does it take a lot of effort? Not at all as you can see in this commit. Only one file is affected while the other file is just for additional test cases. But, how much gain can you get by doing so? After the restructurization, compiled with the highest optimization level of GCC, the simulation could simulate 1M games in about 3 seconds. That is a gain of 93.33% with so little effort. Now you can see how opaque data structure can help much if it is used correctly.

Oh, talking about test cases, I assure you that it is very important to have them. But, you have to get the right understanding: Test cases are there not to ensure the correctness of your program but to raise your confidence level. That means that you should not test for all possible inputs. And, you should not test by looking at how you implement the program. Just test for some risky inputs and that’s it. If later you encounter a bug, add the bug as an additional test case. The bottom line is that if you keep maintaining your test cases fresh, you will have a better life since you are more confident that your program will work well most of the time. Previously I made a mistake by trying to ensure the correctness of my program through testing. I ended up being stressed out with an overwhelming number of test cases that I had to write. That’s just not the way TDD (Test-driven Development) should work. To conclude, you have test cases because you want to be more confident about your program.

In short, I have shown you the benefit of opaque data objects as well as how to use test cases properly. I will add further stories as I go along with the program.

Advertisements
This entry was posted in C, Learning Experience, Programming Languages, Software Engineering and tagged . Bookmark the permalink.

One Response to Learning by Doing: Programming Razz Simulator

  1. Eus says:

    Thing to remember when using an iterator
    Posted by Eus on February 6, 2010 – 5:21am

    When iterating a collection, you have to keep in mind that you should not iterate the collection with another non-read-only iterator under the current iterator because in effect it is just like spawning multiple thread of executions sharing the same data object (i.e., the collection) and all bad stuff may happen if the sub-iterator is not read-only. The following illustrates the problem:

    int main()
    {
    	Collection *c; // a double link-list implementation
    
    	c = get_processed_measurement_data ();
    	refine_data (c);
    
    	return 0;
    }
    
    /* No problem with this one */
    Entry *get_next (Entry *curr_entry)
    {
    	return curr_entry->next;
    }
    
    /* The sub-iterator that will cause the problem */
    void delete_all_similar_entries (Collection *c, Status s)
    {
    	Entry *itr = c->head;
    
    	if (itr == NULL)
    		return;
    
    	do
    	{
    		if (itr->status == s)
    		{
    			Entry *removed;
    
    			itr->next->prev = itr->prev;
    			itr->prev->next = itr->next;
    
    			removed = itr;
    			itr = get_next (itr);
    
    			/* This will cause a trouble to the main iterator */
    			free (removed);
    		}
    		else
    		{
    			itr = get_next (itr);
    		}
    	}
    	while (itr != c->head);
    }
    
    /* The main iterator */
    int refine_data (Collection *c)
    {
    	Entry *itr = c->head;
    
    	if (itr == NULL)
    		return;
    
    	do
    	{
    		if (itr->measurement head);
    }
    

    The above problem is the main motivation behind this.

    Beside that, deleting an iterated element should be done with care since you definitely have to adjust the head pointer if you happen to delete an entry under the pointer as illustrated below:

    /* No problem with this one */
    Entry *get_next (Entry *curr_entry)
    {
    	return curr_entry->next;
    }
    
    /* The iterator that will cause the problem */
    void delete_all_similar_entries (Collection *c, Status s)
    {
    	Entry *itr = c->head; // the head's status is STATUS_B
    
    	if (itr == NULL)
    		return;
    
    	do
    	{
    		if (itr->status == s)
    		{
    			Entry *removed;
    
    			itr->next->prev = itr->prev;
    			itr->prev->next = itr->next;
    
    			removed = itr;
    			itr = get_next (itr);
    
    			/* The trouble maker: the address pointed by the
    			 * collection's head is no longer valid although
    			 * the iteration will still work fine.
    			 */
    			free (removed);
    		}
    		else
    		{
    			itr = get_next (itr);
    		}
    	}
    	while (itr != c->head);
    }
    
    int main()
    {
    	Collection *c; // a double link-list implementation
    
    	delete_all_similar_entries (c, STATUS_B);
    
    	/* Get a problem here since head is not adjusted */
    	c->head->is_iterated = TRUE;
    
    	return 0;
    }
    

    To conclude, when iterating a collection (e.g., a link list or a tree), no non-read-only sub-iterator should be spawned. Moreover, care should be taken to adjust the head/root pointer of the whole collection when the entry under the pointer is deleted.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s