Playing connect4 with the regex engine

[Fox]

Inspired by some other works on the same line, I made the regex engine play Connect Four.

The regexes don't do the work all by itself, although it spend most of it's time matching, it uses the negascout algorithm to transverse the game tree.

To evaluate the game state, I store the board as a string:

my $table = <<EOT
0000000
0000000
0000000
0000000
0001000
0002000
0021000
EOT

Then, to check if anyone won, for example:

$table =~/(?|
          (?: ([12]) (?=      \1      \1      \1) ) | # (1)
          (?: ([12]) (?= .{7} \1 .{7} \1 .{7} \1) ) | # (2)
          (?: ([12]) (?= .{6} \1 .{6} \1 .{6} \1) ) | # (3)
          (?: ([12]) (?= .{8} \1 .{8} \1 .{8} \1) )   # (4)
          )/xs

It will first match 1|2 (1 and 2 are the players stones), and then look ahead for either horizontal match (1) or 3 stones vertically under it (2), or in either diagonals (3) and (4). If match, the winner will be in $1.

Adding a stone on the table is a s/// operation:

       $table =~ s/^ .{4} (?: .{7} . )* \K 0/1/xs

Will add a '1' stone on the (zero-based) column 4. Match fails if column is full.

Finally, the meat of the script is the table evaluation, which is a auto-generated version of the win pattern, except instead of matching 4 equal stones, it matches all imperfect combinations and attribute points depending on how good is the combination (See the setup() sub).


You can run the script like this:

   ./c4player [--depth=9] [--width=7] [--height=7] [--cpu=1]

I choosed the 7x7 board because it has been proven you can't force a win but the script will accept any reasonable dimension.

Overall, the script turned out to be faster than I had thought, spending between 1 ~ 10 seconds to make a move at depth 9, although it's still 1 or 2 orders of magnitude slower than a "vanilla" C implementation.

Looking forward to hear how can I make this faster ;)

<Reveal this spoiler or all in this thread>