Any Interest in creating speed cubing algs for an AI (payment in crypto possible)?

[Ian Knowles]

Hi all,

I've recently developed a basic AI for solving cubes (it can do 2x2x2 and 3x3x3 currently but is only using the very basic approaches to solving the puzzles).

Just wanting to find out if anyone here would be interested to help improve the AI by teaching it better algos (there might be financial rewards offered for this so if you are willing to help but would like to be paid for your help then just indicate this).

(I am part of the decentralised organisation called CIYAM which is known in the Bitcoin community and any payments would be in either BTC or LTC most likely)

Cheers,

Ian.

 

[xyzzy]

https://www.jaapsch.net/puzzles/compcube.htm
http://kociemba.org/cube.htm

These two sites have just about all the information you need to write a good and fast solver from scratch.

You say "teaching", but is it using some kind of neural network to solve the puzzles? I don't think there's been a successful ANN-based algorithm for solving the Rubik's Cube before, so that would be quite interesting.

 

[Ian Knowles]

I've invented a new kind of AI that is not quite the same as a neural network but does have some similarities.

The code to solve the puzzle is not anything specific - but instead just a bunch of "goals" and "algos" which the system is trained on.

For sure this is working with 2x2x2 and 3x3x3 (and I could make it work for 4x4x4 and 5x5x5 as I can do those cubes).

Currently it can't solve the cubes any better than I can really (well slightly better as it knows a few more algos than I can remember) so I'd like to make it perform a little more impressively than I can (in terms of approaching God's number).

This AI is going to be 100% open source (it already is actually) so any contribution made will be part of this development (this is not any sort of trolling but a genuine request for interest to help with the project).

If I have posted this in the wrong area then please move it mods and accept my apology (have only joined in the last hour so am really a newbie here). I know that I am *asking for help* but really I am not asking for help as someone who doesn't already know how to solve a cube (so I don't think that I am violating the rules but am not going to protest if that is what you guys decide).

Just to show everyone that I do know something about cubes I can say that the 5x5x5 algo for parity correction with the "tredge" is not necessary to even know if you just do all of the pairings first (I think that most people who don't understand cubing would not be able to make head or tale of this but I'm pretty certain that you guys understand this perfectly).

 

[xyzzy]

