4

私はTickettoRideを楽しんでいるので、サイドプログラミングプロジェクトとしてPythonでゲームロジックの一部を実装することを試してみることにしました。ゲームボードは基本的に加重マルチグラフであるため、NetworkXを使用してゲームの基本構造を複製するのは簡単でした。

私が問題を抱えているのは、プレイヤーが所有している列車カードの在庫を考慮して、ボードを通る特定のパスが可能かどうかを分析することです。プログラミングの問題というよりは数学の問題だと思います。おそらく力ずくの方法で物事を理解することができますが、もっと効率的な方法があるはずだと思いました。

ゲームを知らない人のために：いつでも、各プレイヤーは8色のいずれかの列車カードの数に加えて、ワイルドカードとして機能する特別な「機関車」カテゴリを持っています。これらの色は、セグメント内のすべての車が同じ色である限り、任意の色を使用できる灰色の線を除いて、ゲームボード（ここに表示）の列車の線の色に対応しています。（トンネルやフェリーが関係するエッジケースがありますが、今はそれらを脇に置いておきます。）

現在のコードを使用すると、特定の2つの都市間のすべてのパスを見つけて、パスに灰色のセグメントが含まれていない限り、その特定のパスをたどるのに必要な各色の列車カードの数を取得できます。灰色以外のセグメントはより単純なので、最初に実行します。パス内の各赤/緑/青のセグメントに十分な赤/緑/青のカードがあるか、ないかのどちらかです。グレーの場合、各セグメントに使用する色を選択できるため、少し複雑になります。

灰色のセグメントが1つしかないパスの場合でも、それは簡単です。1つの色のカードが十分にあるかどうかにかかわらず、それを埋めることができます。ただし、複数の灰色のセグメントがあると、最初のセグメントに選択された色によって2番目または3番目のセグメントを完成させることが不可能になる状況に遭遇する可能性があります。

例として、プレーヤーのカードの在庫が赤4、緑2、青3であり、彼がパリからウィーンに行くことができるかどうかを調べようとしているとします。ボードを見ると、このカードの組み合わせで可能な唯一のルートは、パリ-（3グレー）->チューリッヒ-（2グリーン）->ウィーン-（2グレー）-に行くことであることがわかります。 >チューリッヒ-（2グレー）->ウィーン。これを理解するための私のアルゴリズムは、緑のセグメントから始まり、そこに2枚の緑のカードを割り当てます。次に、残りの4枚の赤と3枚の青のカードを使用して、長さ3、2、および2の灰色のセグメントをカバーする方法を決定する必要があります。

もちろん、答えは、パリとチューリッヒの間で3枚の青いカードを使用し、ヴェネツィアからザグラード、ザグラードからウィーンまでそれぞれ2枚の赤いカードを使用することです。しかし、より多くの色とより多くのセグメントを含むあまり明白でないケースに対してこの問題を解決する一般化されたアルゴリズムをどのように書くのでしょうか？

このための私のコードは今次のようになります：

def can_afford(path, cards):
    grays = list()
    for segment in path:
        if segment.color == 'Gray':
            grays.append(segment)
        else:
            if cards.get(segment.color, 0) >= segment.weight:
                cards[segment.color] -= segment.weight
            else:
                return False
    for gray in grays:
        # Halp!
        pass
    return True

（「重量」は、鉄道車両のセグメントの長さです。）

ここには本当に些細な解決策が潜んでいて、指を置くことができないような気がします。何か案は？

4

3 に答える 3

3

Daniel Brückner が言うように、カードの色を灰色のセグメントに割り当てる方法を見つける問題は、ビンのパッキング問題に対応し、色付きのカードのセットがビンに対応し、灰色のセグメントがパックされるオブジェクトに対応します。

