/* cellc.c -- Version of 'cellb2' working with "#n" (where n is a real > 0.0) instead of "#Good"/"#Bad". MR 28/12/99 Compile & link: gcc -c sym.c gcc cellc.c sym.o -o cellc -lm ---------------------------------------------------------------------- Copyright (C) 1999 Menno Rubingh This source code / program is free software; you are allowed to redistribute it and/or to modify it under the terms of the GNU Public Licence (GNU GPL) as published by the Free Software Foundation. See the file 'COPYING' which should have accompanied this source file. This program comes with ABSOLUTELY NO WARRANTY. ---------------------------------------------------------------------- */ #include #include #include #include #include #include typedef int _bool; #include "sym.h" #define SYM_DOT 1 //Single dot "." #define SYM_QUE 2 //Question mark "?" /* -------------------------------------------------------------------- */ // // Bit-mask stuff. // // A '_word' data type is an unsigned integer used as a ''bit mask''. // Each individual bit in it represents one ''symbol'' in an array of sym_t, // the ''symbol array'', which has exactly as much elements as there are // bits in a '_word'. Empty slots in this array contain the value // (sym_t)0 (= an ''all-blank'' symbol). // // The leftmost bit in the _word corresponds to the 1st element in the // symbol array. // // Note: A sym_t is just a handy way to compactly store a *name* // consisting only of a few printing characters. (I.e., the functionality // is a sym_t is the same as that of an ordinary character string.) // typedef unsigned long _word; //Used for bit ''masks''. #define WORD_NBITS 32 #if ( ULONG_MAX != 4294967295U ) #error "This code assumes 32-bit 'unsigned long'" #endif #define WORD_MASKBIT1 0x80000000 //Bit mask with only leftmost bit high. #define WORD_MASKALL 0xffffffff //Bit mask with ALL bits high. // // Symbol array mgmt funcs, and funcs for operations on '_word's. // // Note: Most operations on '_word's are just simply the built-in bitwise // operations in C. // #if 0 //Unnecessary -- simply use initializator statement in // declaration of the actual instance of the array. void sa_init( sym_t sa[WORD_NBITS] ) //Initialize each sa element as a blank/zero sym_t value. { int i; for ( i = 0; i < WORD_NBITS; i++ ) { sa[i] = 0; } } #endif _word sa_sym2word( sym_t sa[WORD_NBITS], sym_t sym1 ) //Lookup sym1 in sa[]. Return a _word with the appropriate single // bit high if sym1 found in sa[]; return an all-zero bit _word if // not found. { _word mask = WORD_MASKBIT1; int i; assert ( sym1 != 0 ); for ( i = 0; i < WORD_NBITS; i++ ) { if ( sa[i] == sym1 ) { return mask; } mask = ( mask >> 1 ); } return 0U; //Not found } _word sa_inssym( sym_t sa[WORD_NBITS], sym_t sym1 ) //Insert sym1 if not already there. Return 0 on failure: e.g. // when sa[] array already full. If sym1 was already in sa[], // and also if sym1 wasn't present yet and was inserted now, then // then return the corresponding word with one bit high. { _word mask = WORD_MASKBIT1; int i; _word mask_1stempty; int i_1stempty = -1; assert ( sym1 != 0 ); for ( i = 0; i < WORD_NBITS; i++ ) { if ( sa[i] == sym1 ) { return mask; } if ( i_1stempty == -1 && sa[i] == 0 ) { i_1stempty = i; mask_1stempty = mask; } mask = ( mask >> 1 ); } //Not found, so now try to insert: if ( i_1stempty == -1 ) { return 0U; /*Failure: Already full*/ } sa[i_1stempty] = sym1; return mask_1stempty; } sym_t sa_word2sym( sym_t sa[WORD_NBITS], _word word1 ) //Return the sym_t corresponding with the first high bit in // word1 from the left. Return (sym_t)0 if not found or if // no bit high in word1. { _word mask = WORD_MASKBIT1; int i; for ( i = 0; i < WORD_NBITS; i++ ) { if ( ( word1 & mask ) != 0U ) { return sa[i]; } mask = ( mask >> 1 ); } return 0; //Not found } _word sa_aggregate( sym_t sa[WORD_NBITS] ) //Return a bit mask with all bits high corresponding with // symbols present in sa[]. { _word rv = 0U; _word mask = WORD_MASKBIT1; int i; for ( i = 0; i < WORD_NBITS; i++ ) { if ( sa[i] != 0 ) { rv |= mask; } mask = ( mask >> 1 ); } return rv; } void sa_print( sym_t sa[WORD_NBITS] ) //Print all symbols currently stored in sa[]. { int i; for ( i = 0; i < WORD_NBITS; i++ ) { if ( sa[i] != 0 ) { printf( "%s ", sym2str( sa[i] ) ); } } } void sa_printword1( sym_t sa[WORD_NBITS], _word word1 ) //Print on stdout all symbols (names) corresponding to // high bits in word1. Print "-" for each high bit when // the sa[] array does not contain a symbol in the // slot corresponding with that bit. { _word mask = WORD_MASKBIT1; int i; for ( i = 0; i < WORD_NBITS; i++ ) { if ( ( word1 & mask ) != 0U ) { printf( "%s ", ( sa[i] == 0 ? "-" : sym2str( sa[i] ) ) ); } mask = ( mask >> 1 ); } } void sa_printword2( sym_t sa[WORD_NBITS], _word word1 ) //Print on stdout all symbols present in sa[], and suffix // each symbol with a 0 or 1 according to the value of // the corresponding bit in word1. { _word mask = WORD_MASKBIT1; int i; for ( i = 0; i < WORD_NBITS; i++ ) { if ( sa[i] != 0 ) { printf( "%s%d ", sym2str( sa[i] ), ( word1 & mask ) != 0U ); } mask = ( mask >> 1 ); } } /* -------------------------------------------------------------------- */ /* -------------------------------------------------------------------- */ static int n_rand( unsigned int m ) /* Return random integer in [ 0, m ) */ { unsigned int K = ((unsigned int)RAND_MAX + m) / m; return ( rand() / K ); } double f_rand( double max ) //Return a ''double'' random number in interval [ 0.0, max ]. { return ( max * (double)rand() / RAND_MAX ); } /* -------------------------------------------------------------------- */ /* -------------------------------------------------------------------- */ /* ''BC'' data type -- for Brain cells. */ typedef struct BC_tag { _word r; /*Receivers*/ sym_t s; /*Sender symbol*/ double prio; struct BC_tag * pnext; } bc_t; /* -------------------------------------------------------------------- */ bc_t * bc_new( _word r, sym_t s ) //Return PTR to newly allocated bc_t cell with a // receiver _word r and sender symbol s. //Return NULL on alloc failure. // New BC has prio == 1.0. { bc_t * pnew = (bc_t *)malloc( sizeof(bc_t) ); if ( pnew != NULL ) { pnew->r = r; pnew->s = s; pnew->prio = 1.0; pnew->pnext = NULL; } return pnew; } // Arg. 'pp' is address of PTR of 1st element of list // (PTR = NULL if list empty). void bclist_insertattop( bc_t ** pp, int * pncells, bc_t * pbc ) //Insert existing cell pbc at top of list 'pp'. { assert( pp != NULL ); pbc->pnext = *pp; *pp = pbc; (*pncells)++; } void bclist_appendatend( bc_t ** pp, int * pncells, bc_t * pbc ) //Append existing cell pbc at end of list. { assert( pp != NULL ); while ( *pp != NULL ) { pp = &( (*pp)->pnext ); } *pp = pbc; pbc->pnext = NULL; (*pncells)++; } void bclist_appendlist( bc_t ** pp, int * pncells, bc_t * plistapp, int napp ) //Append list 'plistapp' to the end of list 'pp'. // 'plistapp' is a PTR to the 1st element of the list to be // appended. { assert( pp != NULL ); while ( *pp != NULL ) { pp = &( (*pp)->pnext ); } *pp = plistapp; (*pncells) += napp; } void bc_print( const bc_t * pbc, sym_t sa[WORD_NBITS] /*sensor symbol array*/ ) { assert( pbc != NULL ); printf( "( " ); sa_printword2( sa, pbc->r ); printf( "; %s ) %g \n", sym2str(pbc->s), pbc->prio ); } void bclist_dump( const bc_t * p1, sym_t sa[WORD_NBITS] /*sensor symbol array*/ ) { for ( ; p1 != NULL; p1 = p1->pnext ) { bc_print( p1, sa ); } } _bool bclist_containsbc( const bc_t * p1, _word r, sym_t s ) { for ( ; p1 != NULL; p1 = p1->pnext ) { if ( p1->r == r && p1->s == s ) { return 1; } } return 0; } #if 0 _bool bclist_containssender( const bc_t * p1, sym_t s ) { for ( ; p1 != NULL; p1 = p1->pnext ) { if ( p1->s == s ) { return 1; } } return 0; } #endif /* -------------------------------------------------------------------- */ bc_t ** bclist_randselectr( bc_t ** ppList1, _word r ) // //Select randomly (according to prio values) ONE of the cells in // ppList1 that has receiver _word equalling r. // //Return address of PTR to selected bc_t cell. //Input 'ppList1' is address of PTR to 1st cell of list. //Return NULL when there are NO cells with receiver symbol r in // the list. { bc_t ** pp; bc_t * p1; _bool yes; double totprio; double rsel; double m; assert( ppList1 != NULL ); // 1) Pass 1: Add prio values of selection candidate cells yes = 0; totprio = 0.0; for ( p1 = *ppList1; p1 != NULL; p1 = p1->pnext ) { if ( p1->r == r ) { yes = 1; totprio += p1->prio; } } if ( !yes ) //No candidates to select from ! { return NULL; } // 2) Get a random number in [0.0, totprio] rsel = f_rand( totprio ); // 3) Pass 2: Get address of the PTR to the selected cell m = 0.0; for( pp = ppList1 ; *pp != NULL ; pp = &( (*pp)->pnext ) ) { if ( (*pp)->r == r ) { m += (*pp)->prio; if ( rsel <= m ) { return pp; } } } assert( 0 ); //It shouldn't be possible to reach here. return NULL; } bc_t * bclist_excise( bc_t ** pp, int * pncells ) //Remove cell from list, but do not de-allocate cell. // 'pp' is address of the PTR to the cell to be removed. // The value of this PTR will be changed to the value // of the field 'pnext' in the excised cell. // Return PTR to excised cell. { bc_t * pExc = *pp; assert( pp != NULL && *pp != NULL ); *pp = pExc->pnext; pExc->pnext = NULL; (*pncells)--; assert( *pncells >= 0 ); return pExc; } /* -------------------------------------------------------------------- */ double upbound( double x, double A ) //Return x limited to upper boundary A. x and A must be >= 0. { return ( A * ( x / ( x + A ) ) ); } #define PRIOMAX 1000.0 //10.0 #define PRIOMIN 1.0e-10 void bclist_mult1stfewbcs( bc_t * p1, double factor1, double alfa ) //Multiply by factor1, and then by factors gradually but // quickly asymptotically approaching 1.0, ALL of the BCs // in the list. //The multiplication factor for BC number i+1 is the weighted // mean (or 'affine combination') of the factor for BC number i // and the constant value 1.0, using the weight 'alfa' : // factor_{i+1} = alfa * factor_{i} + ( 1.0 - alfa ) * 1.0 . { for ( ; p1 != NULL; p1 = p1->pnext ) { p1->prio *= factor1; //Keep prio within [ PRIOMIN, PRIOMAX ): if ( p1->prio < PRIOMIN ) { p1->prio = PRIOMIN; } p1->prio = upbound( p1->prio, PRIOMAX ); //Compute factor to use for the next BC: factor1 = alfa * factor1 + ( 1.0 - alfa ); } } /* -------------------------------------------------------------------- */ _bool bclist_insertreceivers( bc_t ** pp, int * pncells, sym_t motorArray[WORD_NBITS], _word rnew, sym_t sa[WORD_NBITS] /*sensor array, needed only for printing*/ ) //Insert -- as far as these BCs do not yet exist in the list 'pp' -- // BCs with receiver combination 'rnew' for each sender symbol // in motorArray[]. The new BCs inserted by this func. have // 'prio' == 1.0 . //Return 0 on mem.alloc. failure somewhere; return 1 if no // mem.alloc. failure occured. { bc_t * ptmpnew = NULL; //PTR to 1st element of linked list that will temporarily contain // the new BCs. This list will at the end of this func be // appended to the list 'pp'. int ntmp = 0; // # of elements in list 'ptmpnew'. int i; //Add new BCs to list 'ptmpnew': for ( i = 0; i < WORD_NBITS; i++ ) { sym_t msym = motorArray[i]; if ( msym == 0U ) { continue; } //Empty motorArray[] element. if ( ! bclist_containsbc( *pp, rnew, msym ) && ! bclist_containsbc( ptmpnew, rnew, msym ) ) { bc_t * pnew = bc_new( rnew, msym ); if ( pnew == NULL ) { return 0; } bclist_appendatend( &ptmpnew, &ntmp, pnew ); printf( "INS R --> " ); bc_print( pnew, sa ); } } //Append list 'ptmpnew' to list 'pp': bclist_appendlist( pp, pncells, ptmpnew, ntmp ); return 1; } _bool bclist_newmotor( bc_t ** pp, int * pncells, sym_t snew, sym_t sa[WORD_NBITS] /*sensor array, needed only for printing*/ ) //Update the current BC-list 'pp' for the registering of // a new, previously unknown motor with symbol 'snew'. //For each existing BC in list 'pp', add a copy of that BC // using 'snew' as the sender symbol, if such a BC didn't already // exist in the list. The new BCs inserted by this func. have // 'prio' == 1.0 . //Return 0 on mem.alloc. failure somewhere; return 1 on success. { bc_t * ptmpnew = NULL; //PTR to 1st element of linked list that will temporarily contain // the new BCs. This list will at the end of this func be // appended to the list 'pp'. int ntmp = 0; // # of elements in list 'ptmpnew'. bc_t * p1; for ( p1 = *pp; p1 != NULL; p1 = p1->pnext ) { // Add new BC to list 'ptmpnew' if BC not already known: if ( ! bclist_containsbc( *pp, p1->r, snew ) && ! bclist_containsbc( ptmpnew, p1->r, snew ) ) { bc_t * pnew = bc_new( p1->r, snew ); if ( pnew == NULL ) { return 0; } bclist_appendatend( &ptmpnew, &ntmp, pnew ); printf( "INS M --> " ); bc_print( pnew, sa ); } } //Append list 'ptmpnew' to list 'pp': bclist_appendlist( pp, pncells, ptmpnew, ntmp ); return 1; } void bclist_newsensor( bc_t ** pp, _word rnew, _bool sensoron ) //Update the current BC-list 'pp' for the registering of // a new, previously unknown sensor. //'rnew' is a bit mask with exactly one bit high, namely, // the bit corresponding with the new sensor. //'sensoron' is the current ON/OFF state of the new sensor (1 when // the sensor is ON). //For each existing BC in the list 'pp', insert in that existing // BC a new receiver bit for the new sensor. This new bit is // 0 or 1 according to 'sensoron'. Note: This function inserts // NO new BCs into the list. { bc_t * p1; for ( p1 = *pp; p1 != NULL; p1 = p1->pnext ) { if ( sensoron ) { p1->r |= rnew; //Set additional bit high. } } } /* -------------------------------------------------------------------- */ //#define BCCOMBPROB 0.7 //#define BCGENPROB 0.5 _bool do_oneturn( bc_t ** ppAlive1, int * pnAlive1, _bool * pMotorActive, _bool verbose, _word sensorStates, sym_t sarr[WORD_NBITS] /*sensor symbol array*/, sym_t marr[WORD_NBITS] /*motor symbol array*/ ) //Return 1 if at least one cell active. Set *pMotorActive to 1 // if a motor fired. { bc_t ** ppSel; bc_t * pbc; *pMotorActive = 0; // Insert BCs with receiver combination 'sensorStates' and // with all motor symbols as sender symbols as far as these // BCs didn't already exist in the BC list. if ( ! bclist_insertreceivers( ppAlive1, pnAlive1, marr, sensorStates, sarr ) ) { printf( "Mem.alloc failure in bclist_insertreceivers\n" ); return 0; } // Select random choice among all BCs with // r == current sensor state. ppSel = bclist_randselectr( ppAlive1, sensorStates ); if ( ppSel == NULL ) { //Alive list still empty ==> do nothing. printf( "SEL * : Alive list empty\n" ); return 0; } if ( verbose) { printf( "--> " ); bc_print( *ppSel, sarr ); } // Move active (=selected) BC to top of Alive list pbc = bclist_excise( ppSel, pnAlive1 ); printf( "ACTI: " ); bc_print( pbc, sarr ); bclist_insertattop( ppAlive1, pnAlive1, pbc ); // Print ''MOTOR_xxx'' output printf( "MOTOR_%s\n", sym2str(pbc->s) ); *pMotorActive = 1; return 1; } /* -------------------------------------------------------------------- */ // // BC list: // static bc_t * pAlive1 = NULL; static int nAlive1 = 0; // // Sensor array and _word containing the sensor states: // static sym_t saSensor[WORD_NBITS] = { 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0 }; static _word sensorStates = 0U; // // Motor array: // static sym_t saMotor[WORD_NBITS] = { 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0 }; _bool isOKchar( char c ) { return ( ( '0' <= c && c <= '9' ) || ( 'a' <= c && c <= 'z' ) || ( 'A' <= c && c <= 'Z' ) ); } _bool isOKstr( const char * pstr ) { while ( *pstr != '\0' ) { if ( !isOKchar(*pstr++) ) { return 0; } } return 1; } main() { char cmdbuf[80]; srand( time(NULL) ); while ( fgets( cmdbuf, sizeof(cmdbuf), stdin ) && cmdbuf[0] != 'q' ) { _bool ma; bc_t * pnew; int iloop; //Safeguard to prevent infinite loops. #define LOOPMAX 1000 char symbuf[20]; sym_t newsym; _word r; double gbfactor; double alfa; switch( cmdbuf[0] ) { case 'd': //Print number of Brain Cells: printf( "n = %d\n", nAlive1 ); //Print Brain Cells: bclist_dump( pAlive1, saSensor ); printf( "--\n" ); //Print sensor states: sa_printword2( saSensor, sensorStates ); printf( "; " ); //Print names of known motors: sa_print( saMotor ); printf( "\n" ); break; case '1': do_oneturn( &pAlive1, &nAlive1, &ma, 1, sensorStates, saSensor, saMotor ); break; case ' ': //Keep going until a cell changes state. iloop = 0; while ( ! do_oneturn( &pAlive1, &nAlive1, &ma, 0, sensorStates, saSensor, saMotor ) && iloop++ < LOOPMAX ) { ; } break; case '\n': //Keep going until a motor ''fires''. iloop = 0; while ( !( do_oneturn( &pAlive1, &nAlive1, &ma, 0, sensorStates, saSensor, saMotor ) && ma ) && iloop++ < LOOPMAX ) { ; } break; case 'm': //Insert new motor if ( sscanf( cmdbuf+1, "%19s", symbuf ) != 1 || !isOKstr( symbuf ) ) { printf( "??\n" ); break; } newsym = str2sym(symbuf); if ( sa_inssym( saMotor, newsym ) == 0U ) { printf( "MOTOR arr full\n" ); break; } if ( ! bclist_newmotor( &pAlive1, &nAlive1, newsym, saSensor ) ) { printf( "ERR ins Motor\n" ); break; } printf( "OK\n" ); break; case 'a': //Change state (and insert) sensor ('*' for case 'x': // ''all sensors''). if ( sscanf( cmdbuf+1, "%19s", symbuf ) != 1 || ! ( isOKstr( symbuf ) || symbuf[0] == '*' ) ) { printf( "??\n" ); break; } if ( symbuf[0] == '*' )//Change all sensors { if ( cmdbuf[0] == 'x' ) { sensorStates = 0U; } else { sensorStates = sa_aggregate( saSensor ); } printf( "OK\n" ); break; } //Continue with regular case (not '*') //Insert sensor and augment the BC list with // the appropriate BCs if sensor not yet known. newsym = str2sym(symbuf); r = sa_sym2word( saSensor, newsym ); if ( r == 0U ) { r = sa_inssym( saSensor, newsym ); if ( r == 0U ) { printf( "SENSOR arr full\n" ); break; } bclist_newsensor( &pAlive1, r, ( cmdbuf[0] == 'a' ) ); printf( "INS new Sensor-bit OK\n" ); } //Set state of sensor cell if ( cmdbuf[0] == 'x' ) { sensorStates &= (~r); } else { sensorStates |= r; } printf( "OK\n" ); break; #define PHICRIT 0.1 #define NFACT 0.5 //These last two defines say that the relative distance of the // multiplication factor to the asymptote value 1.0 for the BC // halfway (NFACT) the BC list is PHICRIT. That is, with these two // defines you can trim the slope with which the multiplication factor // decays to 1.0 as we walk through the BC list from begin to end. case '#': //Punish or award the Brain Cells active // most recently. if ( sscanf( cmdbuf+1, "%le", &gbfactor ) != 1 || gbfactor <= 0.0 ) { printf( "??\n" ); break; } alfa = 1.0; if ( nAlive1 > 0 ) { alfa = pow( PHICRIT, 1.0 / ( NFACT * nAlive1 ) ); } printf( "alfa = %g\n", alfa ); bclist_mult1stfewbcs( pAlive1, gbfactor, alfa ); printf( "OK\n" ); break; default: //Unrecognized cmd: print always SOMETHING to the // output. To prevent RES from waiting // interterminately after sending a command that // the Brain Program (= this program) doesn't act // upon. printf( "?\n" ); break; }/*switch*/ fflush( stdout ); } return 0; }