Thursday, August 20, 2015

Conway's Game Of Life - C#

I love Conway's Game Of Life, a fact that I can't deny. I implemented several rather unsophisticated simulators in various programming languages: MOS 6502 assembly, C64 BASIC, Apple Soft BASIC, C, C#. Today I'd like to write about my C# port.

Back in 2004 I started to learn C# and .NET. This process spawned several programming projects. The first was Game Of Life simulator. I recently brought that project back from hibernation. I originally developed the program under SharpDevelop IDE. That IDE is still being developed and supported. I downloaded the newest version 5 and Microsoft's .NET developer's pack for version 4.5 of .NET. I fixed few bugs and made some improvements and I built a new version. It performs nicely. It is so good to watch those colonies evolve again. There is something hypnotic about watching a running GOL colony simulation, any nerd can confirm that.

Anyway, few words about the game:

It was invented by mathematician John Horton Conway in 1970. It is a game that plays itself, since this is a cellular automaton, the evolution of the game is determined by initial state and the rules that govern the creation of subsequent generations of the colony created in each time tick.
The universe of a game is a 2-dimensional grid of cells which can be in 2 possible states: dead or alive. Each cell interacts with 8 adjacent neighbors and depending on the number of alive neighbors, the state of the cell may or may not change in the next generation.

The following rules govern the next state of the cell:

  • Each alive cell that has one or no alive neighbors will die from loneliness.
  • Each alive cell that has two or three alive neighbors will remain alive.
  • In each empty (dead) cell with exactly 3 neighbors will change the state to alive (reproduction).
  • Each alive cell with 4 or more neighbors will die from overcrowding.

My program allows to save the colony in disk file and load one from file. I developed my own colony file plain text format so for now unfortunately you can not download and use directly any popular on the internet colonies in common formats like 'plaintext' or RLE. This is something that you esteemed reader can perhaps do on your own if you are not afraid of doing some programming (write your own converter or alter my program) or you may need to wait until I add this feature in the future version.
Program lets the user to edit the colony by clicking on the colony view area directly. Click on the cell to flip its state. Clicking on the colony view area automatically stops the simulation which can be restarted after modifications are complete. Saving the colony before running simulation is recommended.

Other features include:

  • Individual colony properties/setup file.
  • Zoom range 1-20.
  • Optional painting of the grid lines (slow).
  • Optional painting the dying cells (slow).
  • Possibility of changing the colony size.
  • Random colony generator.
  • Initial population number limit.
  • Single step mode.

In future versions I plan to improve GUI. I will also add support for one or more of the popular GOL colony file formats. Performance also may need some optimization, if I ever want to increase the maximum size of the colony or perhaps implement a dynamically extendable colony size, which may require some more advanced programming techniques to maintain proper rendering speed for huge colonies.

