3

Connect Four ゲームで実際に発生する可能性のある状況を計算する短い (450 行) プログラムを作成しました。プログラムはゲーム ツリーを構築しようとし、状況が既に発生しているかどうかを認識します (また、対称バージョンのみが発生した場合はブランチをスキップします)。

すでに起こった状況に遭遇した回数を数えますint alreadyCounter。しかし、実行時に奇妙なことに気付きました:

追加する

printf("abcdefghijklm");

alreadyCounter私の!の結果を変更します。

他のコア/プロセス/スレッドは使用しません。Cプログラムをコンパイルします

gcc -g -W -Wall -Werror -std=c99 -o connectfour

完全なソースはGitHubにあります。(申し訳ありませんが、コードを大幅に短くすることはできませんでした)

とを見てconnectfour.cくださいconnectfour-strange.c。386 行目だけが異なります。

しかし、多くの「abcdefghijklm」を除いて、異なる結果が得られます。

コネクトフォー:

[...]abcdefghijklmabcdefghijklm########################Finish:
Maximum of 20000 reached
alreadyCounter: 1547
mirroredCounter: 0

connectfour-strange:

[...]
########################Finish:
Maximum of 20000 reached
alreadyCounter: 1566
mirroredCounter: 0

一定の出力を追加するだけで、単一のコア/プロセス/スレッド プログラムで異なる結果が得られるのはなぜですか?

4

4 に答える 4

4

この問題は、学校でのアシスタントの仕事で何度か見てきました。

一部の学生は、どこかにprintfを追加しない限り、プログラムのセグメンテーション違反を起こしていました。

Printf はいくらかのメモリを割り当て、それを使ってクレイジーなことをします。

私の推測では、どこかでバッファ オーバーフローが発生しているか、構造体に十分なメモリを割り当てておらず、printf がそれを消去していると思われます。

valgrind を実行して、問題が発生していないかどうかを確認してください。

于 2012-11-29T17:59:13.690 に答える
1

それがあなたの観察の原因であるかどうかはわかりませんが、334行目以降で、

char mirrored[BOARD_WIDTH][BOARD_HEIGHT];
for (int x = 0; x<BOARD_WIDTH; x++) {
    for (int y=0; y<BOARD_HEIGHT; y++) {
        mirrored[x+1-BOARD_WIDTH][y] = board[x][y];
    }
}

割り当てられたメモリの外側に書き込みます（行インデックスは から-(BOARD_WIDTH)になります-1）。したがって、未定義の動作が呼び出されます。

また、それはボードを反映していません。あなたはおそらく意味した

mirrored[BOARD_WIDTH - 1 - x][y] = board[x][y];

そこの。それとは別に、境界外書き込みのような明白な候補は見当たりません。

(行 43ff)ではisBoardFinished、行/列 0 に到達する前にチェックを停止します。

while (xTemp > 0)

（yトップダウンチェック、および対角線チェックの両方についても同様です）。それはx >= 0フルボードを使用することです。しかし、これは を上書きできませんでしalreadyCounterたが、それでも役に立つかもしれません。

しかし、警告をオンにして最適化を行ってコードをコンパイルすると、考えられる原因が示されます。

connect-four.c: In function ‘getFirstIndex’:
connect-four.c:202:19: warning: ‘index’ may be used uninitialized in this function [-Wuninitialized]
connect-four.c: In function ‘getNewIndex’:
connect-four.c:202:19: warning: ‘index’ may be used uninitialized in this function [-Wuninitialized]
connect-four.c:199:18: note: ‘index’ was declared here
connect-four.c: In function ‘getMyIndex’:
connect-four.c:202:19: warning: ‘index’ may be used uninitialized in this function [-Wuninitialized]
connect-four.c:199:18: note: ‘index’ was declared here
connect-four.c: In function ‘makeTurns’:
connect-four.c:202:19: warning: ‘index’ may be used uninitialized in this function [-Wuninitialized]
connect-four.c:199:18: note: ‘index’ was declared here
connect-four.c:202:19: warning: ‘index’ may be used uninitialized in this function [-Wuninitialized]
connect-four.c:199:18: note: ‘index’ was declared here

したがって、警告と付随する注記 (関数名は異なりますが、インライン化のために同じ場所で複数回表示されます) は、次のようにする必要があることを示しています。

unsigned int getFirstIndex(char board[BOARD_WIDTH][BOARD_HEIGHT]) {
    unsigned int index = 0;
    //               ^^^^^^^

getFirstIndex同一のボードで呼び出して決定論的な結果を得る。ただし、インデックスを返す前にモジュラスを取得するためMAXIMUM_SITUATIONS、返されるインデックスが範囲外であってはなりません。したがって、その結果としてクラッシュは予想されません。しかし、何かを印刷すると、スタックに割り当てが発生する可能性があります (必要ではなく、引数と戻りアドレスはすべてレジスタに渡される可能性があります)。index次回getFirstIndexが呼び出されます。それは返される値を変更し、 の間違ったスロットを調べるdatabaseため、同じボードの以前の出現を見逃すため、値getFirstIndexが生成するだけの場合よりも重複が少なくなります。渡されたボードに依存します (また、特定のスタック位置を占めるビットにも依存しません)。

私のバージョンのgccでは、警告を取得するには、警告をオンにして最適化する必要があることに注意してください。警告clangと最適化を最高レベルにしても警告しません。他のバージョンの gcc と clang、および他のコンパイラーでは、問題の特定が異なる場合があります。

indexで 0 に初期化すると、getFirstIndex一貫した結果が得られます

########################Finish:
Maximum of 20000 reached
alreadyCounter: 4412

文字列が出力されるかどうか、および最適化レベルとは無関係です。初期化しないと、 の値はalreadyCounter両方の要因に依存します。

于 2012-11-29T20:03:02.127 に答える
0

それを見つけるために 500 行のコードを調べるつもりはありませんが、ほとんどの場合、メモリの問題です。

通常、これは配列の末尾を超えてインデックスを作成しているスタックの破損のようなものです。したがって、print ステートメントがスタックを変更し、境界外アクセスの結果が変更されます。

valgrind などのツールを使用して実行すると、違反を特定するのに役立ちます。

于 2012-11-29T17:58:58.833 に答える
0

そのインスタンスは見つかりませんでしたが、マクロを使用して i++ のようなものを渡した場合の一般的な結果です。これは、 結果が i++ として渡された場合 ABS(outcome)にコードを挿入するマクロです 。(outcome) (outcome < 0 ? -outcome : outcome)(i++) (i++ < 0 ? -i++ : i++)

おそらく、スレッド化されたバージョンでは、マクロは何らかの形でコンパイラーによって取り込まれています

于 2012-11-29T18:51:40.220 に答える