minimax connect-four player

Just quickly modified my minimax tic-tac-toe into minimax connect-four. Had the following bug which took a while to track down

#define COORD(x,y) (x+COLS*y)

// then using COORD(x,y+1) is an error
// the fix is

#define COORD(x,y) ((x)+COLS*(y))

since C macros act textually rather than syntactically.

I had to put a depth limiter on the minimax code since it's trying to solve the game perfectly before playing a single move - but with the alpha-beta optimization (which is what I'll do next) it should play the same moves as a perfect player in a short enough time to be feasible.

tic tac toe player complete

So I did finish getting minimax based tic-tac-toe AI to work just now:

There was a fair bit of debugging (for example I had min and max mixed up because I thought color 1 corresponded to white, when it actually corresponded to black), I think I will need to design and name parts of the code more carefully before writing them out to avoid this repeating and becoming a big problem later on.

The next step is to upgrade this to a connect-4 game with AI because then I'll need to be using alpha-beta pruning, since its search space (while still very small) is too big for minimax to work. It will also be a useful step so that I can redesign the code into something more flexible and clear.

hotseat game working

I coded win detection so that you can now play a hotseat game of gomoku with yourself. At first I wrote this:

int detect_win_including_position(int color, int x, int y) {
  if(span_in_direction(color, x, y, 1, 0)+span_in_direction(color, x, y, -1, 0) >= 5) return 1;
  if(span_in_direction(color, x, y, 1, 1)+span_in_direction(color, x, y, -1, -1) >= 5) return 1;
  if(span_in_direction(color, x, y, 0, 1)+span_in_direction(color, x, y, 0, -1) >= 5) return 1;
  if(span_in_direction(color, x, y, -1, 1)+span_in_direction(color, x, y, 1, -1) >= 5) return 1;
  return 0;
}

int span_in_direction(int color, int x, int y, int dx, int dy) {
  int length;
  
  length = 0;
  while(x >= 0 && y >= 0 && x < 15 && y < 15 && board[COORD(x,y)]==color) {
    length++;
    x+=dx;
    y+=dy;
  }
  return length;
} 

but there is a bug in that.. fixed now.

A slightly annoying thing is that when you start there are no counters so the buttons are all small, then you click and all the buttons grow in size. I can't be bothered to fix it (I suppose I should add transparent images to the buttons to fix it).

I have been thinking a bit about evaluation functions and tabulation/memoization (in gomoku only board position matters, not the order of moves - so redundancy when searching the tree could blow up the search times) but it's probably too early to be thinking about these things.

I thought a good warmup would be start with minimax to write a knots-and-crosses AI, then write a connect-4 AI using simple alpha-beta then start to tackle gomoku directly. It's really boring to write the knots-and-crosses but it's a good idea to build up step by step.

some GUI stuff working

Just put the following together using the started code and the GTK tutorials, just a grid of buttons with random counters on them - when you click it prints the coordinates for that button. Seems like a good start, next I should get it to let you play a hotseat game of gomoku, then I can think about making player two choose its moves from an AI (and probably as a warm-up use minimax on 3x3 version, and maybe do a quick connect-4 game too - since that takes much smaller search space).

1. https://developer.gnome.org/gtk-tutorial/2.90/

got some gtk starter code from github

First I thought I would edit Simon Tatham's Portable Puzzle Collection but there are so many lines of code in there I don't want to get involved in it. So I found a tic-tac-toe implementation in github which can be compiled with

gcc `pkg-config --cflags --libs gtk+-3.0` main.c

it just uses labeled buttons instead of nice graphics so next I'll make it use pictures on the buttons instead of labels.

1. http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ 
2. https://github.com/niyasc/tic-tac-toe

gomoku ai project

Gomoku AI Project

I want to create a basic AI for the game gomoku/5-in-a-row (simple version). I'll use this blog for taking notes on the progress. You can play it against people on miniclip, it looks like this:

I don't think it should be so difficult to create a simple AI that is better at this game than me, which only takes a few seconds to calculate its moves on my computer. I'm not sure if I will program it in scheme (so that it's easier to write the code) or C (so that I don't have any worries about speed problems being caused by a languages runtime). I think I will use C so that I can manually handle the allocation of boards.
From reading AIMA, I think alpha-beta pruning should work so I'll try that - but first I think I will make a knots-and-crosses/3-in-a-row AI (so that I get the basic stuff like the tools and implementing an interactive board out of the way).