Rubik's Cube Emulator

[SolidCode]

Hi to all.

I wrote a Rubik's Cube Emulator.
The main purpose was to implement search for a move sequence that would allow the specified transition. This code is implemented with and w/o SSE2 support.
So far there is just the exe file in the attachment. Please try to work with the program, let me know how it runs, any other opinions, suggestions.
Meanwhile I will clean up the code and comment it. Later I am planning to post the code here.

There are also several sequence files included.


[attachment deleted by admin]

[PBrennick]

SolideCode,
It looks nice. I am unsure of the purpose, but that looks like a nice bit of programming must have gone into it. Should there be a randomizer? I just do not know enough about the game, I am sure.

Paul

[Tedd]

Seems to work okay (I didn't play for very long though.)
Random shuffle would be good :wink
One thing is that the moves don't seem to be very intuitive. When I try to slide the edge of one face, it moves the face with the edge instead - not the edge I expected. This may just be me (my opinion/what I expect.) :P
How about drag-rotate the whole cude with right mouse button? :toothy

[SolidCode]

Thank you, Paul!

The main purpose of the program, as it states in the help dialog, is to find a sequence of moves (side rotations) that can perform the transition.
You see, there are different things you can do with the cube. You can assemble it. It's not so difficult.
Besides that there are different games on the cube. E.g. you can make certain pictures/ornaments on cube's sides.
If you know how the cube should look in the end, you can set the source cube as assembled cube and the destination cube as the desired state. Then choose "Actions -> Find Sequence" and the program will start looking for a sequence that could accomplish the transition of cube state that you want. It will start by checking all one-move sequences. Then all two-moves sequences etc. If the desired state is legal, the program will eventually find it. It may take a long time though.
You see, there are 12 possible moves on the cube (6 side rotations clockwise and 6 more counterclockwise). So for one-move sequences there are 12 sequences to check. Now for two-moves sequences there are 132 possible side rotation sequences. Three-move sequences: there are about 1400 of them. Four-move sequences: about 15500. Etc.
As you can imagine, by the time you get to 9-moves sequences it takes a significant amount of time to go through all of the possible sequences.
This is why I wrote the program. It was written completely in MASM. I made two algos: one used 586 instructions. And the other used SSE2 extention. This extention itself speeds the process up about two times. I have optimised the main loop significantly, I experimented a lot to make it work faster. That gave me about 52% speed encrease more. I programmed SSE2 pieces to make use of the Hyper-Threading technology and dual-core if it is available.
This is a little of history behind the program that I am presenting here.
And I would like to hear any opinions or suggestions that others might have.
I also want to welcome everyone to read help text from the Help dialog.

[SolidCode]

Hello Tedd,
Thank you for the interest.
As I have said in the prevois post, the main purpose of the program was to improve the search for sequences. Besides I used this project to get some experience with SSE2.
So my main concern was the fastest sequence search possible. I didn't work with the interface that much. Nevertheless I will keep all interface suggestions for future.
Thank you all.

[Tedd]

Modifying your search algorithm can probably increase the performance considerably more than simply squeezing cycles through SSE or whatever.
A little intelligent thinking should allow you to cut out over half the unnecessary searching (because you've already checked those states -- there is more than one sequence to get the cube to any particular pattern.) However, it can increase the memory required at the same time :P

[P1]

Later I am planning to post the code here.

Please do   :U

Regards,  P1  :8)

[SolidCode]

I thought I could post the source code here. Will you guys take a look at it? Maybe you could see some more room for optimization.
It is in the zip attached. The entire project is in MASM; IDE - RadASM. It's not well commented or groomed. I post it for people to be able to compile it and to work with the code. It is not the final version.
The function that I want you to play with is FindSeq. It does the actual search. One-move and two-moves sequences are searched in different loops. They are fast and are not critical. The most important is the main loop (starts around @nextseq:). It processes basicly all the possible sequences.
A sequence of moves is a byte array. There are 6 sides in a cube. Thus there are 6 rotations. Each side can be rotated 90 degrees clockwise (CW) or counter clockwise (CCW). All this makes up 12 basic moves that are possible on a cube. Rotation of any side 180 degrees is made up of two 90 degrees basic moves.
These basic moves are numbered as follows: 0 is Left side CW; 1 is Left side CCW. Then we have Right side moves etc.

Code Select Expand


;cube moves constants
CM_LEFT     equ 0
CM_LEFTX    equ 1
CM_RIGHT    equ 2
CM_RIGHTX   equ 3
CM_TOP      equ 4
CM_TOPX     equ 5
CM_BOTTOM   equ 6
CM_BOTTOMX  equ 7
CM_FRONT    equ 8
CM_FRONTX   equ 9
CM_BACK     equ 10
CM_BACKX    equ 11

So when we go through sequences we increment 0th move and check the sequence. If the move became 12 then set move0=0 and increment move1. And so on until the sequence limit is reached.
When we have a new sequence, we need to check if it can be shrinked (optimized). It is possible if there are opposite moves (Left CW and Left CCW). These moves actually do nothing and can be eliminated. Then the sequence becomes smaller (it shrinks). If it became smaller then we have checked this sequence before so there is no point of checking it again. We need to skip it.
Besides that 3 same moves in a row are equal to one opposite move. So if we find 3 same moves then the sequence shrinks too, and we don't need to check it either, we just go to increment to the next possible sequence.
If current sequence cannot be optimized then we need to check it: call CmpCube (or CmpCubeXMM). There we take the source cube, perform the moves from the sequence on it and compare it with the destination cube. If they are equal then we have found the shortest sequence to achieve the wanted transformation. Otherwise continue search or abort search if sequnce length limit is reached or fSEARCHING flag is cleared from bStats.
This is what the main loop does basicly.
Optimization algo is one of the most used parts of the code. How do we check if there are opposite moves or 3 same ones in a row? Take a look at the move constants. The difference between any opposite move is bit 0. The rest of opposite move bits are the same. This is the key.
I read four bytes from the array. It's faster this way. Then I have all needed following moves in EAX along with the current move. First of all I XOR move0 and move1 (xor al,ah).
If al==0 then the moves were equal so go to check if move2 is the same too. If so then EAX=1 and go to get the next sequence
If move0 and move1 were opposite then I will always have 1 in AL. So if al==1 then we can go to get the next sequence. This is a very fast and efficient way to do the check.
The rest of the loop should be pretty much self-explanatory. Read the comments. And I will really appreciate it if you find some more ways to spead up the search.

[attachment deleted by admin]

[gabor]

Hello!

First of all, I appreciate your efforts SolidCode! Thank you for sharing the idea and your code!
I am glad that you've choosen such a mathematical problem to implement. These math things do not glow as bright like D3D or OpenGL, but they have far more purpose, I'd like to prove that in this post.
(Of course my intention was not to underestimate the work and effort of implementing 3D stuff or to insult 3D fans!  :U)

Since I am a hungarian and the inventor of Rubik's cube was a hungarian too (Rubik Ernő, Rubik is his last name) and I also have big interest in state machines, automatons and in getting lost in the state space I could not help not to post here.  :bg

As you described your algo my first impression was: this is a code that tries to find a possible resolution of a logical formula, a possible trajectory of state variables of a certain model. In short, this topic is very very exciting indeed! It involves many area of computing. I'll try to give you brief explanations to introduce the problem in general. This might help to get examples and theory (for example from the Net).

1. Resolution
There is a logical formula (math logic, with variables, constants and subformulas). The formula can have tons of results, when it is evaluated, since its variables can be substitued by lots of values. The task is, to find a combinatin or all the combinations of variables that get the formula to be true. Or to prove that the formula cannot be satisfied, that is there is no combination of values that would give a logical true result.

2. State space
This can be comprehended as a generalization of the previous task. There is a model, a system (it can be a real system, like an electric circuit or a software) which arguments are known. An argument can have direct effect on the state of the system. (Like a switch in a circuit affects whether the lamp is lit or not, the value of a register affects the state of the CPU/the software...)
These arguments will be the variables of the mathematical representation of the system. The variables have domains, set of values that are valid for the variable; the Descartes multiplication of these domains make up the state space. (The states of all variables give the state of the system, the state can be described by a vector, which members are the variables). The most important task here is "Is there a valid transition sequence between 2 states?". This question can be slightly modified, and we get another interesting question: "Is a state valid? = Can a state be reached by a legal sequence of allowed transitions from an approvedly valid state (like the starting state)?"

As I can remember, both problems were solved by using graph approach. AI deals with exploring the possible ways of cutting down the necessary steps of getting a result, an answer to such questions. Reasoning uses the same technique, since the model is the same: we have starting conditions, the causes; and we have end states, the goals, the consequences. Very simplified this is the essential part of human thinking and planning.

Some ideas I can think of:
- building up sequences from both sides: source cube state and destination cube state.
- adding learning to the searching
First I would find the best model, the best representation of the cube in space state. What value could a state variable hold?

Since this topic is far more interesting, I will visit here often and I try to look into the subject (if I have time). BTW, I am trying to create a library of graph handling...  :bg

Greets, Gábor

[SolidCode]

Hello Gabor,

I appreciate your interest.

It seems to me that you have a very mathematical mindset. So we are very different. Math often was a very difficult subject in school for me.
I know only one way to solve the problem. That is searching through all possible cases. This is the way that I have implemented here.
Searching for a sequence from both ends... If I understand it correctly, it would be two same thread working in two directions. But there is still one CPU (for most of us). I don't see how this could spead up the process.
Learning for the search... I'm not sure what it means. And I'm not sure I want it. It would probably slow down the algo, and I am not sure it would really help. My program is just a simple tool. The user must be smart enough to save the found results, so that he does not have to search for it again.

If you know of a better and faster algo to accomplish the task, I would be interested to hear about it.

I hope I did not offend you. It's just quite difficult for me to understand a math discussion. Especially in a language that is other than my own.

[gabor]

Hello SolidCode!

Thanks for your answer! You did not offend me at all!
Besides, you pointed out the weaknesses of my suggestions very wisely :wink.
As I wrote before I'll stuck on the topic, and try to look into it as soon as I finish my current work.

About math, I have to tell you that I was not that good in math either. My "secret" is simply that I studied computer science, so I got familiar with algos and methods designed and developed by really smart brains, far far more clever than me. All I try to do is to apply that knowledge on coding tasks like your Rubik's cube...

Greets, Gábor

[tenkey]

The typical fast human solver of the cube uses sequences of specific transformations.

Some solvers fix one layer at a time. My first solutions used this approach.

I now use a corners-first (position and orient four corners, then position last four corners and rotate three at a time if necessary), edges-last (position pairs, then flip last pair if necessary) approach. If I've made a mistake in positioning the last four corners, I'll use moves that swap pairs of corners to fix the positions.

The humans do not produce optimal (shortest sequence) solutions. They do demonstrate that their methods produce solutions in a reasonable amount of time.

Somewhere I have a copy of David Singmaster's Notes on Rubik's 'Magic Cube', which gives some related math (algebra) theory.

[SolidCode]

Hello tenkey,

I'm not sure what you were trying to say. Solving the cube or assebmling it is a subcase. This program can also be used for creating ornaments on the cube.

[Mark Jones]

Very nicely done! :U

I'm not very good with maths at all either (and puzzles like these drive me mad), but think I have something that could help. Currently the routine is brute-force guessing all possible combinations. This would be the best (and only) algorithm if the colored stickers themselves were moved around instead of the cube sectors being rotated... that is to say, a brute-force approach is not taking into consideration that most of the pieces relate to each other in some way. The corner and side pieces have a finite and repeatable relationship to all other sides. Every corner cubelet references 3 colors (sides) and every edge cubelet references 2. When loading the 'middles.csf' state, a brute-force guess reveals the solve in a decent amount of time.

So, maybe a solution would be to assign relationships to each corner and edge piece, and aim to get those pieces in place by virtue of their relationship to each other. Then brute-force the middles. Or maybe rotate things to get the middles in place, and calculate all other piece movements based off of that known starting position and relation.