Are the Diplomacy rules Turing complete?

Archived from groups: rec.games.diplomacy (More info?)

Jim Burgess wrote:
>
> It is depressing to JUST see messages from the spammers and about
> the spamming. Anyone have any real comments or questions??
>
> I'm looking for articles for the next issue of Diplomacy World,
> just one more month to write them!! Contact me for editorial
> guidance or details.

I won't have the free time to spit and polish any formal essay for a Dip
publication in the next month, but I have been mulling over one highly
theoretical topic for the past few weeks. Perhaps others have discussed
this in other publications; I don't know. (If someone has seen detailed
discussions like this before, I'd be interested in a link or something.
The closest thing I've found is a brief mention of Godel's Theorem
applied to Diplomacy in a thread back in 2001.)

As you may be aware from my recent posts, I have found far too much
personal amusement in the various rule problems of this otherwise very
high-quality game. The rule paradoxes trouble me especially. One day I
got in an e-mail argument with a friend who believes that there really
are no paradoxes in the rules, merely ambiguities. His arguments seemed
spurious to me, though, and I tried to devise how I might prove to him
logically that there really are paradoxes in the rules.

It occurred to me that when you feed a paradoxical situation to a judge
program, it will loop infinitely, never rendering any resolution of the
given orders; whereas with orders that illustrate ambiguities, the judge
program will eventually produce an outcome according to programmer bias.
And then, my mind took a turn for the worse. I began to think of an
adjudicator as a logical reasoning engine, which I suppose is really
what it is, and played several thought experiments.

First, what would happen if the rule paradoxes were fixed? I suppose
that there would be no set of orders that would cause an adjudicator to
loop infinitely. Secondly, why exactly does an adjudicator loop like
that? Because of unresolved circular dependencies, such as "if A then
B; if B then A; if not A then not B; if not B then not A". And then, a
thought experiment I found truly fascinating: what other kinds of
logical problems could be represented as Diplomacy orders on a
particular map with particular units in particular places, and solved
using a judge program?

To get directly to the point, I wonder whether it is possible to encode
any Turing machine, including state diagram and initial "tape" (memory)
contents, as a single Diplomacy map, position, and set of orders;
resolve the orders; and then interpret the resultant position as the
final "tape" contents of the Turing machine. In other words, is the
Diplomacy order resolution process Turing-complete?

This question is quite relevant to the issue of paradoxes, and even
useful. If it were proven that the Diplomacy rules are Turing-complete,
then it must necessarily be true that the rules contain paradoxes, since
Turing machines can loop infinitely. And more importantly, fixing the
Diplomacy rules would render them non-Turing-complete! (Of course, even
if the rules are shown not to be Turing-complete, there still can be
paradoxes.)

I would like to present this problem as a challenge for the Computer
Science variety of Diplomacy players out there. To satisfy the
challenge, some kind of proof by contradiction could be offered that
shows the Diplomacy rules are not Turing-complete, or some algorithm
could be offered for translating the encoding of a Turing machine into a
complete Diplomacy order resolution problem, and for translating the
result back into the final tape contents.

In coming up with an encoding, it should be allowable to have a map of
arbitrary but finite size and structure (not even necessarily a planar
graph, but yet conforming to the rules of land/water adjacencies), and
an arbitrary but finite number of Powers and units (up to the number of
supply centers, of course), with each unit having an arbitrary but legal
location and an arbitrary but valid order.

Also, since all the paradoxes I've ever seen involve the convoy order in
conflict with either the beleaguered garrison rule or, more recently,
the rule that dislodged units do not affect provinces their attackers
come from, it seems natural that these situations would be important for
representing most kinds of iterative/recursive logical operations.

Perhaps it would be helpful to correlate Diplomacy orders resolution to
a known Turing-complete inference engine like Prolog. If any set of
Prolog "rules" can be expressed as a set of Diplomacy orders with map
and units, then Diplomacy is Turing complete.

Or perhaps a highly theoretical language like Unlambda
(http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/) would
actually lend itself to this problem. Unlambda is Turing complete with
only 2 primitive functions and 1 operator, though it includes more
primitives for the pretense of convenience.

It may also be that Diplomacy orders resolution could be more easily
proven equivalent to logic circuits. One can build a Turing complete
system entirely out of 2-input NAND gates and a clock; if some corollary
to the NAND operation can be found within the Diplomacy rules, problem
solved.

Anybody else ever given this question some thought?

