Searching \ for '[OT] Tic-Tac-Toes' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=tic+tac+toes
Search entire site for: 'Tic-Tac-Toes'.

Exact match. Not showing close matches.
PICList Thread
'[OT] Tic-Tac-Toes'
2016\09\03@235546 by Isaac M. Bavaresco

picon face
part 1 435 bytes content-type:text/plain; charset="utf-8" (decoded base64)

Years ago I wrote a short program to analyze the game Tic-Tac-Toes and
forgot about it.

This week I was reviewing some old backups and stumbled upon it.

The code is attached to this message, for the ones that may find it amusing.

Compiles with GCC and outputs to stdout. The output can be redirected to
a text file and viewed in your preferred program editor.


Cheers,

Isaac



part 2 9366 bytes content-type:text/plain; name="TicTacToes.cpp"
(decoded base64)

//==============================================================================
// Copyright (c) 2008, Isaac Marino Bavaresco
// All rights reserved
// spam_OUTisaacbavarescoTakeThisOuTspamyahoo.com.br
//==============================================================================
// This program generates all possible sequences for the game Tic-Tac-Toes.
// Definitions:
//        State:
//                Each one of the possible states that the game board may assume during the game.
//                Each state receives one unique VALUE, which is represented by a 18 bit number
//                (stored in 32 bit variables). Each cell is represented by two bits which may
//                assume three different values: 0x = empty, 11 = X, 10 = O
//
//                The theoretical maximum number of states is 3 ** 9 = 19683, but most are invalid states
//                ( all positions occupied by the same symbol, for instance), leaving 772 valid
//                different states.
//                For optimization, the program eliminates the states which are equivalent after
//                rotation or mirroring and considers them all the same state. This way, we may
//                reduce the number of different states by up to 1/8.
//
//        
//==============================================================================
#define WIN32_LEAN_AND_MEAN                // Exclude rarely-used stuff from Windows headers
//==============================================================================
#include
#include
//==============================================================================
struct tagTicTacToes
       {
       unsigned long        Value;
       unsigned long        Id;
       unsigned short        NumberOfChildren;
       struct tagTicTacToes        *NextSibling;
       struct tagTicTacToes        *Children[8];

       };
//==============================================================================
struct tagTicTacToes *Levels[11] = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
struct tagTicTacToes *LastInserted = NULL;

unsigned long        TotalNodes        = 0;
unsigned long        NodesLevel        = 0;
//==============================================================================
unsigned short Finished( unsigned long Value )
       {
       unsigned long Aux;
       unsigned short i;

       unsigned long Mask1[] =
               {
               0x0000003f, // 0000 0000 0000 0000 0000 0000 0011 1111
               0x00000fc0, // 0000 0000 0000 0000 0000 ffff 1100 0000
               0x0003f000, // 0000 0000 0000 0011 1111 0000 0000 0000

               0x000030c3, // 0000 0000 0000 0000 0011 0000 1100 0011
               0x0000c30c, // 0000 0000 0000 0000 1100 0011 0000 1100
               0x00030c30, // 0000 0000 0000 0011 0000 1100 0011 0000

               0x00030303, // 0000 0000 0000 0011 0000 0011 0000 0011
               0x00003330, // 0000 0000 0000 0000 0011 0011 0011 0000
               };

       unsigned long Mask2[] =
               {
               0x0000002a, // 0000 0000 0000 0000 0000 0000 0010 1010
               0x00000a80, // 0000 0000 0000 0000 0000 1010 1000 0000
               0x0002a000, // 0000 0000 0000 0010 1010 0000 0000 0000

               0x00002082, // 0000 0000 0000 0000 0010 0000 1000 0010
               0x00008208, // 0000 0000 0000 0000 1000 0010 0000 1000
               0x00020820, // 0000 0000 0000 0010 0000 1000 0010 0000

               0x00030303, // 0000 0000 0000 0010 0000 0010 0000 0010
               0x00003330, // 0000 0000 0000 0000 0010 0010 0010 0000
               };

       for( i = 0; i < sizeof Mask1 / sizeof Mask1[0]; i++ )
               {
               Aux = Value & Mask1[i];
               if( Aux == Mask1[i] )
                       return 1;
               else if( Aux == Mask2[i] )
                       return 2;
               }
       return 0;
       }
//==============================================================================
unsigned long Mirror( unsigned long Value )
       {
       unsigned long Result;

       Result        = Value                                & 0x0000c30c;
       Result  |= ( Value << 4 )        & 0x00030c30;
       Result  |= ( Value >> 4 )        & 0x000030c3;
       
       return Result;
       }
//==============================================================================
unsigned long Rotate( unsigned long Value )
       {
       unsigned long Result;
       
       Result        = Value                                & 0x00000300;
       Result  |= ( Value << 4 )        & 0x0000c030;
       Result  |= ( Value >> 4 )        & 0x0000300c;
       Result  |= ( Value << 8 )        & 0x00000c00;
       Result  |= ( Value >> 8 )        & 0x000000c0;
       Result  |= ( Value << 12 )        & 0x00030000;
       Result  |= ( Value >> 12 )        & 0x00000003;

       return Result;
       }
