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

A minimax chess engine in regular expressions

nicholas.carlini.com

Post reply on HN
Print view View original

71–80 of 103 posts

Re: A minimax chess engine in regular expressions

#71

Post by klibertp »

jamster02 wrote: post #6
proteal wrote: post #3

“Now comes the clever part.” God bless our soldiers who see that regex is turing complete and choose to implement fun programs. Yall are truly a different breed :)

Regex isn't (necessarily) turing complete :) > Because our program just consists of a sequence of regular expressions, you can't loop at all! That, technically, means we can't actually perform Turing Complete But we can do any bounded computation by just unrolling any loops we may have. Although some (most?) implementations may be. Though by the above quote, the author didn't make use of that.

That's the point, I think: for a large number of real-world algorithms, you don't actually need a Turing Machine. There was a very well-written explanation of this on the front page[1] some time ago, concluded with:

> Any algorithm that can be implemented by a Turing Machine such that its runtime is bounded by some primitive recursive function of input can also be implemented by a primitive recursive function!

Also, "The Little Typer" book explores a language based on "primitive recursive functions" and shows what can be done in it and how.

[1] https://matklad.github.io/2024/08/01/primitive-recursive-fun...

Re: A minimax chess engine in regular expressions

#72

Post by klibertp »

kookamamie wrote: post #61
basementcat wrote: post #2

This is from the same gentleman who (among other things) demonstrated that printf() is Turing complete and wrote a first person shooter in 13kB of Javascript. https://github.com/HexHive/printbf https://github.com/carlini/js13k2019-yet-another-doom-clone

> a first person shooter in 13kB of Javascript I was somewhat disappointed to realize they used WebGL for rendering the graphics.

There was an earlier version of the underlying 3d engine that used only Canvas. WebGL use is justified like this:

> Once I actually got that working doing all of the math by hand in JavaScript I decided that using WebGL would probably be worth it, and actually probably wasn't cheating all that much. WebGL exposes access to the GPU-enabled rendering engine through JavaScript. While it does abstract away some of the rendering, it's less than I thought---it just supports the ability to do the necessary math efficiently---so I decided this wouldn't be cheating. And fortunately, it didn't take long to reproduce the initial renderer, but this time supporting much better (and more efficient) graphics.

From: https://nicholas.carlini.com/writing/2019/3d-renderer-javasc...

Re: A minimax chess engine in regular expressions

#75

Post by [deleted] »

PaulHoule wrote: post #66
larodi wrote: post #49

Earlier quoted context omitted.

Apparently it takes more than skill but also persistence and concentration. Not many schools of thought explain this well .

No, it takes (1) knowing what you learn in a compilers class (or upper level math classes) and (2) putting it to work. He didn't write 80,000 regular expressions, he wrote a compiler that wrote those expressions. Commercial-quality compilers are hard to write but simple compilers are straightforward if you know the fundamentals. It's like the problem of solving the Rubik's cube. If you look at it in terms of geometry…

[deleted]

Re: A minimax chess engine in regular expressions

#77

Post by Ensorceled »

philipwhiuk wrote: post #62
rhdjebejdbd wrote: post #50

Earlier quoted context omitted.

Maybe a generous interpretation of the comment and a realisation that common language isn't always 100% precise would be better than pointless arguments about semantics. There is only a single printf written in the source code.

I don't think it's an unreasonable criticism, otherwise the challenge is trivial: ``` function printg(arg) { printf(arg); } ```

That, of course, isn't what they did.

Re: A minimax chess engine in regular expressions

#78

Post by 3willows »

PaulHoule wrote: post #66
larodi wrote: post #49

Earlier quoted context omitted.

Apparently it takes more than skill but also persistence and concentration. Not many schools of thought explain this well .

No, it takes (1) knowing what you learn in a compilers class (or upper level math classes) and (2) putting it to work. He didn't write 80,000 regular expressions, he wrote a compiler that wrote those expressions. Commercial-quality compilers are hard to write but simple compilers are straightforward if you know the fundamentals. It's like the problem of solving the Rubik's cube. If you look at it in terms of geometry…

Agree. The whole point of the article is to generate the long list of regex programmatically.

A quick way to verify this is to download the repo, remove everything other than main.py and regex-chess.json, and the programme will still work.

All the other python files are building up to regex-chess.json, see e.g. the imports and output to write_regex_json.py.

Re: A minimax chess engine in regular expressions

#80

Post by desireco42 »

I love the author's philosophy of doing 'entirely pointless things' for the joy of learning. This project reminds me why I got into programming in the first place - not just to solve practical problems, but to explore the weird and wonderful possibilities of code. The fact that this works at all is just mind-blowing!
Post reply on HN