12

はるか昔 (20 年以上前と考えてください)、私は雑誌で五目並べゲームのソース コードに出会い、それを自分のコンピューターに打ち込み、大いに楽しんでいました。

ゲームに勝つのは困難でしたが、コンピューター AI のコア アルゴリズムは非常にシンプルで、多くのコードを必要としませんでした。誰かがこのアルゴリズムを知っていて、それに関する情報源や理論へのリンクを持っているのだろうか.

私が覚えているのは、基本的にボード全体をカバーする配列を割り当てたことです。次に、私またはそれが駒を配置するたびに、駒が影響を与える可能性のあるボード上のすべての場所にいくつかの重みを追加します.

たとえば（覚えていないので、重みは間違いなく間違っていることに注意してください）：

1   1   1
 2  2  2
  3 3 3
   444
1234X4321
  3 3 3
 2  2  2
1   1   1

次に、配列をスキャンして、最小値または最大値の開いている場所を探しました。

私が曖昧なこと：

  • おそらく、私用とそれ自体用の2つの配列があり、最小/最大の重み付けがありましたか?
  • アルゴリズムにはもっと多くのことがあったかもしれませんが、その核心は基本的に配列と重み付けされた数値でした

これは誰とでもベルを鳴らしますか？誰かが助けになるものを手に入れましたか？

4

6 に答える 6

6

あなたの説明を読んで、少し考えてみると、あなたが説明したとおりに、おそらく単一の配列で機能すると思います。

5 連勝という目標を達成するには、(a) 対戦相手が成功するのを防ぎ、(b) 自分自身が成功する必要があります。

自分で成功するには、ボード上に既にある他の石の近くに石を配置する必要があるため、列に参加できる石の隣のフィールドにプラスのスコアを追加することは理にかなっています. あなたが与えた線形の例、または二次的なものはおそらくうまくいくでしょう。

相手が成功するのを防ぐには、相手の石の隣に石を配置する必要があります。1 つの石で 2 羽の鳥を攻撃する場合は特に優れているため、対戦相手の石は、自分と同じように周囲のフィールドの値を増加させる必要があります。すでに並んでいる石が多いほど、スコアが高くなり、アルゴリズムは対戦相手を遮断しようとします。

ここで最も重要なことは、さまざまなフィールドの重み付けと、対戦相手の石の重み付けが自分のものと異なるかどうかです。残念ながら、私はそれを手伝うことはできませんが、ゲーム自体が書かれたら、値は試行錯誤によってかなり簡単に理解できるはずです。

ただし、これは非常に基本的なアプローチであり、ツリー検索アルゴリズムよりも優れています。Google で検索すると、 Threat search に関する関連論文があり、これは Gomoku に適しているようです。ただし、紙は有料の壁の後ろにあります:/

于 2010-05-03T18:12:03.297 に答える
2

私は記事を読んでいませんが、説明から私の推測はミニマックスアルゴリズムの何らかの形になるでしょう

于 2010-05-02T12:57:27.130 に答える
2

あなたが言及したこのアルゴリズムを見ました-それは非常にシンプルで高速でした（バックトラッキングなし:-)）そしてそれは非常にうまく機能しました:-) どこかにソースが必要ですが、それは何年も前です...あなたの石には重みがありました他の石がどれだけ近くにあったか、および敵の石の重量に応じて。これらは低かったため、アルゴリズムは攻撃戦略を優先しました。

しかし、これはもちろん非常に単純なアルゴリズムです。勝利の戦略はすでに見つかっています。この論文を参照してください: L. Victor Allis、HJ van den Herik、MPH Huntjens。Go-Moku と Threat-Space Search。自分でプログラムを書いていたとき、それは私を大いに助けてくれました。このようにして、対戦相手を攻撃し、勝利の組み合わせを見つけるのに非常に優れたプログラムを書くことができます.

于 2011-08-09T11:21:54.920 に答える
1

お探しのプログラムはこちらです ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw/gomoku.c

もうすぐ40歳です

于 2015-05-04T20:09:05.510 に答える
1

これは古代のゲームです。Planet Source Codeでコードを見つけました。私は大学時代にこのゲームをプレイし、286 日で BASIC バージョンを手に入れました。

于 2010-05-03T18:52:14.270 に答える
-1

iPhone 向けのオープン ソース バージョンに取り組んでいます。

参加することに興味があるなら、私に連絡してください！

https://github.com/kigster/kigomoku

于 2012-02-25T14:58:28.417 に答える