//==============================================================================
void GenerateEquivalents( unsigned long Value, unsigned long *Equivalents )
       {
       unsigned short i;
       unsigned long Temp;

       Equivalents[0] = Temp = Value;
       for( i = 1; i < 4; i++ )
               Equivalents[i] = Temp = Rotate( Temp );
       Equivalents[4] = Temp = Mirror( Value );
       for( i = 5; i < 8; i++ )
               Equivalents[i] = Temp = Rotate( Temp );
       }
//==============================================================================
unsigned short SearchArray( unsigned long *Equivalents, unsigned long *Children, unsigned short NumberOfChildren )
       {
       unsigned short i, j;

       for( i = 0; i < NumberOfChildren; i++ )
               for( j = 0; j < 8; j++ )
                       if( Children[i] == Equivalents[j] )
                               return 1;
       return 0;
       }
//==============================================================================
struct tagTicTacToes *SearchTree( unsigned long *Equivalents, unsigned short Level )
       {
       unsigned short i;
       struct tagTicTacToes *p;

       
       for( p = Levels[Level]; p; p = p->NextSibling )
               for( i = 0; i < 8; i++ )
                       if( Equivalents[i] == p->Value )
                               return p;

       return NULL;
       }
//==============================================================================
struct tagTicTacToes *InsertChild( unsigned long Value, unsigned short Level, struct tagTicTacToes *Parent )
       {
       struct tagTicTacToes *p;

       p = new struct tagTicTacToes;

       p->Value                = Value;
       p->NumberOfChildren        = 0;
       p->Id                        = TotalNodes;
       p->NextSibling        = NULL;

       Parent->Children[Parent->NumberOfChildren]        = p;
       Parent->NumberOfChildren++;


       if( Levels[Level] )
               LastInserted->NextSibling = p;
       else
               Levels[Level] = p;

       LastInserted = p;

       return p;
       }
//==============================================================================
struct tagTicTacToes *ConnectChild( struct tagTicTacToes *p, struct tagTicTacToes *Parent )
       {
       Parent->Children[Parent->NumberOfChildren]        = p;
       Parent->NumberOfChildren++;

       return NULL;
       }
//==============================================================================
void GenerateChildren( struct tagTicTacToes *Parent, unsigned short Level )
       {
       struct tagTicTacToes        *p;
       unsigned short        i, NumberOfChildren;
       unsigned long        Mask, Bits, Aux, Value;
       unsigned long        Equivalents[8], Children[9];

       Value                        = Parent->Value;
       Mask                        = 0x00000002;
       Bits                        = Level & 0x00000001;
       NumberOfChildren        = 0;

       for( i = 0; i < 9; i++, Mask        <<= 2, Bits        <<= 2 )
               {
               if( !( Value & Mask ))
                       {
                       Aux = Value | Mask | Bits;
                       GenerateEquivalents( Aux, Equivalents );
                       if( !SearchArray( Equivalents, Children, NumberOfChildren ))
                               {
                               Children[NumberOfChildren] = Aux;
                               NumberOfChildren++;
                               p = SearchTree( Equivalents, Level );
                               if( p )
                                       ConnectChild( p, Parent );
                               else
                                       {
                                       InsertChild( Aux, Level, Parent );
                                       TotalNodes++;
                                       NodesLevel++;
                                       printf( "\rNode Id: %lu", TotalNodes - 1 );
                                       }
                               }
                       }
               }
       }
//==============================================================================
void ShowMark( unsigned long Value )
       {
       printf( "%c", Value & 2 ? ( Value & 1 ? 'X' : 'O'  ) : ' ' );
       }

//==============================================================================
void Print( unsigned long Value )
       {
       ShowMark( Value );
       printf( "%c", '|' );
       ShowMark( Value >> 2 );
       printf( "%c", '|' );
       ShowMark( Value >> 4 );
       printf( "\n-+-+-\n" );
       ShowMark( Value >> 6 );
       printf( "%c", '|' );
       ShowMark( Value >> 8 );
       printf( "%c", '|' );
       ShowMark( Value >> 10 );
       printf( "\n-+-+-\n" );
       ShowMark( Value >> 12 );
       printf( "%c", '|' );
       ShowMark( Value >> 14 );
       printf( "%c", '|' );
       ShowMark( Value >> 16 );
       printf( "\n\n" );
       }
//==============================================================================
void Report( void )
       {
       struct tagTicTacToes        *p;
       unsigned short        i, j, Aux;


       for( i = 1; i < 10; i++ )
               {
               printf( "\nLevel: %u\n", i );
               for( p = Levels[i]; p; p = p->NextSibling )
                       {
                       printf( "\nId: %3u Value: %05X Children(%u): ", p->Id, p->Value, p->NumberOfChildren );
                       for( j = 0; j < p->NumberOfChildren; j++ )
                               printf( "%3u ", p->Children[j]->Id );
                       Aux = Finished( p->Value );
                       if( Aux == 0 )
                               printf( "\n\n" );
                       else if( Aux == 1 )
                               printf( "\n**** Victory of X ****\n" );
                       else if( Aux == 2 )
                               printf( "\n**** Victory of O ****\n" );
                       Print( p->Value );
                       }
               }
       }
