Brilliant. The Chinese room thought experiment as a chess engine.
Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
21–30 of 56 posts
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#22Earlier quoted context omitted.
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
No, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization
And there are language families where minimal DFA is still exponentially large compared to NFA.
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#23Alternate title:
Compiling Python to a Branch-Free SIMD Virtual Machine via Extended Regular Expression String Rewriting
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#24Earlier quoted context omitted.
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.
Running NFA is O(nm) not NP.
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#25"Memory plus search is all you need"
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#26This is delightfully insane! I don't think I would say it doesn't play _entirely_ terrible though ;) It's playing really bad, but it could be worse and it's already super impressive that it can even generate legal moves.
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#27It 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 should strive to use more either. Maybe its intentional badness kind of makes it art?
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#28The technical write up is worth perusing but I played a game before reading and accidentally found a winning strategy immediately. I'm not sure if this is a result of the 2-ply nature of the engine or if the mentioned deficiencies account for this but the computer did not act to prevent checkmate in 1 (without any intervening check); the game I played was (in algebraic notation): 1. e4 e5 2. kf3 kf6 3. kxe5 kxe4 4. d…
Nitpick: In chess usually "N" is used to mean "knight", because "K" is already taken by "King".
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#29Earlier quoted context omitted.
Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.
Running NFA is O(nm) not NP.
Sorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.
Re: Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
#30[dead]