The assignment states:

1. The state array in homework #1 used 8 bits per state to store the depth. Modify the state array

to use only four bits per state. As there is no native 4-bit type, you will need to use a larger

type and bit manipulations to get and set the bits for each state. These four bits will be used for

two purposes.

a. Two of the four bits will represent 4 values: Already seen, current depth, next depth, and

unseen. This will efficiently mark what states should be expanded in the current iteration

and future iterations.

b. The other bits will store the depth of each state modulo 4. This is sufficient information to

extract the path from the board.

So I wrote 2 methods that divides the 8 bits into an upper and a lower 4 bits.

//Homework Number 2 FUNCTIONS: uint8_t getStateInfo(uint8_t *BAA, uint32_t hash) { uint32_t index = hash/2; if(hash %2 == 1 )// Odd lower { return BAA[index] & 0x0F; } else //even upper { return BAA[index]>>4; } } //Homework Number 2 FUNCTIONS: void setStateInfo(uint8_t *BAA, uint32_t hash, uint8_t value) { assert(value & 0xF); uint32_t index = hash/2; if(hash %2 == 1 )// Odd lower { BAA[index] = BAA[index] & 0xF; BAA[index] |= value; } else //even upper { BAA[index] = BAA[index] & 0xF; BAA[index] |= value<< 4; } }

Then I am trying to actually use these methods on homework 1's Breadth-First Search

void BFS() { // initialize memory, 1 byte per state, to store the depth of the state uint8_t* depths = new uint8_t[GetMaxHashValue()]; // changed for Homework 2 //Two of the four bits will represent 4 values: Already seen, current depth, next depth, and //unseen. This will efficiently mark what states should be expanded in the current iteration //and future iterations. ==>Upper Bits //The other bits will store the depth of each state modulo 4. This is sufficient information to //extract the path from the board. ==>Lower Bits I'm not sure if this is actually what I think I'm to be doing... //BAA = depths //i = hash //Value is either the state scene or it is the state modulo 4 // reset all memory to -1 (unseen) for(uint32_t i = 0; i<GetMaxHashValue(); i++) { depths[i] = -1; // changed for Homework 2 setStateInfo(depths, i, -1); //This is where I'm confused I'm trying to change the array into half the memory } // Set the start state to depth 0 depths[GetHashFromState(GetStartState())] = 0; uint8_t current_depth = 0; int states_seen; do { states_seen = 0; for (uint32_t i = 0; i < GetMaxHashValue(); ++i) { // Loop through all states; any at the current depth should: if(depths[i] == current_depth) // Needs to be changed for Homework 2 { states_seen++; // * Have their legal actions generated PegState state = GetStateFromHash(i); vector<PegAction> actions = GetLegalActions(state); // * Find all possible successor states for(auto i: actions) { // * Write the depth of the successors depths[GetHashFromState(ApplyAction(state, i))] = current_depth + 1; //Needs to be changed for Homework 2 setStateInfo(depths, i ,GetHashFromState(ApplyAction(state, i))); } } } // Repeat the loop until no states are updated in the loop // Print statistics about the search cout << "Depth " << +current_depth << " has " << states_seen << " states." << endl; current_depth++; }while(states_seen !=0); delete[] depths; //Needs to be changed for Homework 2 }

In class he seems to be saying that it will take half the memory which would be true if we were splitting the 8 bits into 4 bits making the array half the size but it sounds like he wants to take the 8 bits put the hash number into half of it and then make the other half a tag of if we've seen it or not.

I'm not getting any compiling errors I just think I'm doing this wrong and I'm unsure how to apply this if its the way I'm understanding it.