--
Will Berry
Co-founder, Second Brain website hosting
http://www.secondbrainhosting.com/
17 answers Last reply
More about diplomacy rules turing complete
  1. Archived from groups: rec.games.diplomacy (More info?)

    High Will,

    I have to disappoint you, but the rules do not have much to do
    with Turing or Godel.

    The Turing Machine has an infinite memory, while the adjudication
    of a finite map, can be calculated by a machine in linear memory
    and in linear execution (in relation to the number of orders).

    It isn't even NPC.

    The mistake that people make is that they try to understand the
    rules as an algorithm. With this you will end in something as
    the DPTG (which contains still 3 bugs).

    However, you should look to the rules as a set of equations.
    Each move order and support order, is a variable with two
    possible values. For the move order that is 'moves' or 'fails'
    and for the support order that is 'cut' or 'given'. The principle
    of equations is very close to the rules. The rules do not
    define things in the form of an algorithm.

    For each order, if you know the value of the surrounding orders,
    you know the result of that order. So, for each order you can
    write an equation.

    Make for each order a equation. Take all those equations and find
    a solution that fullfills these equations. Then you have your
    adjudication.

    A Diplomacy paradox, is a set of equations, where there is no
    solution or more than one solutions.

    You can deal with paradoxes in two ways. Adapt the rules for the
    equations, such that there is always one solution for a set
    (the 1982 rulebook approach). Or, do a paradox detection, and
    introduce a special paradox rule. Examples of such rules are
    the Szykman rule or the All Hold rule.

    The new adjudicators, JDip, DipTool and Palmpolitik do paradox
    detection and use the Szykman rule.

    To make things easier, you can introduce 'derived decisions'.
    Those are:
    - HOLD STRENGTH (value equal or greater than 0)
    - ATTACK STRENGTH (value equal or greater than 0)
    - DEFEND STRENGTH (value equal or greater than 0)
    - PREVENT STRENGTH (value equal or greater than 0)
    - DISLODGED (yes/no)
    - PATH (yes/no)

    For each of these derived decisions you can give precise semantics
    but also precisely how it depends on other decisions.

    Note, that most people make no different between DEFEND STRENGTH
    and PREVENT STRENGTH. The DEFEND STRENGTH is the strength of
    a moving unit to defend in a head to head battle. While the
    PREVENT STRENGTH is the strength to prevent another unit to
    enter the same area as the moving unit. Those two strengths
    are slightly different.

    This is done in my DATC chapter 5:

    http://web.inter.nl.net/users/L.B.Kruijswijk/#5

    Although, the description of the decisions are a little bit mixed
    with the algorithm (this will be corrected in the next version).
    DipTool of Christian Hagenah, uses a different algorithm in finding
    a solution of the equations.

    > It occurred to me that when you feed a paradoxical situation to a judge
    > program, it will loop infinitely, never rendering any resolution of the
    > given orders;
    RealPolitik uses the 1982 rule. JDip, DipTool and Palmpolitik, have
    paradox detection and use the Szykman rule.

    > And then, my mind took a turn for the worse. I began to think of an
    > adjudicator as a logical reasoning engine, which I suppose is really
    > what it is, and played several thought experiments.
    You can see it like this. But it is closer to proposition logic
    (first order logic, because the orders have binary result) and
    not predicate logic (second order logic).

    Regards,

    Lucas
  2. Archived from groups: rec.games.diplomacy (More info?)

    > It may also be that Diplomacy orders resolution could be more easily
    > proven equivalent to logic circuits. One can build a Turing complete
    > system entirely out of 2-input NAND gates and a clock; if some corollary
    > to the NAND operation can be found within the Diplomacy rules, problem
    > solved.
    >
    > Anybody else ever given this question some thought?

    I certainly haven't.

    But if I did .... I think I might need one of your Second Brains to try and
    comprehend the concepts involved. ;)

    > --
    > Will Berry
    > Co-founder, Second Brain website hosting
    > http://www.secondbrainhosting.com/

    Alastair
    (now removing tongue from cheek).

    PS One day soon I'll post something sensible to r.g.d. But I guess it'll
    have to wait until after exam time ...

    PPS Actually I just about managed to almost understand Lucas's response, so
    maybe my First Brain isn't quite as addled as I thought.
  3. Archived from groups: rec.games.diplomacy (More info?)

    Lucas B. Kruijswijk wrote:
    >
    > It isn't even NPC.

    I should hope not! We'd *never* get done playing!


    > However, you should look to the rules as a set of equations.
    > Each move order and support order, is a variable with two
    > possible values. For the move order that is 'moves' or 'fails'
    > and for the support order that is 'cut' or 'given'. The principle
    > of equations is very close to the rules. The rules do not
    > define things in the form of an algorithm.

    Agreed, the rules themselves are not an algorithm. But they are
    requirements for an algorithm, i.e. they describe the required output
    (final state) for any given input (map, unit positions, orders). The
    ambiguities in the rules of course mean that there is more than one
    correct output for certain inputs; and the paradoxes mean that no output
    is correct for certain inputs (i.e. those inputs cause the algorithm not
    to provide output).

    In this way I think it is meaningful to say "are the rules Turing
    complete". But I suppose I should rephrase the problem statement as: Is
    it true that *any* Diplomacy adjudicator algorithm that fully conforms
    to the rules (not just adjudicators that follow some particular design)
    is Turing complete?


    > The Turing Machine has an infinite memory, while the adjudication
    > of a finite map, can be calculated by a machine in linear memory
    > and in linear execution (in relation to the number of orders).

    I agree with this as well, with two caveats. First, "infinite memory"
    need only mean "as much memory as you'll ever use + 1". After all, our
    desktops and laptops are Turing complete, but their memories are quite
    finite; consider also emulators and the Recursion Theorem. And besides,
    if a Turing machine actually uses infinite memory, then it clearly loops
    infinitely and never terminates. Secondly, who says the number of
    provinces and adjacencies on a Diplomacy map, or even the number of
    units on the board, has to be finite? It seems to me that a map/graph
    that extends predictably forever, with units that occur infinitely in
    expressible patterns, will still be compatible with the rules. The same
    decisions can just be repeated for all units according to the patterns
    given.

    I am operating under the assumption that if any Diplomacy adjudicator is
    Turing complete, any implementation of a Universal Turing Machine using
    a Diplomacy adjudicator would construct a map having enough nodes
    ("provinces") and adjacencies as it needs to, in whatever arrangement
    fits the problem, and populate it with as many units of whatever type as
    it sees fit as well, and then issue orders to those units before
    "calling" the adjudicator.

    In other words, the initial tape contents and state diagram of the
    Turing machine must be encoded as (map, unit positions, orders). The
    initial tape contents, by the way, may be infinite if specified as a
    deterministic pattern (i.e. "001" repeating forever) without breaking
    the definition of a Turing machine; though there must always be a finite
    number of states.


    > You can deal with paradoxes in two ways. Adapt the rules for the
    > equations, such that there is always one solution for a set
    > (the 1982 rulebook approach). Or, do a paradox detection, and
    > introduce a special paradox rule. Examples of such rules are
    > the Szykman rule or the All Hold rule.
    >
    > The new adjudicators, JDip, DipTool and Palmpolitik do paradox
    > detection and use the Szykman rule.
    >
    > ...
    >
    >>It occurred to me that when you feed a paradoxical situation to a judge
    >>program, it will loop infinitely, never rendering any resolution of the
    >>given orders;
    >
    > RealPolitik uses the 1982 rule. JDip, DipTool and Palmpolitik, have
    > paradox detection and use the Szykman rule.


    It seems to me that paradox detection is eerily like infinite loop
    detection. The only way I can think of to implement paradox detection
    is like this: Let U be the number of units on the map. If at any time
    the adjudicator processes more than U dependencies without actually
    deciding anything, then it is looping infinitely and it's time to apply
    either the Szykman rule or the "three or more can trade places" rule,
    however you can decide what the "culprits" are. Or something like that.
    Another reasonable loop detection threshold would be the number of
    provinces on the map times the number of adjacencies between provinces;
    but the number of units is always smaller, and each unit can have only
    one order, so U works better.

    But what if the map extends infinitely in a deterministic pattern, and
    has an infinite number of units placed in a deterministic pattern given
    orders according to a deterministic pattern? Then the Szykman rule
    (when implemented as above) breaks due to a count-to-infinity problem.

    For example:

    Map: An infinite set of supply center provinces P for all i >= 0,
    with each P being adjacent by land to P and vice versa
    Units:
    England: An army at P[2i] for all i >= 0
    France: An army at P[2i+1] for all i >= 0
    Orders:
    England: A P[2i] -> P[2i+1] for each army P[2i]
    France: A P[2i+1] hold for each army P[2i+1]

    The final state of this map can be determined in a finite number of
    steps with the proper reasoning; and I hold that this example is within
    the rules of the game (neglecting, of course, departure from the
    standard map and order writing conventions), even though I doubt any
    judge program out there would accept it. (Victory conditions would be
    that a player controlled more than half the supply centers; since the
    number of supply centers is countable this is not a problem.)

    However, when you allow the map and the number of units to become
    deterministically infinite, you can detect paradox about as reliably as
    you can detect an infinite loop in a Turing machine -- that is, never
    perfectly. At least, this seems true to me, and if it can be shown that
    any proper adjudicator is Turing complete, as I suspect, then I will
    know that the Szykman rule and all other in-case-of-paradox rules are
    broken in the general case (even though they may work perfectly on
    finite, "normal" maps) by way of the Halting Problem.


    On a personal note: if it seems like I'm abusing any of you, it's only
    in the way that a chess player seeks out games versus more experienced
    players than himself. That, and as one of my friends says, sometimes I
    just have to find my inner troll and stroke it.

    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  4. Archived from groups: rec.games.diplomacy (More info?)

    "Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk> wrote in message
    > PPS Actually I just about managed to almost understand Lucas's response,
    so
    > maybe my First Brain isn't quite as addled as I thought.

    That's better than me. What the hell are they talking about?

    What are the paradoxes in the rules anyway? I've never seen the infamous
    convoy paradox come up in 10 years of playing Diplomacy.


    Grant
  5. Archived from groups: rec.games.diplomacy (More info?)

    Grant Flowers wrote:
    >
    > What are the paradoxes in the rules anyway? I've never seen the infamous
    > convoy paradox come up in 10 years of playing Diplomacy.

    RUN! Run while you still have your precious little soul!

    http://www.diplomacy-archive.com/diplomacy_rules.htm#Rule%20Issues

    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  6. Archived from groups: rec.games.diplomacy (More info?)

    "Will Berry" wrote:
    > Agreed, the rules themselves are not an algorithm. But they are
    > requirements for an algorithm, i.e. they describe the required output
    > (final state) for any given input (map, unit positions, orders). The
    > ambiguities in the rules of course mean that there is more than one
    > correct output for certain inputs; and the paradoxes mean that no output
    > is correct for certain inputs (i.e. those inputs cause the algorithm not
    > to provide output).
    This is true, but the point I wanted to make is that you have to transform
    the rules in a more formal description as first step.

    This formal description can be an algorithm or a more mathematical description.

    What you see with the DPTG is that the distance between the English rules
    and the DPTG is very large.

    Large gap
    English rules ------------------------ DPTG

    In this way it is very hard to proof that the DPTG is correct. And indeed,
    it is not correct, it contains 3 bugs.

    What I promote is the following:

    small
    gap
    English rules ---- Mathematical description
    / | \
    Alg1 Alg2 Alg3

    So, I am looking to a mathematical description that is very close to the
    original English rules. So, that everyone agrees with this description.
    From this mathematical description you can derive one or more algorithms.
    But, since you are thinking in a more formal way, there is less risk on
    bugs (and no dispute on how it should be interpreted).

    I think I managed to do so in my DATC, although the description and the
    algorithm is still intervened (will be corrected in next update).

    However, if someone finds a better formal way that is closer to the
    original rules, I am certainly interested.

    One thing is clear, in this mathematical description you should not add
    any sequence on how orders are adjudicated. This is not according to the
    rules (so, your distance to the rules becomes larger) and the
    correctness of your description starts to depend on this sequence.
    Since, the sequence in how orders are adjudicated is very complex,
    you run into trouble.

    If you have this mathematical description (without sequence), you will
    see that the best way is to let the computer determine the (very complex)
    sequence at runtime (instead of hard coding) is the better approach.
    Palmpolitik, JDip and DipTool are programmed this way. Although DipTool
    has a different approach then Palmpolitik or JDip.

    About infinity maps. In that moment you don't have computational Turing
    problem anymore. A Turing machine has a infinite tape, but with a finite
    part of the tape with initial values.

    With an infinite map, you get at least one additional paradox. You can
    create an order and unit chain to infinity. Such chain could be
    adjudicated correctly in two ways.

    Regards,

    Lucas
  7. Archived from groups: rec.games.diplomacy (More info?)

    Lucas B. Kruijswijk wrote:
    >
    > About infinity maps. In that moment you don't have computational Turing
    > problem anymore. A Turing machine has a infinite tape, but with a finite
    > part of the tape with initial values.

    I believe IBM OS/390 initializes all new memory to 0xDEADBEEF before
    giving it to the program, to aid debugging in case of a crash. This is
    basically equivalent to an infinite tape with an infinitely repeating
    pattern of initial values.


    > With an infinite map, you get at least one additional paradox. You can
    > create an order and unit chain to infinity. Such chain could be
    > adjudicated correctly in two ways.

    I had never thought of that, but I can see how it could happen. But I'm
    having trouble coming up with an example.

    England:
    Army P[2i] -> P[2i+1], i >= 0
    France:
    Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0
    Army P[4i+3] -> P[4i+2], i >= 0

    With these orders, all French moves fail because all supports are cut.
    You can prove this inductively.

    England:
    Army P[2i] -> P[2i-1], i >= 1
    France:
    Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0
    Army P[4i+3] -> P[4i+2], i >= 0

    Here every other English unit is dislodged. This can likewise be proven
    inductively.

    England:
    Army P[4i] support Army P[4i+2] -> P[4i+1], i >= 0
    Army P[4i+2] -> P[4i+1], i >= 0
    France:
    Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0
    Army P[4i+3] -> P[4i+2], i >= 0

    Here France loses half its units.

    England:
    Army P[4i+2] support Army P[4i] -> P[4i+1], i >= 0
    Army P[4i] -> P[4i+1], i >= 0
    France:
    Army P[4i+1] support Army P[4i+3] -> P[4i+2], i >= 0
    Army P[4i+3] -> P[4i+2], i >= 0

    Here all units standoff.

    I can't think of a scenario where there are two equally valid outcomes,
    but it seems possible. Such a situation might be useful in contructing
    a TM emulator for Diplomacy. Iteration might be simulated as a chain of
    similar attacks, that may or may not succeed, on units that affect other
    parts of the action.

    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  8. Archived from groups: rec.games.diplomacy (More info?)

    "Grant Flowers" <darthvader@SPAMworldnet.att.net> wrote in message
    news:FsNmc.29045$Ut1.834860@bgtnsc05-news.ops.worldnet.att.net...
    >
    > "Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk> wrote in
    message
    > > PPS Actually I just about managed to almost understand Lucas's response,
    > so
    > > maybe my First Brain isn't quite as addled as I thought.

    > That's better than me. What the hell are they talking about?

    It's OK. The subsequent conversation has totally lost me. Normal service is
    resumed.

    > What are the paradoxes in the rules anyway? I've never seen the infamous
    > convoy paradox come up in 10 years of playing Diplomacy.

    And I agree with Will. Run like the wind away from that particular thread of
    discussion ....

    Alastair
  9. Archived from groups: rec.games.diplomacy (More info?)

    Alastair Tomlinson wrote:
    > "Grant Flowers" <darthvader@SPAMworldnet.att.net> wrote in message
    > news:FsNmc.29045$Ut1.834860@bgtnsc05-news.ops.worldnet.att.net...
    >
    >>That's better than me. What the hell are they talking about?
    >
    > It's OK. The subsequent conversation has totally lost me. Normal service is
    > resumed.

    For the masochistic, here is a good definition of the Turing machine and
    an applet that simulates one:

    http://en.wikipedia.org/wiki/Turing_machine
    http://www.igs.net/~tril/tm/


    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  10. Archived from groups: rec.games.diplomacy (More info?)

    "Will Berry" wrote:
    > I can't think of a scenario where there are two equally valid outcomes,
    > but it seems possible.
    What about:

    Army p -> p for i >= 0

    ?

    It is not a circular movement, but a movement into infinity.

    It can all fail or all succeed.

    The nice thing about these moves is, that if p[0] has supply center,
    then you may build. However, you will still keep the same number of
    armies :-))

    Regards,

    Lucas
  11. Archived from groups: rec.games.diplomacy (More info?)

    Lucas B. Kruijswijk wrote:
    >
    > Army p -> p for i >= 0
    >
    > It is not a circular movement, but a movement into infinity.
    >
    > It can all fail or all succeed.

    One could argue that this should have the same result as a circular
    movement (i.e. all moves succeed), since it is necessary in both cases
    to detect a loop in order to actually reach any decision. I prefer that
    all moves succeed, but I wouldn't insist that the official rules are
    sufficiently precise to justify such an opinion.


    > The nice thing about these moves is, that if p[0] has supply center,
    > then you may build. However, you will still keep the same number of
    > armies :-))

    However, it could give you the win when ordering all to hold would not,
    depending on how you account for an infinite number of SCs. I would
    personally prefer to say that <inf> + 1 = <inf> for the purpose of
    counting centers, but 2 * <inf> would in fact be greater than <inf>.
    This way, if a power were able to double his centers, that could give
    him the win; but merely increasing his centers by a constant number
    would not affect anything for that purpose.


    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  12. Archived from groups: rec.games.diplomacy (More info?)

    Lucas B. Kruijswijk wrote:
    >
    > This is true, but the point I wanted to make is that you have to transform
    > the rules in a more formal description as first step.

    I'm seeing your point here now. Since there are several logically
    different ways of interpreting the English rules into an algorithm, only
    some of those valid ways might be Turing complete. This actually
    increases the usefulness of the problem, because it tells us which
    interpretations of the rules definitely have paradoxes and which ones
    may or may not.


    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  13. Archived from groups: rec.games.diplomacy (More info?)

    "Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk>
    > > What are the paradoxes in the rules anyway? I've never seen the
    infamous
    > > convoy paradox come up in 10 years of playing Diplomacy.
    >
    > And I agree with Will. Run like the wind away from that particular thread
    of
    > discussion ....

    Well, like the big Dipper I am, I'm not being totally honest. I kind of
    know what the paradox is, but I can't believe the amount of bandwidth it has
    devoured during the 10 years or so I've been reading RGD.

    A few weeks ago I tried to launch a thread in which people might talk about
    some of the comic anecdotes they've experienced in FTF games, but met with
    little response. Why is it that the convoy paradox gets so much attention
    from RGD posters but the play of the game itself achieves so little? If I
    were a newbie coming across this newsgroup I'd think it was the most boring
    game ever created.

    Anyway, back to lurking...


    Grant
  14. Archived from groups: rec.games.diplomacy (More info?)

    "Grant Flowers" <darthvader@SPAMworldnet.att.net> writes:

    Hi Grant, I've always enjoyed both parts of this sort of
    conversation, since I'm well trained in mathematical logic
    techniques, Turing machines, Kurt Godel and the MISuses of
    the Incompleteness Theorem, and non-cooperative game theory,
    BUT I view the more fun way to deal with and play the game
    is better informed by psychology and Zen philosophy. This
    makes the Game of Diplomacy THE game, in my eyes, since it
    really does "have it all". What you are supposed to do
    (IMHO, wink, wink...) is to salute those of us who battle
    down the mathematical logic highways and byways, even if
    you don't want to follow along, since you plan to saw off
    their branch and stab the hell out of them once they get
    far enough off the edge...... but now to the question...

    >"Alastair Tomlinson" <agtomlinson.nospamplease@yahoo.co.uk>
    >> > What are the paradoxes in the rules anyway? I've never seen the
    >infamous
    >> > convoy paradox come up in 10 years of playing Diplomacy.
    >>
    >> And I agree with Will. Run like the wind away from that particular thread
    >of
    >> discussion ....

    >Well, like the big Dipper I am, I'm not being totally honest. I kind of
    >know what the paradox is, but I can't believe the amount of bandwidth it has
    >devoured during the 10 years or so I've been reading RGD.

    The reason, quite simply is that there are the people that like these
    aspects of trying to solve the game. The same people who like to
    debate paradox completeness tend to like to study stalemate lines.
    The neat thing about Diplomacy IS that it can attract that type of
    debate while being a completely unsolvable game (i.e. it never will
    be anywhere close to tic-tac-toe or even chess in its solvability).
    That's why it absorbs bandwidth....

    >A few weeks ago I tried to launch a thread in which people might talk about
    >some of the comic anecdotes they've experienced in FTF games, but met with
    >little response. Why is it that the convoy paradox gets so much attention
    >from RGD posters but the play of the game itself achieves so little? If I
    >were a newbie coming across this newsgroup I'd think it was the most boring
    >game ever created.

    Ideally, we would see both. I've told my BEST comic anecdotes here
    before, but I'll tell two of them again. FTF is the BEST place for
    really funny stuff and you HAVE to get the personalities involved
    to really understand it, thus you only will "get" the second one
    in all likelihood.

    The first one happened at a PudgeCon in 1983, over 20 years ago
    now. "Pudge" is Bob Olsen, who was a famous player of his time,
    who lived in Wichita at the time and hosted large numbers of
    players at his house for weekends of gaming. I was in a game
    with the late Kathy Byrne Caruso and Eric Ozog (who still plays
    FTF in the Pacific Northwest sometimes). I can't really remember
    the details of the game, since they don't really matter. But
    I had been elected 1982 Toady of the Year and Kathy was the Queen
    Toad of the time, so I "should" have been doing her bidding.
    I was playing Russia and stabbed her Germany. Of course, Kathy
    came right back and worked up an alliance that CRUSHED me.
    I forget what country Eric was playing, but at one point,
    some really funny moves were played, as I desperately tried
    to survive (Kathy, in her Queens accent you have to remember
    was continually telling EVERYONE in earshot what a dirty rotten
    toady I really was in a VERY loud voice), Eric did something
    that kind of helped me, not very much, but a little bit.
    And the two of us went out on the front step and fell down
    laughing and almost missed the next turn..... ;-)
    It was completely hilarious and totally stupid all at the same
    time. And it had nothing to do with being Turing Complete.

    The other one was at a Diplomatic Incident in Boston, where
    I was playing with, among others, Dan Shoham. I pulled off
    this massive stab of Dan (who really at heart WAS just a Carebear
    who liked to win) that devastated his position and Dan was
    just SO shocked. How could I lie to him like that? I got
    an award at that Incident for that stab, that was about 10
    years ago.... I had completely set him up (think non-cooperative
    game theory to the next level....) and again I could hardly
    keep playing I was giggling so hard. Dan's JDPR remains
    eons ahead of where mine will never be..... ;-)

    >Anyway, back to lurking...


    >Grant

    Yes, Grant, REAL r.g.d will have all of that....

    Jim-Bob
  15. Archived from groups: rec.games.diplomacy (More info?)

    Would there be an issue if the Turing program always completed, but gave
    different answers depending on the order in which it was given the
    orders?

    On Thu, 6 May 2004, Will Berry wrote:

    > Jim Burgess wrote:
    > >
    > > It is depressing to JUST see messages from the spammers and about
    > > the spamming. Anyone have any real comments or questions??
    > >
    > > I'm looking for articles for the next issue of Diplomacy World,
    > > just one more month to write them!! Contact me for editorial
    > > guidance or details.
    >
    > I won't have the free time to spit and polish any formal essay for a Dip
    > publication in the next month, but I have been mulling over one highly
    > theoretical topic for the past few weeks. Perhaps others have discussed
    > this in other publications; I don't know. (If someone has seen detailed
    > discussions like this before, I'd be interested in a link or something.
    > The closest thing I've found is a brief mention of Godel's Theorem
    > applied to Diplomacy in a thread back in 2001.)
    >
    > As you may be aware from my recent posts, I have found far too much
    > personal amusement in the various rule problems of this otherwise very
    > high-quality game. The rule paradoxes trouble me especially. One day I
    > got in an e-mail argument with a friend who believes that there really
    > are no paradoxes in the rules, merely ambiguities. His arguments seemed
    > spurious to me, though, and I tried to devise how I might prove to him
    > logically that there really are paradoxes in the rules.
    >
    > It occurred to me that when you feed a paradoxical situation to a judge
    > program, it will loop infinitely, never rendering any resolution of the
    > given orders; whereas with orders that illustrate ambiguities, the judge
    > program will eventually produce an outcome according to programmer bias.
    > And then, my mind took a turn for the worse. I began to think of an
    > adjudicator as a logical reasoning engine, which I suppose is really
    > what it is, and played several thought experiments.
    >
    > First, what would happen if the rule paradoxes were fixed? I suppose
    > that there would be no set of orders that would cause an adjudicator to
    > loop infinitely. Secondly, why exactly does an adjudicator loop like
    > that? Because of unresolved circular dependencies, such as "if A then
    > B; if B then A; if not A then not B; if not B then not A". And then, a
    > thought experiment I found truly fascinating: what other kinds of
    > logical problems could be represented as Diplomacy orders on a
    > particular map with particular units in particular places, and solved
    > using a judge program?
    >
    > To get directly to the point, I wonder whether it is possible to encode
    > any Turing machine, including state diagram and initial "tape" (memory)
    > contents, as a single Diplomacy map, position, and set of orders;
    > resolve the orders; and then interpret the resultant position as the
    > final "tape" contents of the Turing machine. In other words, is the
    > Diplomacy order resolution process Turing-complete?
    >
    > This question is quite relevant to the issue of paradoxes, and even
    > useful. If it were proven that the Diplomacy rules are Turing-complete,
    > then it must necessarily be true that the rules contain paradoxes, since
    > Turing machines can loop infinitely. And more importantly, fixing the
    > Diplomacy rules would render them non-Turing-complete! (Of course, even
    > if the rules are shown not to be Turing-complete, there still can be
    > paradoxes.)
    >
    > I would like to present this problem as a challenge for the Computer
    > Science variety of Diplomacy players out there. To satisfy the
    > challenge, some kind of proof by contradiction could be offered that
    > shows the Diplomacy rules are not Turing-complete, or some algorithm
    > could be offered for translating the encoding of a Turing machine into a
    > complete Diplomacy order resolution problem, and for translating the
    > result back into the final tape contents.
    >
    > In coming up with an encoding, it should be allowable to have a map of
    > arbitrary but finite size and structure (not even necessarily a planar
    > graph, but yet conforming to the rules of land/water adjacencies), and
    > an arbitrary but finite number of Powers and units (up to the number of
    > supply centers, of course), with each unit having an arbitrary but legal
    > location and an arbitrary but valid order.
    >
    > Also, since all the paradoxes I've ever seen involve the convoy order in
    > conflict with either the beleaguered garrison rule or, more recently,
    > the rule that dislodged units do not affect provinces their attackers
    > come from, it seems natural that these situations would be important for
    > representing most kinds of iterative/recursive logical operations.
    >
    > Perhaps it would be helpful to correlate Diplomacy orders resolution to
    > a known Turing-complete inference engine like Prolog. If any set of
    > Prolog "rules" can be expressed as a set of Diplomacy orders with map
    > and units, then Diplomacy is Turing complete.
    >
    > Or perhaps a highly theoretical language like Unlambda
    > (http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/) would
    > actually lend itself to this problem. Unlambda is Turing complete with
    > only 2 primitive functions and 1 operator, though it includes more
    > primitives for the pretense of convenience.
    >
    > It may also be that Diplomacy orders resolution could be more easily
    > proven equivalent to logic circuits. One can build a Turing complete
    > system entirely out of 2-input NAND gates and a clock; if some corollary
    > to the NAND operation can be found within the Diplomacy rules, problem
    > solved.
    >
    > Anybody else ever given this question some thought?
    >
    > --
    > Will Berry
    > Co-founder, Second Brain website hosting
    > http://www.secondbrainhosting.com/
    >
  16. Archived from groups: rec.games.diplomacy (More info?)

    George D. Phillies wrote:
    > Would there be an issue if the Turing program always completed, but gave
    > different answers depending on the order in which it was given the
    > orders?

    I suppose that would mean that the method of encoding the machine as
    (map, state, orders), or of decoding the result into the final tape
    contents, was flawed.

    --
    Will Berry
    Co-founder, Second Brain website hosting
    http://www.secondbrainhosting.com/
  17. Archived from groups: rec.games.diplomacy (More info?)

    "George D. Phillies" <phillies@WPI.EDU> writes:

    That would be very bad... it's difficult to get computers
    to consider things simultaneously, but the simultaneous
    movement characteristic is critical.

    Jim-Bob

    >Would there be an issue if the Turing program always completed, but gave
    >different answers depending on the order in which it was given the
    >orders?

    >On Thu, 6 May 2004, Will Berry wrote:

    >> Jim Burgess wrote:
    >> >
    >> > It is depressing to JUST see messages from the spammers and about
    >> > the spamming. Anyone have any real comments or questions??
    >> >
    >> > I'm looking for articles for the next issue of Diplomacy World,
    >> > just one more month to write them!! Contact me for editorial
    >> > guidance or details.
    >>
    >> I won't have the free time to spit and polish any formal essay for a Dip
    >> publication in the next month, but I have been mulling over one highly
    >> theoretical topic for the past few weeks. Perhaps others have discussed
    >> this in other publications; I don't know. (If someone has seen detailed
    >> discussions like this before, I'd be interested in a link or something.
    >> The closest thing I've found is a brief mention of Godel's Theorem
    >> applied to Diplomacy in a thread back in 2001.)
    >>
    >> As you may be aware from my recent posts, I have found far too much
    >> personal amusement in the various rule problems of this otherwise very
    >> high-quality game. The rule paradoxes trouble me especially. One day I
    >> got in an e-mail argument with a friend who believes that there really
    >> are no paradoxes in the rules, merely ambiguities. His arguments seemed
    >> spurious to me, though, and I tried to devise how I might prove to him
    >> logically that there really are paradoxes in the rules.
    >>
    >> It occurred to me that when you feed a paradoxical situation to a judge
    >> program, it will loop infinitely, never rendering any resolution of the
    >> given orders; whereas with orders that illustrate ambiguities, the judge
    >> program will eventually produce an outcome according to programmer bias.
    >> And then, my mind took a turn for the worse. I began to think of an
    >> adjudicator as a logical reasoning engine, which I suppose is really
    >> what it is, and played several thought experiments.
    >>
    >> First, what would happen if the rule paradoxes were fixed? I suppose
    >> that there would be no set of orders that would cause an adjudicator to
    >> loop infinitely. Secondly, why exactly does an adjudicator loop like
    >> that? Because of unresolved circular dependencies, such as "if A then
    >> B; if B then A; if not A then not B; if not B then not A". And then, a
    >> thought experiment I found truly fascinating: what other kinds of
    >> logical problems could be represented as Diplomacy orders on a
    >> particular map with particular units in particular places, and solved
    >> using a judge program?
    >>
    >> To get directly to the point, I wonder whether it is possible to encode
    >> any Turing machine, including state diagram and initial "tape" (memory)
    >> contents, as a single Diplomacy map, position, and set of orders;
    >> resolve the orders; and then interpret the resultant position as the
    >> final "tape" contents of the Turing machine. In other words, is the
    >> Diplomacy order resolution process Turing-complete?
    >>
    >> This question is quite relevant to the issue of paradoxes, and even
    >> useful. If it were proven that the Diplomacy rules are Turing-complete,
    >> then it must necessarily be true that the rules contain paradoxes, since
    >> Turing machines can loop infinitely. And more importantly, fixing the
    >> Diplomacy rules would render them non-Turing-complete! (Of course, even
    >> if the rules are shown not to be Turing-complete, there still can be
    >> paradoxes.)
    >>
    >> I would like to present this problem as a challenge for the Computer
    >> Science variety of Diplomacy players out there. To satisfy the
    >> challenge, some kind of proof by contradiction could be offered that
    >> shows the Diplomacy rules are not Turing-complete, or some algorithm
    >> could be offered for translating the encoding of a Turing machine into a
    >> complete Diplomacy order resolution problem, and for translating the
    >> result back into the final tape contents.
    >>
    >> In coming up with an encoding, it should be allowable to have a map of
    >> arbitrary but finite size and structure (not even necessarily a planar
    >> graph, but yet conforming to the rules of land/water adjacencies), and
    >> an arbitrary but finite number of Powers and units (up to the number of
    >> supply centers, of course), with each unit having an arbitrary but legal
    >> location and an arbitrary but valid order.
    >>
    >> Also, since all the paradoxes I've ever seen involve the convoy order in
    >> conflict with either the beleaguered garrison rule or, more recently,
    >> the rule that dislodged units do not affect provinces their attackers
    >> come from, it seems natural that these situations would be important for
    >> representing most kinds of iterative/recursive logical operations.
    >>
    >> Perhaps it would be helpful to correlate Diplomacy orders resolution to
    >> a known Turing-complete inference engine like Prolog. If any set of
    >> Prolog "rules" can be expressed as a set of Diplomacy orders with map
    >> and units, then Diplomacy is Turing complete.
    >>
    >> Or perhaps a highly theoretical language like Unlambda
    >> (http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/) would
    >> actually lend itself to this problem. Unlambda is Turing complete with
    >> only 2 primitive functions and 1 operator, though it includes more
    >> primitives for the pretense of convenience.
    >>
    >> It may also be that Diplomacy orders resolution could be more easily
    >> proven equivalent to logic circuits. One can build a Turing complete
    >> system entirely out of 2-input NAND gates and a clock; if some corollary
    >> to the NAND operation can be found within the Diplomacy rules, problem
    >> solved.
    >>
    >> Anybody else ever given this question some thought?
    >>
    >> --
    >> Will Berry
    >> Co-founder, Second Brain website hosting
    >> http://www.secondbrainhosting.com/
    >>
Ask a new question

Read More

Video Games