I know you have a bunch of experience already, in programming and computation-intensive code, but please listen! Some of the people posting (e.g. rokicki and cuBerBruce) have an amazing amount of experience in programming cube solvers, and the advice they are giving is definitely helpful. When you don't understand something, make sure not to just assume it's unhelpful - do some research, or ask questions, and try to see what the advice means. It may save you a lot of work later on.
Yes, I bow to their expertise and I readily acknowledge I am the noob of all noobs, I have no problem admitting that, at all. Please don't mistake my exuberance for anything but the extreme joy I found in programming a 4x4x4 solver. I had no idea how in the dark I was until I saw Bruce's program prune the heck out of the search tree like a hot knife through butter
It is possible to have a fair amount of programming experience and be a total dork when it comes to cubing. Dork #1, right here <------. I do read the posts/links/web pages and PDFs, but that does not necessarily translate into a complete understanding. That is not to say I don't make some underlining and often times
incorrect conjectures about what I am reading. Please understand I am weak on the nomenclature, and some of what I am reading is not crystal clear to me. Not by a longshot.
When I do grasp something, I do have the innate ability to fully delve into it, and, at times, even raise the bar. I am not yet at the fully-grasping phase yet. I do understand the concept of indexing and pruning and searching, just not as it applies to cubing. To illustrate this, here is a fairly complex indexing function for the game of checkers where one side has 3 kings and 1 checker and the other side has 2 kings and 2 checkers. This function will magically enumerate from 0 to n-1, where n is the total number of possible arrangements, without duplicating an index, nor skipping any ranges.
Code:
/*********************************************************************/
/* */
/* General Indexing Function Combinatoric Macros */
/* --------------------------------------------- */
/* */
/* Given there are N identical pieces of the same color, how many */
/* ways can they be arranged uniquely on a game board, independent */
/* of the size of the board? */
/* */
/* The answer involves producing a polynomial expansion of the form */
/* */
/* a + (b-1)(b-2)/2! + (c-1)(c-2)(c-3)/3! + .. (z-1)(z-2)..(z-N)/N! */
/* */
/*********************************************************************/
#define _2_same_pieces_subindex(a,b) ((a) + ((((b)-1)*((b)-2))/2))
#define _3_same_pieces_subindex(a,b,c) ((a) + ((((b)-1)*((b)-2))/2) + ((((c)-1)*((c)-2)*((c)-3))/6))
#define _4_same_pieces_subindex(a,b,c,d) ((a) + ((((b)-1)*((b)-2))/2) + ((((c)-1)*((c)-2)*((c)-3))/6) + ((((d)-1)*((d)-2)*((d)-3)*((d)-4))/24))
#define _5_same_pieces_subindex(a,b,c,d,e) ((a) + ((((b)-1)*((b)-2))/2) + ((((c)-1)*((c)-2)*((c)-3))/6) + ((((d)-1)*((d)-2)*((d)-3)*((d)-4))/24) + ((((e)-1)*((e)-2)*((e)-3)*((e)-4)*((e)-5))/120))
unsigned long long get_08_piece_index_3K1C_AGAINST_2k2c(unsigned char wk1, unsigned char wk2, unsigned char wk3, unsigned char wc1, unsigned char rk1, unsigned char rk2, unsigned char rc1, unsigned char rc2)
{
unsigned long long index_function_value;
unsigned long long index_part_1, index_part_2;
unsigned long combined_checker_contribution_to_index, index_part_3;
unsigned char adjust_rk1_index,
adjust_rk2_index,
adjust_wk1_index,
adjust_wk2_index,
adjust_wk3_index;
index_function_value = 0;
/*********************************************/
/* order of placement on the board: wrrWWWRR */
/*********************************************/
adjust_wk1_index = wk1;
adjust_wk2_index = wk2;
adjust_wk3_index = wk3;
adjust_rk1_index = rk1;
adjust_rk2_index = rk2;
if(wk1 > wc1)
adjust_wk1_index--;
if(wk1 > rc1)
adjust_wk1_index--;
if(wk1 > rc2)
adjust_wk1_index--;
/**********************/
if(wk2 > wc1)
adjust_wk2_index--;
if(wk2 > rc1)
adjust_wk2_index--;
if(wk2 > rc2)
adjust_wk2_index--;
/**********************/
if(wk3 > wc1)
adjust_wk3_index--;
if(wk3 > rc1)
adjust_wk3_index--;
if(wk3 > rc2)
adjust_wk3_index--;
/**********************/
/**********************/
if(rk1 > wc1)
adjust_rk1_index--;
if(rk1 > rc1)
adjust_rk1_index--;
if(rk1 > rc2)
adjust_rk1_index--;
if(rk1 > wk1)
adjust_rk1_index--;
if(rk1 > wk2)
adjust_rk1_index--;
if(rk1 > wk3)
adjust_rk1_index--;
/**********************/
if(rk2 > wc1)
adjust_rk2_index--;
if(rk2 > rc1)
adjust_rk2_index--;
if(rk2 > rc2)
adjust_rk2_index--;
if(rk2 > wk1)
adjust_rk2_index--;
if(rk2 > wk2)
adjust_rk2_index--;
if(rk2 > wk3)
adjust_rk2_index--;
/**********************/
/*************************************************************************************************/
/* */
/* February 12, 2009 */
/* */
/* Completely changed this indexing function. First, the order in which data is passed in now */
/* matches the CONSTANT identifying the slice: k_WWWwRRrr -- this is now standard for all of the */
/* indexing functions. Second, the all checkers indexing function for 3 pieces is used. Why not */
/* use what is already available? Third, the colors were reversed to match the spec. */
/* */
/* July 11, 2001 */
/* */
/* With one black checker in the king row, count from 1-378 for each of the 4 squares. */
/* The white checkers can reside on 28*27/2 = 378 squares, so the equations is of the form: */
/* */
/* (rc1-1)* 378 + _2_same_pieces_subindex(wc1, wc2) */
/* */
/* When the black checker has moved to square 5 or greater, then you add 378*4 (1512) to the */
/* count and determine which of the 27*26/2 remaining combination of squares the white checkers */
/* are on. With 27*26/2 = 351, the equation looks like... */
/* */
/* (rc1-5)* 351 + _2_same_pieces_subindex(wc1, wc2) + 1512 */
/* */
/* This technique treats the black and white checkers as one "sub-index", rather than separate */
/* components. We count from 1 to (4*378 + 24*351) = 9936, then pass this as the "Q" to */
/* the precompiled macro. This "Q" is a substitue for "rc1" and "wc1" and "wc2". */
/* */
/* September 4, 2010 */
/* */
/* Changed the indexing function again, hopefully for the last time. Dealing with that wonderful */
/* Microsoft Compiler bug where intermediate calculations exceeding 2^31 are always treated as a */
/* signed 32-bit result, which invariably resulted in a negative number, which invariably would */
/* decrease the index when an increase was expected, and, consequently, duplicate indices would */
/* always be produced. It's a good thing I decided to re-test the indexing functions!! */
/* */
/*************************************************************************************************/
combined_checker_contribution_to_index = 1 + get_03_piece_index_0K2C_AGAINST_0k1c(33-rc2, 33-rc1, 33-wc1);
/*************************************************************************************************************/
/* */
/* September 4, 2010 */
/* */
/* Gradually converting more GOOD, WORKING indexing functions over to this new format. See my comments from */
/* August 26, 2010 for a full explanation. Thanks to Billy Gates for more wasted time. */
/* */
/*************************************************************************************************************/
index_part_1 = (unsigned long long)(1187550) * (unsigned long)(combined_checker_contribution_to_index - 1);
index_part_2 = (unsigned long long)(325) * (unsigned long)(_3_same_pieces_subindex(adjust_wk1_index, adjust_wk2_index, adjust_wk3_index) -1);
index_part_3 = (unsigned long)(_2_same_pieces_subindex(adjust_rk1_index, adjust_rk2_index));
index_function_value = (unsigned long long)(index_part_1 + index_part_2 + index_part_3);
return (index_function_value - 1);
}
So, I am thinking about how to index just the corners, and just the centers. I'd like to pre-solve turns-from-solution (tfs) for the corners, and all of the centers that are reasonable (1 missing per side, 2 per side, maybe no more).
If I could create such an indexing function, there is no need to store positions at all, just transform a position to an index, and write to that index during the solve, and read that many bytes into the file when probing.
The problem is: Creating the indexing function!
Checkers and chess, I had no problem with. Flat board, easy to enumerate the state space. Corners, ugh! 3D. Orientation variations. I am not sure how to map a turned vs. unturned cube. Also, there are some turns that are illegal positions, such as just one corner being flipped, etc., so I am not sure about how to go about it.
What I am doing: Sharing all of the portions of my code that would be of interest, in hopes that some of the guys who did write some easy-to-read code might be interested in doing the same. If I could get a lean/mean version of a program running, some of the hardware I have access to might crank out some very interesting finds!
The pillars of civilization were built upon ideas shared and improved upon over vast spans of time. Who knows, we might brainstorm some killer code through cooperation.
Korf, 1997 is the earliest I know (and quite a nice paper, I think).
Yes, very nice. Some code would have been even better.
Interestingly, the paper mentions the work of Dr. Jonathan Schaeffer. He cited one of the papers I wrote in two of his own papers (on checkers) and he was nice enough to thank me (and some others, of course) on his website after he solved the game of checkers.
I would say "roadmap" is not the right analogy. The corner "distance-from-solved" database will give you a LOWER BOUND on the number of moves needed to solve the entire 4x4x4 position. This often allows aborting a search path before reaching the leaf nodes for your current search depth.
Such a database is usually created using a breadth-first search. This is a different type of search from a depth-first search. This is all talked about in Jaap's Computer Puzzling page I referenced earlier.
If you want to see some really cool endgame databases used in run-time during a search, check out my 80-square chess program,
which can announce a mate in 268 moves in the endgame of King + Queen + 1 Pawn vs. King + Queen. I added 2 pieces to the board,
one that can move like a Knight + Rook, which I called the Chancellor. The other moves like a Knigh + Bishop = Archbishop.
The King + Archbishop vs. King has a longest win of 21 moves I think, and it is really hard to administer for the side
with the archbishop.
Anyway, if you like chess, this program will surprise you with some really strong moves on this 80-square board.
It's about 64 MB compressed with all of the 3-piece and some of the 4-piece endings already included.
A menu item will load the position for some of the longest win configurations.
lightningcloudcomputing.com/vortex.zip
I The corner "distance-from-solved" database will give you a LOWER BOUND on the number of moves...
Ah ha! Lighbulb moment! So if you are at a depth of 3 plies executing a 10 ply search, you are 7 plies from your terminal node, you can use the INEXACT information in the corner-tfs to basically check your own corner arrangement, and discard all of those that definitely can't be solved with a lower bound of 7 turns. Nice! You see, I am "too used to" the EXACT distance-to-win data in the databases I have experience with, so this experience was working against me!
So is there an indexing function that generates only one instance of each of the 8! * 3^7 corner configurations? Or would that just be the IDA* move generator with only face turns?