Currently it can't solve the cubes any better than I can really (well slightly better as it knows a few more algos than I can remember) so I'd like to make it perform a little more impressively than I can (in terms of approaching God's number).

There's a complete listing of move-optimal algs for every possible last layer case.

If you want to get near God's number, (I believe) it's necessary to solve in a way that doesn't even remotely resemble how humans normally solve the cube. If you look at official FMC results (solve a 3×3×3 in one hour with as few moves as possible), the top FMCers can get averages of around 25 moves, which is still five moves higher than God's number. Just for comparison, a typical implementation of Kociemba's algorithm can generate a ≤21-move solution in milliseconds. (Herbert Kociemba recently released a Python implementation.)

This AI is going to be 100% open source (it already is actually)

Link to the source? I'm kinda interested in the approach you're taking.

 

[Ian Knowles]

So what I'm doing is really something new.

The main point is open source AI but I am wanting to have this happen with the help of a community that might appreciate this (I know that AI is probably going to make unemployment 90% within ten years).

Maybe you Rubik's cube solvers don't understand your importance to the future of the world but I see this.

The link to the source code is as follows: https://github.com/ciyam/ciyam/blob/master/src/cube.cpp

(the approach that I am taking to AI can involve humans - and I am sure that this sort of community is the right sort of community to be involved with this)

Oh - btw - if you are in doubt about the ability of my AI to solve a 2x2x2 or a 3x3x3 cube then just send the scramble and I will send the solution (obviously even better if you install the software and do this for yourself).

 

[One Wheel]

I really don't have the knowledge to help with this, but it sounds really interesting. Is it similar to AlphaGo in terms of probabilistic strategy? My understanding was that AlphaGo essentially plays thousands of games against itself to figure out what good positions look like. Do you need to input algs or does the computer develop them? I suspect that this thread properly belongs in the software section.

(I know that AI is probably going to make unemployment 90% within ten years).

We could argue all day about this, but suffice to say I'm dubious about this particular statement for many reasons.

 

[obelisk477]

Hi all,

I've recently developed a basic AI for solving cubes (it can do 2x2x2 and 3x3x3 currently but is only using the very basic approaches to solving the puzzles).

Just wanting to find out if anyone here would be interested to help improve the AI by teaching it better algos (there might be financial rewards offered for this so if you are willing to help but would like to be paid for your help then just indicate this).

(I am part of the decentralised organisation called CIYAM which is known in the Bitcoin community and any payments would be in either BTC or LTC most likely)

Cheers,

Ian.

Well no one has offered, so I'll help. What kind of algorithms are you looking for

 

[Ian Knowles]

In regards to unemployment let's just say that 90% is my prediction (and I do hope that I am wrong).

The AI that I've constructed can create its own algos, however, at this stage that doesn't work very well for more than a few moves (due to the huge number of permutations) so for the most part I manually taught it how to solve the 2x2x2 and 3x3x3 cubes (although it learned some of the simple steps on its own as I couldn't be bothered teaching it that).

I think that the 2x2x2 is probably not far from being optimal - some examples of scrambles and solutions are as follows:
U R L' Y2 F Y2 Z' B' X R ==> X' U' F' D' R' D R Z2 U' R U R' U' R' F R F' U
U2 F' F' X D F' F' X Y U ==> Z' U2 D2 L F Z2 U2
X' Y2 F B2 U' Y X' ==> Z U D' L Z2 U
Z Y2 L U F U Y' Z' ==> X U F' L' F' D' R' D' R Z2 R' U' R U' R' U2 R Y' U2 L' U R' D2 R U' R' D2 R2 X' Y

Basically what I'm thinking to offer is crypto rewards for publishing better algos that solves each step along the path (i.e. CRS -> F2L -> OLL -> PLL). This will effectively operate as a new kind of POW (Proof Of Work) approach that would be open for either humans or computers.

A few 3x3x3 example scrambles and solutions are as follows:
S' Rw Bw L F F2 X2 Bw B Bw2 Z F D B E Rw' Z F Fw ==> M E2 L F U2 F L' D F' R F Z2 L F' L' F U2 R' F R F' U2 L' B L B' U2 B' R B R' U' R U R' U' R U R' U' R U R' Y2 Dw R' U R U2 R' U R Dw' Y2 Y U2 R U' R' U2 R U' R' Y2 U R U R' U' R U R' U' R U R' Y F U R U' R' F' U' F R U R' U' F' U' R' F R' B2 R F' R' B2 R2 U2 Z2

S M Lw E B' Bw' Fw U Dw' X Z2 S Lw M Z' X Z Y' Bw' S' ==> E M2 L' F U2 L2 D F2 D' L2 D' Z2 L' U' L F' L F L' U' F R' F' R B U' B' L' B L B' U' B' R B U' R' U2 R U' R' Y R2 U2 R' U' R U' R' U2 R' Y U R U' R' U2 R U' R' Y Dw R' U R U2 R' U R Dw' Y U2 F U R U' R' F' U2 R U R' U R U2 R' U2 R U R' U R U2 R2 F R' B2 R F' R' B2 R2 U R' F R' B2 R F' R' B2 R2 U' Y' L' U L' U' L' U' L' U L U L2 Y Z2

Z' Dw B Rw2 Z' Dw M' M D2 Uw Lw S' Rw M U Y Dw' E' S' Y ==> M S R B' F L' F' B R' B' Z2 U F' L F L' U R' F R F' U2 L' B L B' R2 U2 R' U' R U' R' U2 R' Y2 R U' R' U2 R U' R' Y U R U' R' U2 R U' R' Y U F U R U' R' F' U2 R U R' U R U2 R' R U R' U R U2 R' U2 R U R' U R U2 R' U' R U R' U R U2 R' U2 R U R' U R U2 R' U Z2

Anyone that is interested in participating should contact me via PM.

 

[xyzzy]

Basically what I'm thinking to offer is crypto rewards for publishing better algos that solves each step along the path (i.e. CRS -> F2L -> OLL -> PLL). This will effectively operate as a new kind of POW (Proof Of Work) approach that would be open for either humans or computers.

Optimally solving a 2×2×2 or 3×3×3 is really fast with today's hardware (on the order of nanoseconds for the former and centiseconds for the latter). The "better algos" already exist (cf. AlgDb), and even if they didn't, we could find them pretty quickly.

 

[Ian Knowles]

I've no doubt that the algos already exist so basically what I'm thinking of doing is to offer rewards for training the AI to solve the cube with less moves than it currently does (also to provide training for 4x4x4 and 5x5x5).

Eventually the AI will be able to do this learning for itself but at this early point it is going to be simply more effective to get human help to train it.

The POW approach that I'm considering is going to involve the use of a PRNG to create say a thousand scrambles then compare the current AIs solutions to one that has potential better algos (the specific scrambles will not be knowable in advance so there is no way to "win" other than to actually provide better algos).

 

[mark49152]

I don't have much to offer on training the AI, but you should certainly read about random state scrambles and ensure you're using proper scrambles to test your software.

Example: X' Y2 F B2 U' Y X' ==> Z U D' L Z2 U - both scramble and solution are effectively only two moves, due to rotations and cancellations. The second 2x2 scramble is only three moves.

Likewise in your first 3x3 scramble the sequence F F2 X2 Bw B Bw2 cancels to only one move.

 

[Ian Knowles]

Thanks - I'll be improving the scrambling to at least cancel out stuff such as Y followed by Y' (it's currently just choosing random moves which can sometimes end up being nonsensical as you rightly have pointed out).

The reason for the unnecessary Z moves in the solution is because it's been taught to solve it the slow way that I use (i.e. always starting with a white cross and after solving that turn the cube upside down). Some coding changes are probably going to be necessary in order to allow for a different set of steps depending upon which face becomes the starting point although I'll have to work out how that can be done in a very general manner in order to suit the AI implementation.

 

[mark49152]

Like others, I'm also curious about your approach. All the approaches to computer solving I've seen have been algorithmic - either search-based or by recognising patterns and executing corresponding solution steps. Recognition of patterns tends to be much simpler than the typical use-cases for neural nets because there are only a small number of pieces relevant to each step or pattern, yielding a small number of discrete cases. Typically the pattern cases are enumerated and associated with solution steps via a look-up table.

Can you explain how your approach differs?

 

[Ian Knowles]

I think what you have described is pretty much how it functions (so I guess it isn't fundamentally different). To train it you give it a simple goal (for a 3x3x3 the first goal is to rotate the cube so that the yellow is on top and the orange is at the front).

It can train itself provided that the number of move permutations isn't very high (so the first step described above it learned itself in less than a second). The actual code isn't a neural network as such but perhaps that isn't highly relevant to the way it functions.

As each goal takes you closer to a solution it will start according to the last already matched goal in the goal sequence and continue performing known algos depending upon the state it finds (the more complicated the algo the less chance it has of being able to teach itself due to the huge number of permutations involved).

What is of key importance is that it has no idea that it is solving a "cube" but instead simply reads the state and then works with the list of known "ops" that it can perform. It can also optimise the amount of work required by learning how a move actually affects the state (so if it's performing an U move then it knows that it can ignore checking the state of the bottom face even though it doesn't really know what a bottom face is).

 

[shadowslice e]

One project I was going to do over the summer (provided I get good enough at coding) is sort of a genetic programming approach where you have a series of randomly chosen goals (eg create a 2x2x2, Roux FB) and combine it with others until you get to a point which is solvable then combine the steps that work the best and so on and so on while adding other random mutations like fusing certain steps and splitting others.

Though I would be focusing on human usability so max is x number of pieces solved at a time and minimum n number of steps and stuff.

 

[Ian Knowles]

I like your thinking and would welcome you to use the CIYAM platform to play with this idea (it's FOSS).

It might also make it easier for you as you won't need to learn programming to do this (as I've done all of that work already).