現在、ビン パッキング問題はNP 困難ですが、動的計画法を使用して疑似多項式時間(つまり、ビンのサイズが多項式である時間)で問題を解決できるため、この場合は大惨事ではありません。ビンのサイズがゲーム内のカードの数によって制限されるアプリケーションには、これで十分です。これは、デコレータを使用してメモ化するビン パッキングの実装例です。@functools.lru_cache

functools import lru_cache から

@lru_cache(maxsize=None)
def packing(bins, objects):
    """Return a packing of objects into bins, or None if impossible. Both
    arguments are tuples of numbers, and the packing is returned in
    the form of a list giving the bin number for each object.

    >>> packing((4,5,6), (6,5,4))
    [2, 1, 0]
    >>> packing((4,5,6), (1,1,2,4,5))
    [0, 0, 0, 1, 2]

    """
    if not objects:
        return []
    o = objects[0]
    rest = objects[1:]
    for i, b in enumerate(bins):
        if o <= b:
            p = packing(bins[:i] + (b - o,) + bins[i+1:], rest)
            if p is not None:
                return [i] + p
    return None

これを使用して、Ticket to Ride でパスをたどることができるかどうかを判断できます。

def can_afford(path, cards):
    """Return True if path can be followed using cards, False if not.
    cards might be updated, so pass a copy if you don't want that to
    happen.

    """
    grays = []
    for segment in path:
        c, w = segment.color, segment.weight
        if c == 'Gray':
            grays.append(w)
        elif cards.get(c, 0) >= w:
            cards[c] -= w
        else:
            return False
    return packing(tuple(cards.values()), tuple(grays)) is not None

cardsを作成した場合は、 の代わりにcollection.Counter書くことができることに注意してください。cards[c]cards.get(c, 0)

于 2013-01-23T16:41:05.080 に答える
0

この問題は、ビン パッキング、サブセット サム、およびその他の同様の問題といくつかの類似点があります。言及された多くの関連する問題はNP完全であるため、この問題に対する（既知の）効率的なアルゴリズムは存在しないことが判明する可能性がありますが、現時点ではこれを証明することはできません-それは単なる直感です. もう少し考えてから、この回答を更新します。

于 2013-01-23T17:03:41.440 に答える
0

これにアプローチする別の方法は、次のように検索ツリーを構築することです。

  • 各ノードには、都市名、一連のカード、および列車の番号が付けられています。これは、特定のルートの開始都市と、利用可能なカードと列車のピースに対応しています。

  • ノードの各子は、親からノードへのルートを完了した後に手札に残るカードと列車の駒とともに、親から到達できる都市に対応します。

たとえば、ツリーのルートはモントリオールに対応し、青 4 つ、白 1 つ、ワイルド カード 1 つ、および 45 個の列車のピースがあります。ルートの子は次のようになります。

  • トロント、(青 1、白 1、ワイルド 1)、42 # 青のカード 3 枚を使用
  • トロント、（青 2 個、白 1 個）、42 # 青 2 個とワイルド カード 1 個を使用
  • New York, ( 青 1 枚、白 1 枚、ワイルド 1 枚)、42 # 青のカード 3 枚を使用
  • New York, ( 青 2 個、白 1 個 )、43 # 青 2 個とワイルドカード 1 個を使用
  • ボストン、( 青 3 個、白 1 個)、43 # 青 1 個とワイルドカード 1 個を使用
  • ボストン、( 青 2、白 1、ワイルド 1)、43 # 青のカードを 2 枚使用
  • Boston, ( 4 青 ), 43 # 白 1 枚とワイルドカード 1 枚を使用

次に、このツリーで深さ優先検索を実行して、目的地の都市に到達できるかどうかを確認するだけです。検索ツリーに追加するエッジは、手札のカードによって制限されます (つまり、手札に合計 6 枚の黒/ワイルド カードがないため、モントリオールからスー セント マリーに直接行くことはできません)。残りの列車の数 (カードが 3 枚しか残っていない場合、カルガリーからシアトルに行くことはできません)。

于 2013-01-23T18:06:28.093 に答える