c - コネクト5ゲームでビットボード？

Question

コネクト 5 ゲームでビットボードを使用できるかどうかを教えてください。コネクト 4 ゲームの例はたくさん見ましたが、ボードが 15x15 や 19x19 などの非常に大きい場合は何もありませんでした。ボードを 64 ビットで表現する方法がわかりません。

助けてくれてありがとう

Answer 1

unwind's answer で説明されているように可能ですが、そうすることで、1 つの CPU 命令でデータ構造全体に対して論理演算を実行するビットボードの主な利点が無効になります。最適には、ビットボードのサイズは、プラットフォームの命令セットの幅になります。

考えられる回避策は、ボードを複数の小さな「標準」ビットボード (プラットフォームに応じて 32 ビットまたは 64 ビット) として表し、各ミニ ビットボードに個別に論理演算を適用することです。たとえば、15x15 のボードは 4 つの 8x8 ボードに分割できます。例:

typedef uint64_t miniboard_type; // 8x8 board

typedef struct
{
    miniboard_type miniboard[4]; // Larger 15x15 board comprising 4 8x8 boards
} bitboard_type;

bitboard_type bitboard;

それに応じて、ミニビットボード間のエッジを考慮して数学とロジックを調整する必要があるかもしれないと思います (これは、メインのビットボードで何をしたいかによって異なります)。

Answer 2

は？

もちろん、「ビットボード」が「セルごとに 1 ビットを使用する 2D 配列」を意味する場合は可能です。

たとえば、各行 (または列) が整数バイトになるように四捨五入すると簡単な場合がありますが、そうする必要はありません。

次のようなことをしてください：

#include <stdint.h>
#include <limits.h>

#define WIDTH 22
#define HEIGHT 17
uint8_t bits[(WIDTH * HEIGHT + CHAR_BIT - 1) / CHAR_BIT];

これはバイトの配列として宣言され、セルbitsの行列を保持するのに十分なバイトがあります。WIDTHHEIGHT

例の値では、(22 * 17 + 7) / 8 または 47 バイト長 (8 と仮定CHAR_BIT) になります。