Here is a test of Artificial Intelligence informed and uninformed search algorithms.
We have a 3×3 grid where B means BLACK KNIGHT and W is WHITE KNIGHT of chess.
+---+---+---+ +---+---+---+ | W | | W | | B | | B | +---+---+---+ +---+---+---+ | | | | ----> | | | | +---+---+---+ +---+---+---+ | B | | B | | W | | W | +---+---+---+ +---+---+---+B and W can "L" move exactly like knights chess pieces.
What is the best search algorithm to put black ones into current white ones squares and white ones into current black ones square?
- A STAR
- BFS
- DFS
- HILL CLIMBING
I'm really confused and I don't know the correct choice.
An important aspect is that the number of possible positions is rather small :
420 = Binomial(8,2) * Binomial(6, 2)
A consequence is that whatever which the algorithm is selected, you have to pay attention not to go through the same node several times , i.e. through the same position. Traditionally, chess programmes use hash tables when analyzing positions with a low number of pieces. Here, taking into account the small number of possible positions, it is possible to select a perfect hashing, i.e. with no collusion.
Concerning the algorithms:
I have therefore implemented the BFS in C++. The result is provided about instantaneously.
The 16 half-moves are given hereafter:
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | W | | | | W | | | | W | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | B | | W | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | B | | B | W | B | | | W | B | | | W | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | | | B | | W | | B | B | W | | B | B | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | | | W | | | | W | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | W | B | | | | B | | | | | | | | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | W | | B | W | W | | B | W | W | | B | W | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | B | | W | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| B | | W | | B | | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | W | | | | W | | | | W | B | | | | B | | B | | B |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| W | | B | | | | B | | | | B | | | | B | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | B | | | | B | W | | | | W | | W | | W | | W | | W |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
And the programme:
#include <iostream>
#include <array>
#include <vector>
#include <tuple>
#include <algorithm>
int depl[9][2] = {
{5,7}, {6,8}, {3,7}, {2,8}, {-1,-1},
{0,6}, {1,5}, {0,2}, {1,3}};
struct position {
std::array<int, 2> B;
std::array<int, 2> W;
int hash;
position *up = nullptr;
position (int w0, int w1, int b0, int b1) {
if (w0 > w1) std::swap (w0, w1);
if (b0 > b1) std::swap (b0, b1);
B[0] = b0;
B[1] = b1;
W[0] = w0;
W[1] = w1;
cal_hash();
}
position() {};
void cal_hash () {
hash = 1000*B[0] + 100*B[1] + 10*W[0] + W[1];
}
std::vector<position> gene_mov (int white_black) {
std::vector<position> res;
if (!white_black) { // White
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int pos = depl[W[i]][j];
bool test = (pos == W[1-i]) || (pos == B[0]) || (pos == B[1]);
if (!test) {
res.push_back (position(pos, W[1-i], B[0], B[1]));
}
}
}
} else { // Black
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int pos = depl[B[i]][j];
bool test = (pos == B[1-i]) || (pos == W[0]) || (pos == W[1]);
if (!test) {
res.push_back (position(W[0], W[1], pos, B[1-i]));
}
}
}
}
return res;
}
void print (int shift = 0) {
char displ[3][3] = {{' ',' ',' '},
{' ',' ',' '},
{' ',' ',' '}};
displ[1][1] = ' ';
displ[2 - W[0]/3][W[0]%3] = 'W';
displ[2 - W[1]/3][W[1]%3] = 'W';
displ[2 - B[0]/3][B[0]%3] = 'B';
displ[2 - B[1]/3][B[1]%3] = 'B';
Wshift(shift);
std::cout << "+---+---+---+\n";
for (int i = 0; i < 3; ++i) {
Wshift(shift);
for (int j = 0; j < 3; j++) {
std::cout << "| " << displ[i][j] << " ";
}
std::cout << "|\n";
Wshift(shift);
std::cout << "+---+---+---+\n";
}
std::cout << "\n";
}
void Wshift (int shift) {
for (int i = 0; i < shift; ++i)
std::cout << " ";
}
};
std::tuple<bool, int, std::vector<position>> find_moves (position &first, position &end) {
std::vector<position> moves;
std::array<bool, 10000> pos_found = {false};
std::vector<std::vector<position>> dfs;
using pvector = std::vector<position>;
dfs.push_back(pvector(1, first));
int iter = 1;
int white_black = 0;
while (true) {
int n = dfs[iter-1].size();
if (n == 0) return std::make_tuple(false, 0, moves);
dfs.push_back(pvector(0));
for (int i = 0; i < n; ++i) {
auto candidates = dfs[iter-1][i].gene_mov(white_black);
for (auto &c: candidates) {
if (pos_found[c.hash]) continue;
c.up = &dfs[iter-1][i];
if (c.hash == end.hash) { // Last position attained: get the previous moves
moves.resize(iter+1);
moves[iter] = c;
for (int i = iter - 1; i >= 0; i--) {
moves[i] = *(moves[i+1].up);
}
return std::make_tuple(true, iter, moves);
}
pos_found[c.hash] = true;
dfs[iter].push_back (c);
}
}
iter++;
white_black = 1 - white_black;
}
return std::make_tuple(false, -1, moves);
}
int main () {
position first(6, 8, 0, 2);
position end(0, 2, 6, 8);
bool success;
int n_iter;
std::vector<position> moves;
std::tie (success, n_iter, moves) = find_moves (first, end);
std::cout << "success = " << success << "\n";
std::cout << "n_iter = " << n_iter << "\n";
for (auto &m: moves) {
m.print();
std::cout << "\n";
}
return 0;
}