状態ごとに 4 ビットのみを使用するように状態配列を変更する必要があります。ネイティブの 4 ビット型がないため、より大きな型とビット操作を使用して、各状態のビットを取得および設定する必要があります。これらの 4 ビットは 2 つの目的で使用されます。
を。4 つのビットのうちの 2 つは、4 つの値を表します: 既に見られている、現在の深さ、次の深さ、および見えない。これにより、現在の反復と将来の反復でどの状態を展開する必要があるかが効率的にマークされます。
b. 他のビットは、4 を法とする各状態の深さを格納します。これは、ボードからパスを抽出するのに十分な情報です。
はい、これはハードウェアに関する質問なので、回答は期待していません。単なるガイダンスです。defineStateInfo 関数の処理方法がわかりません。これが私の現在のコードです：
#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;
}