Re: Chess engine in braifuck
Yes, minimax algorithm is the desired AI design to consider.odomobo wrote: ↑Tue Mar 05, 2019 1:45 amDo you plan on using a minimax algorithm, a heuristic-based move selector, or simply a random move generator?
I'd recommend using a much simpler game as a proof-of-concept. Even if you do eventually implement chess, you might want to use a simple variant of chess (e.g. los alamos chess, with forced promotion to queen, and win by capturing the king, not by checkmate). This would greatly simplify the move generator, which would still be quite complicated.
Next, I'd recommend using some kind of macro system so you can write the code at a slightly higher level. That is, unless you're truly masochistic. I don't have any particular recommendation.
Make sure the brainfuck compiler you use doesn't have program-size limitations, as your program will be enormous. I imagine the default 30kb of program memory will be enough, but if not, you'll need to find an implementation which meets your needs.
You'll need to write a memory map of which variables will be located where in memory, and how they will be used. Using a macro processor will make it much easier to jump between memory locations, and make it possible to modify your memory map as required.
There may be no "proper" way to implement recursion, but it's possible. The way I know of is after your globals, to have a stack with frames of a defined size, with sentinels at each stack frame. Then it's possible to navigate between the current stack frame and the globals, by walking the sentinels. If you don't know what I'm talking about, I can give an example.
A simpler game as a proof-of-concept is just an amazing idea, thank's a lot, this would be the major direction in following work.
I'm truly masochistic, that's true. I have some reasons for that: I'm a self learner and going along the "from bottom to top" approach. I did VICE-like chess engine, than micro-Max-like, than the move generator of micro-Max in NASM assembly. Each time it was a bit "too high" level, so I wanted to dive deeper, hence brainfuck implementation idea. Guys, I'm sorry for this part of the answer for nobody probably cares about the reasons for doing this.
I've already implemented a brainfuck interpreter(forget speed) with 65536 bytes, 2 byte cell size. Thanks for the advise.
Memory map is needed for any brainfuck program, but thank's for mentioning this important point.
The recursion is one of the biggest problems actually so I would really appreciate any detailed examples, you'd help a lot.
The I was thinking to implement minimax is as follows: ++++++[//minimax_algorithm] where the number of pluses defines the search depth and the loop within square brackets is a move generator that returns(to some other cell) the best move on a given depth.