Need help designing a multi-threaded solver

[4Dummies]

I was sneered at for having too broad a question on stackOverflow, so I hope this is a reasonable place for a poorly-defined question, because I need help in making it better-defined.

I've been working on refining a solution to the strategy game Qubic, and have close to 100 million positions solved.  That's actually just a beginning, so you get some sense of the scope of what I'm working on.  There is a known solution, but it is not optimal.  I want optimal.  It may take 10 years.

I've been doing the work mostly in C and Python.  C where it has to be fast (the actual solver) and Python where the development has to be fast (everywhere else) because I am the bottleneck, since I'm having trouble putting together a framework that organizes the solving process.

I have several multi-core machines: 2 Core i-7s, a 16-core Xeon and a Core i5 laptop.  The Xeon also has a thousand or so available GPU cores on a spare nVidia card, but I haven't even started coding for that.

So I want to create a framework that will manage the solver.  The main problem is that I cannot predict how long it will take so solve any position.  The way I have been working, they may take 6 minutes on my fastest machine, or may exhaust my patience after a couple of weeks (at which point I usually have to take the machine down for updates or some such).  So I plan on a time limit of a few hours.  When a solver times out, I plan to derive the possible subsequent positions (after 2 moves) and solve those.  Generally, almost all of the subsequent positions involve blunders, and are solved very quickly and I'm left with one or two that are slightly easier to solve than the original position.  Positions are expressed as 64-character strings.  Solutions (or failures) are expressed in somewhat longer strings, less than 512 characters.

I've started looking at Python modules multiprocess, subprocess, threading, and pyzmq.  All are interesting, and I'm having trouble deciding which to use.  I need some guidance.

I track my solutions with an SQLite database and module sqlite3, and this database could also be used by the framework.

my code here

[Larz60+]

OK, so where's the question and 'code so far' example?

[4Dummies]

There's no code, because I haven't selected the tools yet. That's the question: choose among or between threading, multiprocessing, subprocess, pyzmq, and anything else, and give advice about how to put the pieces together. I'm in a quandary for having too many choices, each of which has its own learning curve, and I may not even know about the best possible tools for the job.

[Larz60+]

if you have over a million positions solved, you are going about the solution the wrong way.
You need to develop some nearest neighbor algorithms.

I haven't written games since the Apple II e was popular, but
I know You want to break it down into small steps, and I personally would use something like a mind map,
maybe x mind 8 to keep track of it all.

There are some game developers here, and you should wait for them to respond.

[4Dummies]

if you have over a million positions solved, you are going about the solution the wrong way.
You need to develop some nearest neighbor algorithms.

I haven't written games since the Apple II e was popular, but
I know You want to break it down into small steps, and I personally would use something like a mind map,
maybe x mind 8 to keep track of it all.

There are some game developers here, and you should wait for them to respond.

I have no idea what these maps are, but I don't think a "nearest neighbor" approach is likely to help, the playing arena being as dense and connected as it is.  The way I'll be breaking it up is by looking at successor positions.  Anyone feel free to enlighten me if I'm wrong.

BTW the easiest way to think about the game is that it's 3-D tic-tac-toe requiring 4 in a row, on a 4x4x4 "board".  A first-player win was announced in September 1980 issue of Mathematics Magazine, and I have that author's solution.  My goal is to improve it.

And I'm not writing a game, I'm solving it.  One version of the game already exists on one of my SourceForge pages at https://sourceforge.net/projects/qubic/?...=directory.  I have changes in mind for it, but that's not what this is about.

[Larz60+]

Well, here's a pdf that has an entire chapter (beginning on page 95 (pdf page 113): http://www.aiexp.info/files/allis-thesis.pdf
and a list of others: https://www.google.com/#q=pseudo+algorit...Qubic+game

[Larz60+]

Originally I had this game confused with a much simpler one (I think it was called qubit), sorry about that.

I've been reading the article in http://www.aiexp.info/files/allis-thesis.pdf from last post, and realize
the complexity now.

This chapter seems to have some useful algorithms (for Qubic), as well as pseudo code for same.

[wavic]

Any particular reason to use strings for positioning? Why not numbers. It will be faster. And you could use the GPUs

[4Dummies]

Originally I had this game confused with a much simpler one (I think it was called qubit), sorry about that.

I've been reading the article in  http://www.aiexp.info/files/allis-thesis.pdf from last post, and realize
the complexity now.

This chapter seems to have some useful algorithms (for Qubic), as well as pseudo code for same.

I read that some time ago. Allis was interested in some of the same things I am, but not interested in an _optimum_ solution. His techniques do not lend themselves to optimization. At least as far as I can tell.

---

Any particular reason to use strings for positioning? Why not numbers. It will be faster. And you could use the GPUs

It's much easier to understand what the code is doing. And I can also use GPUs on strings, especially since they are fixed-length. Numeric coding would not save all that much space, and would require other things to support development -- especially the debugging parts.

Because I am personally the bottleneck to progress, making my job easier is important. And a great deal of my job is ensuring correctness and fixing bugs.

---

Well, here's a pdf that has an entire chapter (beginning on page 95 (pdf page 113): http://www.aiexp.info/files/allis-thesis.pdf
and a list of others: https://www.google.com/#q=pseudo+algorit...Qubic+game

The Allis thesis was interesting, but does not help that much beyond what I already have.

The other link is mostly (except for that thesis) about other things, or things that are not helpful, as far as I can tell.