Download here ( and enjoy.
(The most current version as of 10/14/2015 is -



Marek K

Wednesday, August 19, 2015

Game of Tic-Tac-Toe.

It would probably be difficult to find anybody that has never played a classic 3x3 Tic-Tac-Toe game. I remember that at school it was one of the time killing methods during boring activities we were made to attend. We played many different variants of the game, mostly going beyond the 3x3 boundaries (we played often 5x5 variant or until the space was available on the piece of paper). Anyway, while experimenting on my C-128 with CP/M system and Aztec C compiler, I thought that Tic-Tac-Toe would be a good project for a game running in such environment as it requires no graphics, text mode being sufficient for presentation and player input. Well, I started the development on that platform, however the cycles of code changing/compiling/testing took awfully long time (due to CP/M and compiler slowness on C-128), therefore I decided to move the development to a modern computer. This proved a fun casual programming project, the goal was to create an unbeatable computer AI playing classic 3x3 Tic-Tac-Toe game.

The game rules:

Players play on a 3x3 square board:

 In the empty spaces of the board, using pencils on a paper (or a computer generated board) players put their symbols taking turns. One player plays with 'O' (circle) and another with 'X' - cross. In my version if human player selects 'O' symbol, he/she begins the game. Otherwise, computer AI performs the first move. It does not matter which symbol really starts the game, but we must establish some laws. A different approach could be to select the 1-st player randomly and this would also be fine.
The goal of the game is to win by putting the player's 3 symbols in a row in any horizontal, vertical or diagonal line. This game, if both players make no mistakes and play with proper tactic, can not be lost or won and shall always end-up in a tie.
For the benefit of this article and explanation of the algorithm, I will name the board columns A, B C and rows 1, 2 and 3. The corner spots are A1, A3, C1, C3. The edge spots are B1, A2, C2 and B3. The center spot is B2.

Because the development started on a limited in resources platform (CP/M OS, 8-bit hardware), I established some development directives to prevent the system running out of resources playing such a simple game, which would make the programmer look rather lame.

The rules are:

  • Do not use recursion (stack limitations).
  • Use as few local function variables as possible (stack limitations).
  • Game works in text mode (CP/M limitation) in a scroll-down fashion (not using potentially incompatible terminal control characters, aimed for portability here).

When approaching such problem from programming perspective I always use top-down programming method. I write main() function first and invoke whatever functions I might need, implemented or not, inventing them along the way. Later I proceed to implement the rest of the needed functions using exactly the same method. I repeat the process until all the required functions are implemented. Then it is time to make the code to compile/link properly. At this point the process of debugging starts which consists of the cycles of testing/debugging/correcting code until the program is up to my expectations and bugs free.

As with any game, we should start with the main program loop, which basically consists of initialization function, presentation function, user input function, game logic function and game-end test.

In pseudo-code, we might end-up with something like this:

repeat until game_not_ended
   if game_ended
      if play_again
   if game_ended
      if play_again

The C implementation may look similar to this:

    int n;


    do {
       n = end_game();
       if (0 == n) {
          n = end_game();
       if (1 == n) {
    } while(0 == n || 1 == n);

This part of course is not too difficult, even for a beginner. The devil is in details, as they say. The first two of the development directives that I made before imply that the game logic should be based on a simple heuristic evaluation. Computer should perform analysis of all possible moves in the next turn, assign the score to each possibility and then pick the best move based on this evaluation. That function is comp_move(), 

Before implementation, I needed to design a clear strategy based on the experience of playing the game and on game rules. The strategy I assumed is as follows (remember that computer will be only looking one move ahead and base its decision on existing game state):

  • The top most important directive is to prevent other player from winning.
  • Next priority is to favor the center spot, if not yet taken, make the move there.
  • If none of the above conditions occurred, then if the human player already occupies two opposite corners but remaining corners are free, make move to any edge spot.
       This hypothetical situation occurs when player has symbols in spots 
       A1, C3  and spots A3, C1 are free OR the opposite/symmetrical (player:
       A3, C1, free: A1, C3). 

       See graphical representation below:


  • If the player symbol occupies an edge and one of the corners on the opposite side of the board, the preferred position is a corner spot next to the player occupied edge spot and opposite to the player occupied corner spot.
       The above pattern occurs if player has one of A1, A3 combined with 
       C2 OR one of C1, C3 combined with A2 OR one of A1, C1 combined with 
       B3 OR one of A3, C3 combined with B1.

       See graphical representation below:


  • If player played a corner, also play a corner.
  • If player symbol occupies 2 adjacent edge spots, take a corner between them.
  • if player played an edge, also play an edge.

Above tactics are applied in the order as listed, from top to bottom.
Below is the code if my implementation:

 * A computer move routine (AI).
 * Looks unbeatable :-) (needs more testing).
   int i, j, k, l, m, n;

   k = l = -1; /* indexes of computer move */
   m = n = 0;  /* game evaluation results/scores for computer and player */

   /* evaluate heuristically each possible next move for player and computer */
   /* i - column index, j - row index */
   for (i=0; i<3; i++) {
      for (j=0; j<3; j++) {
         if (' ' == board[i][j]) {
            board[i][j] = plr_sym; /* simulate player's move */
            /* if player's move would result in winning, give this position */
            /* highest score to prevent human player from winning */
            if (cmc > 0 && n < 100 && 1 == game_done()) {
                n = 100; k = i;    l = j;
            } /* next - favor the center spot */
            else if (n < 50 && i == 1 && j == 1) {
                n = 50;    k = l = 1;
            } /* next - if human player occupies two opposite corners */
                          /* and remaining corners are free, prefer edge spot */
            else if (cmc > 0 && n < 25 && abs(j-i) == 1 &&
                       ((board[0][0] == plr_sym && board[2][2] == plr_sym
                               && board[0][2] == ' ' && board[2][0] == ' ')
                       || (board[2][0] == plr_sym && board[0][2] == plr_sym
                              && board[0][0] == ' ' && board[2][2] == ' '))) {
                n = 25;    k = i; l = j;
            } /* next - if player has a corner and edge on opposite sides */
              /* take the corner spot next to the player's edge piece */
            else if (cmc > 0 && n < 20 && abs(j-i) == 2
                               && board[i][1] == plr_sym
                              && ((i == 2 && (board[0][0] == plr_sym
                                 || board[0][2] == plr_sym))
                                 || (i == 0 && (board[2][0] == plr_sym)
                                 || board[2][2] == plr_sym))) {
                n = 20; k = i; l = j;
            } /* next - similar but simmetrical situation */
            else if (cmc > 0 && n < 20 && abs(j-i) == 2
                                   && board[1][j] == plr_sym
                                   && ((j == 2 && (board[0][0] == plr_sym
                                   || board[2][0] == plr_sym))
                                   || (j == 0 && (board[0][2] == plr_sym)
                                   || board[2][2] == plr_sym))) {
                n = 20; k = i; l = j;
            /* next - prefer corner spots if this is not the 1-st move */
            /* and player also played corner */
            else if (cmc != 0 && n < 12 && i != 1 && j != 1 && plr_nm_col != 1
                                         && plr_nm_row !=1) {
                n = 12; k = i; l = j;
            } /* next - if player occupies 2 adjacent edge spots and */
              /* the remaining edge spots are free, take corner between them */
            else if (cmc > 0 && n < 6 && i != 1 && j != 1
                         && board[i][1] == plr_sym && board[1][j] == plr_sym) {
                n = 6; k = i; l = j;
            } /* next - prefer edge spots if this is not 1-st move and */
              /* player also played edge */
            else if (cmc != 0 && n < 3 && abs(j-i) == 1
                               && abs(plr_nm_col-plr_nm_row) == 1) {
                n = 3; k = i; l = j;
            board[i][j] = comp_sym; /* simulate computer move */
            m = eval_game(comp_sym); /* evaluate the current game */
            /* if computer move gets higher score than player move and other */
            /* preferred strategies then take precedence and assign new */
            /* computer move to current location [i,j] */
            if (m > n) {
                n = m; k = i; l = j;
            board[i][j] = ' '; /* restore board to previous state */
   /* if move indexes were assigned, perform this move */
   if (0 <= k) {
        cmc++; mvc++;
       board[k][l] = comp_sym;
       printf("Computer move: %c%d\n", (char)('A'+k), l+1);

There is not much more to say about this simple game.
Download from here and enjoy not winning it ever :-)
Game runs in text mode (DOS) and should work under any modern version of windows system.
The program is written in C and is highly portable and will compile on Windows, Linux, AIX and even under CP/M 3.0 (Aztec C).


Marek K