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

[download]
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

[download]
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

[download]
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]

[download]
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>

In reply to Playing connect4 with the regex engine by Fox

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.