//==============================================================================
int main(int argc, char* argv[])
       {
       unsigned short        i;
       struct tagTicTacToes *p;

       p = new struct tagTicTacToes;

       p->Value                = 0x00000000;
       p->NumberOfChildren        = 0;
       p->NextSibling        = NULL;

       Levels[0]                = p;

       for( i = 0; i < 10; i++ )
               {
               NodesLevel = 0;
               printf( "\n\nLevel %u\n", i + 1 );
               for( p = Levels[i]; p; p = p->NextSibling )
                       if( !Finished( p->Value ))
                               GenerateChildren( p, i + 1 );
                       else
                               {
                               printf( " Finished" );
                               }
               printf( "\nNodes in level: %lu", NodesLevel );
               }

       Report();

       return 0;
       }
//==============================================================================

part 3 197 bytes content-type:text/plain; name="ATT00001.txt"
(decoded base64)

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2016\09\04@041545 by Justin Richards

face picon face
Hi Issac,

thanks for sharing.

This looked like a good candidate for me to GCC for the first time.

So installed ubuntu (as a vm).

Then tried gcc TicTacToes.cpp Compiler complained so installed g++ (after
googling the issue)

then g++ TicTacToes.cpp compliler complained with conio.h

found and dowloaded conio.h and placed in /usr/include

compiler complains with _mingw.h missing

Should I be trying this within cygwin under windows.

Perhaps I can modify code to compile within ubuntu.

I am looking for path of least resistance, so perhaps if you can recall the
platform that you originally compiled, then I could start from there.

Cheers Justin






On 4 September 2016 at 11:55, Isaac M. Bavaresco <.....isaacbavarescoKILLspamspam@spam@gmail.com>
wrote:

{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\04@073738 by Isaac M. Bavaresco

picon face
Hi Justin,

The conio.h is DOS/Windows only. You could probably remove the #include,
then some function calls may generate errors. Just replace those
functions with their Linux equivalents.

Cheers,
Isaac



Em 04/09/2016 05:15, Justin Richards escreveu:
{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\04@074435 by Isaac M. Bavaresco

picon face
part 1 2115 bytes content-type:text/plain; charset="Windows-1252" (decoded quoted-printable)

Justin,

The conio.h header file is not even necessary, just comment it out and
it will compile OK.

I also converted the file from CPP to C. It was a matter of just
changing the extension and replace the two 'new' operators with calls to
'malloc'. It took just the time between my last reply and this one to
change and test.

See the attached file.

Cheers,

Isaac



Em 04/09/2016 05:15, Justin Richards escreveu:
{Quote hidden}


part 2 9461 bytes content-type:text/plain; name="TicTacToes.c"
(decoded base64)

//==============================================================================
// Copyright (c) 2008, Isaac Marino Bavaresco
// All rights reserved
// EraseMEisaacbavarescospam_OUTspamTakeThisOuTyahoo.com.br
//==============================================================================
// This program generates all possible sequences for the game Tic-Tac-Toes.
// Definitions:
//        State:
//                Each one of the possible states that the game board may assume during the game.
//                Each state receives one unique VALUE, which is represented by a 18 bit number
//                (stored in 32 bit variables). Each cell is represented by two bits which may
//                assume three different values: 0x = empty, 11 = X, 10 = O
//
//                The theoretical maximum number of states is 3 ** 9 = 19683, but most are invalid states
//                ( all positions occupied by the same symbol, for instance), leaving 772 valid
//                different states.
//                For optimization, the program eliminates the states which are equivalent after
//                rotation or mirroring and considers them all the same state. This way, we may
//                reduce the number of different states by up to 1/8.
//
//
//==============================================================================
#define WIN32_LEAN_AND_MEAN                // Exclude rarely-used stuff from Windows headers
//==============================================================================
#include
#include
//#include
//==============================================================================
struct tagTicTacToes
       {
       unsigned long        Value;
       unsigned long        Id;
       unsigned short        NumberOfChildren;
       struct tagTicTacToes        *NextSibling;
       struct tagTicTacToes        *Children[8];

       };
//==============================================================================
struct tagTicTacToes *Levels[11] = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
struct tagTicTacToes *LastInserted = NULL;

unsigned long        TotalNodes        = 0;
unsigned long        NodesLevel        = 0;
//==============================================================================
unsigned short Finished( unsigned long Value )
       {
       unsigned long Aux;
       unsigned short i;

       unsigned long Mask1[] =
               {
               0x0000003f, // 0000 0000 0000 0000 0000 0000 0011 1111
               0x00000fc0, // 0000 0000 0000 0000 0000 ffff 1100 0000
               0x0003f000, // 0000 0000 0000 0011 1111 0000 0000 0000

               0x000030c3, // 0000 0000 0000 0000 0011 0000 1100 0011
               0x0000c30c, // 0000 0000 0000 0000 1100 0011 0000 1100
               0x00030c30, // 0000 0000 0000 0011 0000 1100 0011 0000

               0x00030303, // 0000 0000 0000 0011 0000 0011 0000 0011
               0x00003330, // 0000 0000 0000 0000 0011 0011 0011 0000
               };

       unsigned long Mask2[] =
               {
               0x0000002a, // 0000 0000 0000 0000 0000 0000 0010 1010
               0x00000a80, // 0000 0000 0000 0000 0000 1010 1000 0000
               0x0002a000, // 0000 0000 0000 0010 1010 0000 0000 0000

               0x00002082, // 0000 0000 0000 0000 0010 0000 1000 0010
               0x00008208, // 0000 0000 0000 0000 1000 0010 0000 1000
               0x00020820, // 0000 0000 0000 0010 0000 1000 0010 0000

               0x00030303, // 0000 0000 0000 0010 0000 0010 0000 0010
               0x00003330, // 0000 0000 0000 0000 0010 0010 0010 0000
               };

       for( i = 0; i < sizeof Mask1 / sizeof Mask1[0]; i++ )
               {
               Aux = Value & Mask1[i];
               if( Aux == Mask1[i] )
                       return 1;
               else if( Aux == Mask2[i] )
                       return 2;
               }
       return 0;
       }
//==============================================================================
unsigned long Mirror( unsigned long Value )
       {
       unsigned long Result;

       Result        = Value                                & 0x0000c30c;
       Result  |= ( Value << 4 )        & 0x00030c30;
       Result  |= ( Value >> 4 )        & 0x000030c3;

       return Result;
       }
//==============================================================================
unsigned long Rotate( unsigned long Value )
       {
       unsigned long Result;

       Result        = Value                                & 0x00000300;
       Result  |= ( Value << 4 )        & 0x0000c030;
       Result  |= ( Value >> 4 )        & 0x0000300c;
       Result  |= ( Value << 8 )        & 0x00000c00;
       Result  |= ( Value >> 8 )        & 0x000000c0;
       Result  |= ( Value << 12 )        & 0x00030000;
       Result  |= ( Value >> 12 )        & 0x00000003;

       return Result;
       }
//==============================================================================
void GenerateEquivalents( unsigned long Value, unsigned long *Equivalents )
       {
       unsigned short i;
       unsigned long Temp;

       Equivalents[0] = Temp = Value;
       for( i = 1; i < 4; i++ )
               Equivalents[i] = Temp = Rotate( Temp );
       Equivalents[4] = Temp = Mirror( Value );
       for( i = 5; i < 8; i++ )
               Equivalents[i] = Temp = Rotate( Temp );
       }
//==============================================================================
unsigned short SearchArray( unsigned long *Equivalents, unsigned long *Children, unsigned short NumberOfChildren )
       {
       unsigned short i, j;

       for( i = 0; i < NumberOfChildren; i++ )
               for( j = 0; j < 8; j++ )
                       if( Children[i] == Equivalents[j] )
                               return 1;
       return 0;
       }
//==============================================================================
struct tagTicTacToes *SearchTree( unsigned long *Equivalents, unsigned short Level )
       {
       unsigned short i;
       struct tagTicTacToes *p;


       for( p = Levels[Level]; p; p = p->NextSibling )
               for( i = 0; i < 8; i++ )
                       if( Equivalents[i] == p->Value )
                               return p;

       return NULL;
       }
//==============================================================================
struct tagTicTacToes *InsertChild( unsigned long Value, unsigned short Level, struct tagTicTacToes *Parent )
       {
       struct tagTicTacToes *p;

       p = (struct tagTicTacToes*)malloc( sizeof( struct tagTicTacToes ));

       p->Value                = Value;
       p->NumberOfChildren        = 0;
       p->Id                        = TotalNodes;
       p->NextSibling        = NULL;

       Parent->Children[Parent->NumberOfChildren]        = p;
       Parent->NumberOfChildren++;


       if( Levels[Level] )
               LastInserted->NextSibling = p;
       else
               Levels[Level] = p;

       LastInserted = p;

       return p;
       }
//==============================================================================
struct tagTicTacToes *ConnectChild( struct tagTicTacToes *p, struct tagTicTacToes *Parent )
       {
       Parent->Children[Parent->NumberOfChildren]        = p;
       Parent->NumberOfChildren++;

       return NULL;
       }
//==============================================================================
void GenerateChildren( struct tagTicTacToes *Parent, unsigned short Level )
       {
       struct tagTicTacToes        *p;
       unsigned short        i, NumberOfChildren;
       unsigned long        Mask, Bits, Aux, Value;
       unsigned long        Equivalents[8], Children[9];

       Value                        = Parent->Value;
       Mask                        = 0x00000002;
       Bits                        = Level & 0x00000001;
       NumberOfChildren        = 0;

       for( i = 0; i < 9; i++, Mask        <<= 2, Bits        <<= 2 )
               {
               if( !( Value & Mask ))
                       {
                       Aux = Value | Mask | Bits;
                       GenerateEquivalents( Aux, Equivalents );
                       if( !SearchArray( Equivalents, Children, NumberOfChildren ))
                               {
                               Children[NumberOfChildren] = Aux;
                               NumberOfChildren++;
                               p = SearchTree( Equivalents, Level );
                               if( p )
                                       ConnectChild( p, Parent );
                               else
                                       {
                                       InsertChild( Aux, Level, Parent );
                                       TotalNodes++;
                                       NodesLevel++;
                                       printf( "\rNode Id: %lu", TotalNodes - 1 );
                                       }
                               }
                       }
               }
       }
//==============================================================================
void ShowMark( unsigned long Value )
       {
       printf( "%c", Value & 2 ? ( Value & 1 ? 'X' : 'O'  ) : ' ' );
       }

//==============================================================================
void Print( unsigned long Value )
       {
       ShowMark( Value );
       printf( "%c", '|' );
       ShowMark( Value >> 2 );
       printf( "%c", '|' );
       ShowMark( Value >> 4 );
       printf( "\n-+-+-\n" );
       ShowMark( Value >> 6 );
       printf( "%c", '|' );
       ShowMark( Value >> 8 );
       printf( "%c", '|' );
       ShowMark( Value >> 10 );
       printf( "\n-+-+-\n" );
       ShowMark( Value >> 12 );
       printf( "%c", '|' );
       ShowMark( Value >> 14 );
       printf( "%c", '|' );
       ShowMark( Value >> 16 );
       printf( "\n\n" );
       }
//==============================================================================
void Report( void )
       {
       struct tagTicTacToes        *p;
       unsigned short        i, j, Aux;


       for( i = 1; i < 10; i++ )
               {
               printf( "\nLevel: %u\n", i );
               for( p = Levels[i]; p; p = p->NextSibling )
                       {
                       printf( "\nId: %3u Value: %05X Children(%u): ", p->Id, p->Value, p->NumberOfChildren );
                       for( j = 0; j < p->NumberOfChildren; j++ )
                               printf( "%3u ", p->Children[j]->Id );
                       Aux = Finished( p->Value );
                       if( Aux == 0 )
                               printf( "\n\n" );
                       else if( Aux == 1 )
                               printf( "\n**** Victory of X ****\n" );
                       else if( Aux == 2 )
                               printf( "\n**** Victory of O ****\n" );
                       Print( p->Value );
                       }
               }
       }
//==============================================================================
int main(int argc, char* argv[])
       {
       unsigned short        i;
       struct tagTicTacToes *p;

       p = (struct tagTicTacToes*)malloc( sizeof( struct tagTicTacToes ));

       p->Value                = 0x00000000;
       p->NumberOfChildren        = 0;
       p->NextSibling        = NULL;

       Levels[0]                = p;

       for( i = 0; i < 10; i++ )
               {
               NodesLevel = 0;
               printf( "\n\nLevel %u\n", i + 1 );
               for( p = Levels[i]; p; p = p->NextSibling )
                       if( !Finished( p->Value ))
                               GenerateChildren( p, i + 1 );
                       else
                               {
                               printf( " Finished" );
                               }
               printf( "\nNodes in level: %lu", NodesLevel );
               }

       Report();

       return 0;
       }
//==============================================================================

part 3 197 bytes content-type:text/plain; name="ATT00001.txt"
(decoded base64)

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2016\09\04@081739 by Justin Richards

face picon face
Thanks Issac,

much appreciated.

Cheers Justin

On 4 September 2016 at 19:44, Isaac M. Bavaresco <isaacbavarescospamspam_OUTgmail.com>
wrote:

{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\04@082822 by Isaac M. Bavaresco

picon face
Justin,

This program was written under Windows XP and compiled with GCC = MinGW
= TDM-GCC ( <http://tdm-gcc.tdragon.net> ).
To write and build the code I use Code::Blocks, that is a multi-platform
IDE available for Windows, UNIX/Linux and Mac.

Cheers,
Isaac



Em 04/09/2016 05:15, Justin Richards escreveu:
{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\04@083540 by Justin Richards

face picon face
Issac,

you read my mind.  I was still pondering what platform was used.

I am not familiar with GCC but assumed it was native (for want of a better
word)  to linux.

Cheers Justin



On 4 September 2016 at 20:28, Isaac M. Bavaresco <RemoveMEisaacbavarescoTakeThisOuTspamgmail.com>
wrote:

{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\04@094933 by Isaac M. Bavaresco

picon face
part 1 3319 bytes content-type:text/plain; charset="Windows-1252" (decoded quoted-printable)

Justin,

I found a bug that prevented the detection of some 'O' wins. The
corrected file is attached.

Cheers,

Isaac



Em 04/09/2016 09:35, Justin Richards escreveu:
{Quote hidden}


part 2 9439 bytes content-type:text/plain; name="TicTacToes.c"
(decoded base64)

//==============================================================================
// Copyright (c) 2008, Isaac Marino Bavaresco
// All rights reserved
// isaacbavarescoEraseMEspam.....yahoo.com.br
//==============================================================================
// This program generates all possible sequences for the game Tic-Tac-Toes.
// Definitions:
//        State:
//                Each one of the possible states that the game board may assume during the game.
//                Each state receives one unique VALUE, which is represented by a 18 bit number
//                (stored in 32 bit variables). Each cell is represented by two bits which may
//                assume three different values: 0x = empty, 11 = X, 10 = O
//
//                The theoretical maximum number of states is 3 ** 9 = 19683, but most are invalid states
//                ( all positions occupied by the same symbol, for instance), leaving 772 valid
//                different states.
//                For optimization, the program eliminates the states which are equivalent after
//                rotation or mirroring and considers them all the same state. This way, we may
//                reduce the number of different states by up to 1/8.
//
//
//==============================================================================
#define WIN32_LEAN_AND_MEAN                // Exclude rarely-used stuff from Windows headers
//==============================================================================
#include
#include
//==============================================================================
struct tagTicTacToes
       {
       unsigned long        Value;
       unsigned long        Id;
       unsigned short        NumberOfChildren;
       struct tagTicTacToes        *NextSibling;
       struct tagTicTacToes        *Children[8];

       };
//==============================================================================
struct tagTicTacToes *Levels[11] = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
struct tagTicTacToes *LastInserted = NULL;

unsigned long        TotalNodes        = 0;
unsigned long        NodesLevel        = 0;
//==============================================================================
unsigned short Finished( unsigned long Value )
       {
       unsigned long Aux;
       unsigned short i;

       unsigned long Mask1[] =
               {
               0x0000003f, // 0000 0000 0000 0000 0000 0000 0011 1111
               0x00000fc0, // 0000 0000 0000 0000 0000 1111 1100 0000
               0x0003f000, // 0000 0000 0000 0011 1111 0000 0000 0000

               0x000030c3, // 0000 0000 0000 0000 0011 0000 1100 0011
               0x0000c30c, // 0000 0000 0000 0000 1100 0011 0000 1100
               0x00030c30, // 0000 0000 0000 0011 0000 1100 0011 0000

               0x00030303, // 0000 0000 0000 0011 0000 0011 0000 0011
               0x00003330, // 0000 0000 0000 0000 0011 0011 0011 0000
               };

       unsigned long Mask2[] =
               {
               0x0000002a, // 0000 0000 0000 0000 0000 0000 0010 1010
               0x00000a80, // 0000 0000 0000 0000 0000 1010 1000 0000
               0x0002a000, // 0000 0000 0000 0010 1010 0000 0000 0000

               0x00002082, // 0000 0000 0000 0000 0010 0000 1000 0010
               0x00008208, // 0000 0000 0000 0000 1000 0010 0000 1000
               0x00020820, // 0000 0000 0000 0010 0000 1000 0010 0000

               0x00020202, // 0000 0000 0000 0010 0000 0010 0000 0010
               0x00002220, // 0000 0000 0000 0000 0010 0010 0010 0000
               };

       for( i = 0; i < sizeof Mask1 / sizeof Mask1[0]; i++ )
               {
               Aux = Value & Mask1[i];
               if( Aux == Mask1[i] )
                       return 1;
               else if( Aux == Mask2[i] )
                       return 2;
               }
       return 0;
       }
//==============================================================================
unsigned long Mirror( unsigned long Value )
       {
       unsigned long Result;

       Result        = Value                                & 0x0000c30c;
       Result  |= ( Value << 4 )        & 0x00030c30;
       Result  |= ( Value >> 4 )        & 0x000030c3;

       return Result;
       }
//==============================================================================
unsigned long Rotate( unsigned long Value )
       {
       unsigned long Result;

       Result        = Value                                & 0x00000300;
       Result  |= ( Value << 4 )        & 0x0000c030;
       Result  |= ( Value >> 4 )        & 0x0000300c;
       Result  |= ( Value << 8 )        & 0x00000c00;
       Result  |= ( Value >> 8 )        & 0x000000c0;
       Result  |= ( Value << 12 )        & 0x00030000;
       Result  |= ( Value >> 12 )        & 0x00000003;

       return Result;
       }
//==============================================================================
void GenerateEquivalents( unsigned long Value, unsigned long *Equivalents )
       {
       unsigned short i;
       unsigned long Temp;

       Equivalents[0] = Temp = Value;
       for( i = 1; i < 4; i++ )
               Equivalents[i] = Temp = Rotate( Temp );
       Equivalents[4] = Temp = Mirror( Value );
       for( i = 5; i < 8; i++ )
               Equivalents[i] = Temp = Rotate( Temp );
       }
//==============================================================================
unsigned short SearchArray( unsigned long *Equivalents, unsigned long *Children, unsigned short NumberOfChildren )
       {
       unsigned short i, j;

       for( i = 0; i < NumberOfChildren; i++ )
               for( j = 0; j < 8; j++ )
                       if( Children[i] == Equivalents[j] )
                               return 1;
       return 0;
       }
//==============================================================================
struct tagTicTacToes *SearchTree( unsigned long *Equivalents, unsigned short Level )
       {
       unsigned short i;
       struct tagTicTacToes *p;


       for( p = Levels[Level]; p; p = p->NextSibling )
               for( i = 0; i < 8; i++ )
                       if( Equivalents[i] == p->Value )
                               return p;

       return NULL;
       }
//==============================================================================
struct tagTicTacToes *InsertChild( unsigned long Value, unsigned short Level, struct tagTicTacToes *Parent )
       {
       struct tagTicTacToes *p;

       p = (struct tagTicTacToes*)malloc( sizeof( struct tagTicTacToes ));

       p->Value                = Value;
       p->NumberOfChildren        = 0;
       p->Id                        = TotalNodes;
       p->NextSibling        = NULL;

       Parent->Children[Parent->NumberOfChildren]        = p;
       Parent->NumberOfChildren++;


       if( Levels[Level] )
               LastInserted->NextSibling = p;
       else
               Levels[Level] = p;

       LastInserted = p;

       return p;
       }
//==============================================================================
struct tagTicTacToes *ConnectChild( struct tagTicTacToes *p, struct tagTicTacToes *Parent )
       {
       Parent->Children[Parent->NumberOfChildren]        = p;
       Parent->NumberOfChildren++;

       return NULL;
       }
//==============================================================================
void GenerateChildren( struct tagTicTacToes *Parent, unsigned short Level )
       {
       struct tagTicTacToes        *p;
       unsigned short        i, NumberOfChildren;
       unsigned long        Mask, Bits, Aux, Value;
       unsigned long        Equivalents[8], Children[9];

       Value                        = Parent->Value;
       Mask                        = 0x00000002;
       Bits                        = Level & 0x00000001;
       NumberOfChildren        = 0;

       for( i = 0; i < 9; i++, Mask        <<= 2, Bits        <<= 2 )
               {
               if( !( Value & Mask ))
                       {
                       Aux = Value | Mask | Bits;
                       GenerateEquivalents( Aux, Equivalents );
                       if( !SearchArray( Equivalents, Children, NumberOfChildren ))
                               {
                               Children[NumberOfChildren] = Aux;
                               NumberOfChildren++;
                               p = SearchTree( Equivalents, Level );
                               if( p )
                                       ConnectChild( p, Parent );
                               else
                                       {
                                       InsertChild( Aux, Level, Parent );
                                       TotalNodes++;
                                       NodesLevel++;
                                       printf( "\rNode Id: %lu", TotalNodes - 1 );
                                       }
                               }
                       }
               }
       }
//==============================================================================
void ShowMark( unsigned long Value )
       {
       printf( "%c", Value & 2 ? ( Value & 1 ? 'X' : 'O'  ) : ' ' );
       }

//==============================================================================
void Print( unsigned long Value )
       {
       ShowMark( Value );
       printf( "%c", '|' );
       ShowMark( Value >> 2 );
       printf( "%c", '|' );
       ShowMark( Value >> 4 );
       printf( "\n-+-+-\n" );
       ShowMark( Value >> 6 );
       printf( "%c", '|' );
       ShowMark( Value >> 8 );
       printf( "%c", '|' );
       ShowMark( Value >> 10 );
       printf( "\n-+-+-\n" );
       ShowMark( Value >> 12 );
       printf( "%c", '|' );
       ShowMark( Value >> 14 );
       printf( "%c", '|' );
       ShowMark( Value >> 16 );
       printf( "\n\n" );
       }
//==============================================================================
void Report( void )
       {
       struct tagTicTacToes        *p;
       unsigned short        i, j, Aux;


       for( i = 1; i < 10; i++ )
               {
               printf( "\nLevel: %u\n", i );
               for( p = Levels[i]; p; p = p->NextSibling )
                       {
                       printf( "\nId: %3u Value: %05X Children(%u): ", p->Id, p->Value, p->NumberOfChildren );
                       for( j = 0; j < p->NumberOfChildren; j++ )
                               printf( "%3u ", p->Children[j]->Id );
                       Aux = Finished( p->Value );
                       if( Aux == 0 )
                               printf( "\n\n" );
                       else if( Aux == 1 )
                               printf( "\n**** Victory of X ****\n" );
                       else if( Aux == 2 )
                               printf( "\n**** Victory of O ****\n" );
                       Print( p->Value );
                       }
               }
       }
//==============================================================================
int main(int argc, char* argv[])
       {
       unsigned short        i;
       struct tagTicTacToes *p;

       p = (struct tagTicTacToes*)malloc( sizeof( struct tagTicTacToes ));

       p->Value                = 0x00000000;
       p->NumberOfChildren        = 0;
       p->NextSibling        = NULL;

       Levels[0]                = p;

       for( i = 0; i < 10; i++ )
               {
               NodesLevel = 0;
               printf( "\n\nLevel %u\n", i + 1 );
               for( p = Levels[i]; p; p = p->NextSibling )
                       if( !Finished( p->Value ))
                               GenerateChildren( p, i + 1 );
                       else
                               {
                               printf( " Finished" );
                               }
               printf( "\nNodes in level: %lu", NodesLevel );
               }

       Report();

       return 0;
       }
//==============================================================================

part 3 197 bytes content-type:text/plain; name="ATT00001.txt"
(decoded base64)

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2016\09\04@213918 by RussellMc

face picon face

On 4 September 2016 at 23:44, Isaac M. Bavaresco <EraseMEisaacbavarescospamgmail.com>
wrote:

> Justin,
>
> >
>
> ​
> It took just the time between my last reply and this one to

change and test.
>

​7 minutes +/- (trans-internet + any-requisite-hyper-space-jumps).


          Russell​
--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2016\09\04@224245 by Richard Pope

picon face

Russell and et al,
    When I got my VIC-20 in 1982, one of the first programs that I
typed in was a Tic-Tac-Toe game. I believe that it was in one of the
Compute books.
Thanks,
rich!

On 9/4/2016 8:38 PM, RussellMc wrote:
{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2016\09\05@054257 by Justin Richards

face picon face
Latest version compiles and runs.

Great example code for me to digest.

Thanks

Justin

On 4 September 2016 at 21:49, Isaac M. Bavaresco <RemoveMEisaacbavarescospam_OUTspamKILLspamgmail.com>
wrote:

{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\05@083817 by Isaac M. Bavaresco

picon face

Richard,

My code is not a Tic-Tac-Toes  "game", it is an analyzer that shows all
the possible game sequences with every possible "X wins", "O wins" and ties.

I also wrote a similar analyzer for the game Peg Solitaire, but I don't
remember if it I got it right, but it is out of the computing and memory
capacity for a normal computer anyway.

Cheers,

Isaac




Em 04/09/2016 23:42, Richard Pope escreveu:
{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2016\09\05@211750 by Bob Ammerman

flavicon
face
> I also wrote a similar analyzer for the game Peg Solitaire, but I don't remember
> if it I got it right, but it is out of the computing and memory capacity for a
> normal computer anyway.
>
> Isaac

Over the years I have written a complete 'solver' for 15-peg solitaire. The first version that could solve the whole game ran on an IBM 370 (model 3083) which was a huge mainframe. Took about 1hr of CPU hand crafted in assembly language.

The current version is C under windows. It runs to completion in seconds even when extended from 15 to 21 pegs by adding another row.

-- Bob Ammerman
RAm Systems






-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\05@213239 by Isaac M. Bavaresco

picon face
Em 05/09/2016 22:17, Bob Ammerman escreveu:
>> I also wrote a similar analyzer for the game Peg Solitaire, but I don't remember
>> if it I got it right, but it is out of the computing and memory capacity for a
>> normal computer anyway.
>>
>> Isaac
> Over the years I have written a complete 'solver' for 15-peg solitaire. The first version that could solve the whole game ran on an IBM 370 (model 3083) which was a huge mainframe. Took about 1hr of CPU hand crafted in assembly language.
>
> The current version is C under windows. It runs to completion in seconds even when extended from 15 to 21 pegs by adding another row.
>
> -- Bob Ammerman
> RAm Systems

I think I was overestimating the 32 Peg Solitaire complexity.
I didn't know that Wikipedia had a page about it. It seems that the
maximum possible (reachable) states is around 23,475,688 of a
mathematical maximum of 187,636,299, so calculating all those states is
possible.

Cheers,
Isaac
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\06@070458 by Bob Ammerman

flavicon
face
32 pegs? What pattern?

~ Bob Ammerman
RAm Systems

> -----Original Message-----
> From: piclist-bouncesSTOPspamspamspam_OUTmit.edu [spamBeGonepiclist-bouncesSTOPspamspamEraseMEmit.edu] On Behalf
Of
{Quote hidden}

The
> first version that could solve the whole game ran on an IBM 370 (model
3083)
> which was a huge mainframe. Took about 1hr of CPU hand crafted in assembly
> language.
> >
> > The current version is C under windows. It runs to completion in seconds
even
> when extended from 15 to 21 pegs by adding another row.
> >
> > -- Bob Ammerman
> > RAm Systems
>
> I think I was overestimating the 32 Peg Solitaire complexity.
> I didn't know that Wikipedia had a page about it. It seems that the
maximum
> possible (reachable) states is around 23,475,688 of a mathematical maximum
> of 187,636,299, so calculating all those states is possible.
>
> Cheers,
> Isaac
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change
> your membership options at http://mailman.mit.edu/mailman/listinfo/piclist

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2016\09\06@073447 by Bob Ammerman

flavicon
face
> 32 pegs? What pattern?
>
> ~ Bob Ammerman
> RAm Systems

Never mind... figured it out. Cross with 3x3 in center, 2x3 on each arm.

~ Bob Ammerman
RAm Systems

> {Original Message removed}

2016\09\06@074224 by Isaac M. Bavaresco

picon face
It's the only size and layout I knew until two days ago.
Many years ago my mother discovered a perfect solution (finishing with
just one peg in the center) and I memorized it. Now I can solve it every
time.

Let's try some ASCII art:

 OOO
 OOO
OOOOOOO
OOO.OOO
OOOOOOO
 OOO
 OOO



Em 06/09/2016 08:04, Bob Ammerman escreveu:
> 32 pegs? What pattern?
>
> ~ Bob Ammerman
> RAm Systems
>
>> {Original Message removed}

2016\09\06@173947 by Denny Esterline

picon face
>
>
> My code is not a Tic-Tac-Toes  "game", it is an analyzer that shows all
> the possible game sequences with every possible "X wins", "O wins" and
> ties.
>
>
Obligatory XKCD reference

https://xkcd.com/832/

-Denny
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

More... (looser matching)
- Last day of these posts
- In 2016 , 2017 only
- Today
- New search...