我需要修改状态数组以使每个状态仅使用四位。由于没有原生 4 位类型，您将需要使用更大的类型和位操作来获取和设置每个状态的位。这四个位将用于两个目的。
一个。四位中的两位将代表 4 个值：已经看到、当前深度、下一个深度和未看到。这将有效地标记在当前迭代和未来迭代中应该扩展哪些状态。
湾。其他位将存储每个状态模 4 的深度。这是从电路板中提取路径的足够信息。
是的，这是一个硬件问题，所以我不期待答案，只是指导。我不确定如何继续我的 determineStateInfo 函数。这是我当前的代码：
#include <iostream>
#include <climits>
#include <vector>
#include <assert.h>
#include <stdio.h>
enum state {NEXT_DEPTH = 2, UNSEEN = 3, CURRENT_DEPTH = 1, ALREADY_SEEN = 0};
bool valid[56] =
{
false, false, false, false, false, false, false,
false, true, true, true, true, true, false,
false, true, true, true, true, true, false,
false, true, true, true, true, true, false,
false, true, true, true, true, true, false,
false, true, true, true, true, true, false,
false, true, true, true, true, true, false,
false, false, false, false, false, false, false
};
struct PegState {
bool board[56];
};
struct PegAction {
int from, to, middle;
};
PegState GetStartState()
{
PegState s;
for (int x = 0; x < 56; x++)
{
s.board[x] = true;
}
s.board[24] = 0;
return s;
}
uint32_t GetHashFromState(PegState s)
{
uint32_t hash = 0;
for (int x = 0; x < 56; x++)
{
if (valid[x])
hash = (hash<<1)|(s.board[x]?1:0);
}
return hash;
}
PegState GetStateFromHash(uint32_t hash)
{
PegState s;
for (int x = 55; x >= 0; x--)
{
if (valid[x])
{
s.board[x] = hash&0x1;
hash = hash>>1;
}
}
return s;
}
uint32_t GetMaxHashValue()
{
uint32_t vals = 0;
for (int x = 0; x < 55; x++)
{
if (valid[x])
vals = (vals<<1)|1;
}
return vals;
// return 0xFFFFFFFFul;
}
void Print(PegState s)
{
for (int x = 0; x < 7; x++)
{
for (int y = 0; y < 8; y++)
{
if (valid[x+y*7])
{
printf("%c", s.board[x+y*7]?'o':'.');
}
else {
printf(" ");
}
}
printf("\n");
}
printf("\n");
printf("\n");
}
std::vector<PegAction> GetLegalActions(PegState s)
{
std::vector<PegAction> moves;
for (int x = 0; x < 5; x++)
{
for (int y = 1; y < 7; y++)
{
if (valid[x+0+y*7] && valid[x+1+y*7] && valid[x+2+y*7])
{
// right
if ((s.board[x+0+y*7] == true) &&
(s.board[x+1+y*7] == true) &&
(s.board[x+2+y*7] == false))
{
PegAction a;
a.from = x+0+y*7;
a.middle = x+1+y*7;
a.to = x+2+y*7;
moves.push_back(a);
}
// left
if ((s.board[x+0+y*7] == false) &&
(s.board[x+1+y*7] == true) &&
(s.board[x+2+y*7] == true))
{
PegAction a;
a.from = x+2+y*7;
a.middle = x+1+y*7;
a.to = x+0+y*7;
moves.push_back(a);
}
}
}
}
for (int x = 1; x < 6; x++)
{
for (int y = 0; y < 6; y++)
{
if (valid[x+(y+0)*7] && valid[x+(y+1)*7] && valid[x+(y+2)*7])
{
// down
if ((s.board[x+(y+0)*7] == true) &&
(s.board[x+(y+1)*7] == true) &&
(s.board[x+(y+2)*7] == false))
{
PegAction a;
a.from = x+(y+0)*7;
a.middle = x+(y+1)*7;
a.to = x+(y+2)*7;
moves.push_back(a);
}
// up
if ((s.board[x+(y+0)*7] == false) &&
(s.board[x+(y+1)*7] == true) &&
(s.board[x+(y+2)*7] == true))
{
PegAction a;
a.from = x+(y+2)*7;
a.middle = x+(y+1)*7;
a.to = x+(y+0)*7;
moves.push_back(a);
}
}
}
}
return moves;
}
PegState ApplyAction(PegState s, PegAction a)
{
assert(s.board[a.from] == true);
s.board[a.from] = false;
assert(s.board[a.middle] == true);
s.board[a.middle] = false;
assert(s.board[a.to] == false);
s.board[a.to] = true;
return s;
}
void undo()
{
}
void reverse()
{
}
void setBit(uint8_t *array, const uint32_t hash, const uint8_t new_info)
{
assert(new_info == (new_info&0xF));
const uint8_t index ( hash/2 );
if(hash%2 == 0) //even
{
array[index] &= 0xF; //00001111
array[index] |= new_info << 4;
}
else
{
array[index] &= 0xF0; //11110000
array[index] |= new_info;
}
}
uint8_t getStateInformation(const uint8_t *array, const uint32_t hash)
{
const uint8_t index ( hash/2 );
if(hash%2 == 0) //even
return array[index] & 0xF;
else
return array[index] & 0xF0;
}
void savestate(PegState *temp)
{
FILE *f;
f = fopen("state.txt", "w+");
for (int x = 0; x < 55; x++) {}
//fwrite(&temp.board[x], sizeof(PegState), 1, f);
}
uint8_t determineStateInfo(uint8_t status, uint32_t depth)
{
if(status == CURRENT_DEPTH)
{
}
else if(status == ALREADY_SEEN)
{
}
return 0;
}
bool compare(uint8_t stateInfo)
{
if(stateInfo == 0xF)
return true;
else
return false;
}
void BFS()
{
// initialize memory, 1 byte per state, to store the depth of the state
uint32_t maxVal = GetMaxHashValue();
int8_t *dist = new int8_t[maxVal];
// reset all memory to -1 (unseen)
for (uint32_t x = 0; x < maxVal; x++)
dist[x] = -1;
// Set the start state to depth 0
PegState s = GetStartState();
dist[GetHashFromState(s)] = 0;
Print(s);
printf("Ready to begin search\n");
// Loop through all states; any at the current depth should:
// * Have their legal actions generated
// * Find all possible successor states
// * Write the depth of the successors
// Repeat the loop until no states are updated in the loop
int update = 0;
int expand = 0;
int currDepth = 0;
do {
expand = 0;
update = 0;
for (uint32_t x = 0; x < maxVal; x++)
{
uint8_t i = getStateInformation(dist[x], maxVal);
// if (0 == x%100000000)
// printf("%ul\n", x);
if (dist[x] == currDepth)
{
expand++;
s = GetStateFromHash(x);
std::vector<PegAction> m = GetLegalActions(s);
for (unsigned int t = 0; t < m.size(); t++)
{
PegState res = ApplyAction(s, m[t]);
uint32_t rank = GetHashFromState(res);
if (dist[rank] == -1)
{
dist[rank] = currDepth+1;
update++;
}
}
}
}
printf("Depth %d; %d expanded; %d unique generated\n",currDepth, expand, update);
currDepth++;
} while (update > 0);
for (uint32_t x = 0; x < maxVal; x++)
{
if (dist[x] == (currDepth-1) || dist[x] == 0)
{
s = GetStateFromHash(x);
Print(s);
}
}
// Print statistics about the search
}
int main(int argc, const char * argv[])
{
BFS();
return 0;
}