language-agnostic - 位置を評価するためのかなり単純なヒューリスティックを使用するゲームは何ですか?

Question

私は子供にプログラミングを教えており、現在、いくつかの基本的な人工知能の概念を紹介しています。まず、ゲームツリー全体を検索する三目並べゲームを実装して、完全にプレイします。終了したら、同じ概念を、1 つ 1 つを評価するにはポジションが多すぎるゲームに適用したいので、中間ポジションを評価するためのヒューリスティックを実装する必要があります。

私が考えることができる最高のものは、Dots and Boxesでした。ボードのサイズを任意に大きく設定して、彼がツリー全体を検索するのを防ぐことができるという利点があり、非常に基本的なスコア関数を自分のボックスの数から対戦相手のボックスの数を引いたものにすることができます。残念ながら、これは、プレイヤーが実際にボックスを作り始める前にかなりの数の手がかかるため、ゲームの開始のほとんどで、すべてのポジションがスコア 0 で同等に評価されることを意味します。

ゲームについてもっと良いアイデアを持っている人はいますか? (または、ドットとボックスのより優れたスコアリング関数)?

score 7 · Accepted Answer

考えられるゲームの 1 つに、Connect Fourがあります。シンプルなルールのシンプルなゲームですが、Tic-Tac-Toe よりも複雑です。

score 7 · Accepted Answer

別のゲームの選択肢として、オセロとして知られるリバーシがあります。

単純なヒューリスティックは、各有効な動きによって得られるタイルの数を単純に数え、最大のものを選択することです。そこから、ボードの位置を考慮して、対戦相手に対して脆弱に最小化することができます。

score 3 · Accepted Answer

チェッカーを使用すると、いくつかの方法を教えることができます。単純な先読み、最善のケースと最悪のケースの決定の深層探索、短期的な利益と長期的な利益の違い、そしてあなたが教えたいことを学んだ後に彼らが取り組み続けることができる何か。

個人的には、最後の部分が最も重要だと思います。AI の開発には、立ち止まって、それを打ち負かすことができるかどうかを確認し、より深い AI メカニズムを掘り下げるのに適した自然なポイントがあります。生徒はひどくイライラすることなく興味を持ち続け、プロジェクトを続けたい場合は自分でできることが増えます。

score 2 · Accepted Answer

Rubik's Infinityはかなり楽しいです。Connect Four に少し似ていますが、微妙に異なります。ポジションの評価は非常に簡単です。

しばらく前に Perl スクリプトを作成して再生しましたが、実際には見た目より先の動きの数を減らす必要がありました。

score 2 · Accepted Answer

マンカラはどうですか？各ターンに可能な手は 6 つだけで、それぞれの結果のスコアを計算するのは簡単ですが、対戦相手の反応を考慮することが重要であり、ゲームツリーはかなり速く大きくなります。

score 2 · Accepted Answer

2

五目並べは、AI を作成するのに適したシンプルで楽しいゲームです。

于 2008-09-16T20:08:49.350 に答える

score 2 · Accepted Answer

リバーシはどうですか？ピースの数、エッジのピースの数、およびコーナーのピースの数に基づいたヒューリスティックスの非常に優れたスペースがあります。

score 1 · Accepted Answer

コネクトフォーが大好きです。Minimax アルゴリズムを使用してプログラムするのは非常に簡単です。適切な評価関数は次のようになります。

eval_score = 0
for all possible rows/lines/diagonals of length 4 on the board:
    if (#player_pieces = 0) // possible to connect four here?
        if (#computer_pieces = 4)
            eval_score = 10000
            break for loop
        else
            eval_score = eval_score + #computer_pieces
            (less pieces to go -> higher score)
        end if
    else if (#player_pieces = 4)
        eval_score = -10000
        break for loop
    end if
end for

プログラムを改善するには、次を追加できます。

コンピュータが最初に動く場合は、中央の列でプレイします (これが最適であることが証明されています)。
アルファベータ剪定
移動注文
Zobrist ハッシュ

score 1 · Accepted Answer

フォー・イン・ア・ライン十分に難しいが、簡単に機能する評価関数を考え出すのに十分簡単です。

score 0 · Accepted Answer

ゴーを見てください。

非常に小さなボードの子供には十分にシンプルです。
複雑さは無限に拡大します。
尺度または基礎として使用できる論文、アルゴリズム、およびプログラムが多数あります。

更新: Go の簡略版である reversi が言及されました。より良い選択かもしれません。

score 0 · Accepted Answer

ランダムな線がすでに追加されている状態で、点と箱のゲームを開始してみてはいかがでしょうか。これにより、すぐに行動に移すことができます。ボックスでゲームを開始しないようにする必要があります。

score 0 · Accepted Answer

ドットとボックスのより良いヒューリスティックに関しては、ゲームのオンライン戦略ガイドを参照することをお勧めします. 「点と箱の戦略」に関する Googleの最初の結果は非常に役に立ちます。

チェーンルールの使い方を知ることで、OK プレーヤーと良いプレーヤーを区別できます。チェーンルールがいつ不利になるかを知ることが、最高のプレーヤーと優れたプレーヤーを分けるものです。

language-agnostic - 位置を評価するためのかなり単純なヒューリスティックを使用するゲームは何ですか?

12 に答える 12

Related

Reference