1 Replies - 404 Views - Last Post: 15 February 2013 - 12:52 PM Rate Topic: -----

#1 classic89  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 03-November 11

Memory Manipulation

Posted 15 February 2013 - 10:04 AM

This is a homework assignment but I'm having problems understanding bit manipulation. This program is in C++.

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Memory Manipulation

#2 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1199
  • View blog
  • Posts: 7,309
  • Joined: 07-September 06

Re: Memory Manipulation

Posted 15 February 2013 - 12:52 PM

I believe that he is actually asking you to store the information in 4 bit segments, where you have 2 fields (each taking 2 bits of the 4 bits you have available).

For example:
First | Second
  ----|----



Then you break that information down to:
viewed depth%4 | viewed depth%4
    --      -- | --     --



Such that the first entry in the 8 bits of data has 2 bits allocated to the viewed information and two bits allocated to the depth (mod 4), and the second entry in the 8 bits has the same.

Hopefully that makes sense.

One other thing, when you are setting the values of the information in your set function you are zeroing the bottom 4 bits in both cases, though you want to zero the bottom 4 bits in the first case, and the top 4 in the second case.
// ...
		BAA[index] = BAA[index] & 0xF0; // clear the bottom 4 bits
		BAA[index] |= value;
	}
	else{
		BAA[index] = BAA[index] & 0x0F; // clear the top 4 bits
		BAA[index] |= value << 4;
	}
// ...


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1