Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions

nicholas.carlini.com

Post reply on HN
Print view View original

51–56 of 56 posts

Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions

#51

Post by Kaliboy »

bigdict wrote: post #6
Kaliboy wrote: post #5

This is amazing. I'm at loss for words. During my CS years I remember being fascinated by NFA's, as opposed to boring single universe DFA's. For some reason I internalized that I would never see something like an NFA implemented beyond text books. Then came Carlini.

But... they are equivalent?

Yeah I know, but I thought I was doing purely theoretical excercises.

And we always changed the regex NFA to an equivalent DFA and that was the implementation.

So somehow I managed to internalize the idea that an NFA is purely theoretical and can't be built.

Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions

#53

Post by zzazzdsa »

strenholme wrote: post #13

For people who are interested, here is the solution. In standard PGN, the solution is: 1. e4 e5 2. Nf3 Nf6 3. Nxe5 Nxe4 4. Qe2 Nxd2 5. Nc6+ Ne4 6. Nxd8 Kxd8 7. Qxe4 a6 8. Bg5+ Be7 9. Qxe7# In the Stockfish notation this engine uses, White’s moves are: 1. e2e4 2. g1f3 3. f3e5 4. d1e2 5. e5c6 6. c6d8 7. e2e4 8. c1g5 9. e4e7 Here is a Lichess analysis of this game: https://lichess.org/WnMF3LpX (In terms of Regexes, Java…

I won with 1. e4 e5 2. Qh5 a6 3.Bc4 a5 4. Qxf7#. I wonder if you could implement a stronger engine in regex (stockfish classic at O(1) nodes is plenty strong already)

Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions

#54

Post by casey2 »

devanshp wrote: post #9

This is absurd. I did not realize you could do nearly this much computation in regex.

This is an odd comment because it's a famously (imo) over known fact due to cs textbooks and how academia organizes knowledge, optimizing for pushing papers over genuine discovery.

Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions

#55

Post by deterministic »

zelphirkalt wrote: post #27

It would be different, if somehow all those 84688 regexes were coded by hand. Then it would be a piece of art. It would be different, if the number of regexes was maybe below 300, and it still plays acceptably. The sheer number of regexes kind of defeats the purpose. At that code size, a much better engine can be written, or other kind of code for an engine be generated. Regexes themselves are not really something we…

You completely missed the point of the article. It's the equivalent of compiling C++ to a Turing machine. Not practical, not optimum, but freaking amazing. Maybe think about it as an art project.
Post reply on HN