I should say I tend to look for stalemate lines on the go, so the ones I've found thus far have been ones relevent to games I've been in. There are a lot more than this.

If you're looking to become uneliminatable as an eastern power (China, Turan, India, Srivijaya) then you can form a minimal stalemate line with 20 centers:

(Starts at Silla, just east of China's start, goes west and then south after reaching Ujjain)

A Sil
F YeS
A Hen & A Sic S A ChA
A Tib S A Amd
A Nep S A Kas
A Ind S A Sha
A Knj & A Ras S A Ujj
A Cho H
F Cor H
F Ser H
F Min & F Jam S F SuS

20 units

Holds 20 centers (Ser, Cho, Ujj, Knj, Ind, Kas, Var, Tib, Pag, ChA, Nan, Gua, Sil, Sai, Kam, Cah, Jam, Plm, Kal, But)

Once you start getting boardwide effort to stop a major power or alliance, you can defend many more centers using almost the same number of units:

(Starting from the Western Sea, just west of Wagadu's starting location, and stretching West to East)

F WtS H
F Tka & F Mau S F STa
A Kut & A Tah S A Ifr
A Tri S A Bar
A Ale & A Mec S A Jer
A Oma & A Yem S A Nef
F Ara-Bsr (prevent transformation to fleet, if it ever moves, move it back again next turn)
A Sha S A Man
A Amd & A Kas S A Sog
A Hen S A Yan
F YeS S A Blh

25 units

45 Centers (Tka, Awl, KuS, Nio, Wal, JeJ, Mau, Ifr, Zaw, Kan, Bar, Ale, AQa, Mak, Axu, Adu, Roh, Mal, Zim, Mah, Jer, Yem, Soc, Man, Ujj, Ind, Knj, Kas, Tib, Var, Cho, Ser, Plm, Jam, Kal, Cah, But, Kam, Pag, Gua, ChA, Nan, Yan, Sai, Sil)

If you're stalemating a single player and not an alliance, your stalemate line must control at least 55 centers to prevent the solo. There are a number of places you can extend the line forwards - the most unit efficient is probably pushing forward into 3 of the mediterreanean islands and 7 of the easily claimed centers in front of the Asian part of the previous line:

(Again starting at Western Sea, stretching west to east)

F WtS H
F Tka & F Mau S F STa
A Kut S A Ifr
F LiS S F Sic (& vice versa)
F EgS & F Cre & F Cyp S F CiS
F STy & A Jer S A Dam
A Nef S A Bag
A Bas S A Isf
A Sjs S A Kho
A Her S A Buk
A Blk & A Uyg S A Sam
A Yan S A Chn
A YeS S A Blh

30 units

Holds 55 centers (all those of the previous line + Sic, Cre, Cyp, Bag, Isf, Bas, Her, Buk, Sam, Uyg).

It's easy to see that centers like OrB could be easily added to a line like this - just as in Classic, the more centers you control, the easier it will be to form a stalemate line. This is the minimal unit east-west line that protects exactly 55 centers though (I think).

There are a fair few North-South lines too, but I've spent enough time typing these out today :D

Stalemate lines in Known World 901. Now I am sad.

In the two variants I am working on now, I am going the extra mile, or kilometer if you swing that way, to avoid stalemates having an impact on the game. Both will have victory criteria of less than a majority of the dots. One of them should be especially. stalemate resistant. It will be a true global variant with a wraparound map, so there will be no corners. It will also feature high seas provinces (multiple fleets allowed), and be significantly less densely "dotted" than Standard, so more capacity and room for maneuver.

@David what happens if two players reach the victory SC threshold in the same turn?

@DEC - With computers, you should be able to systematically check for stalemate positions.

I really liked Known World, thanks DEC. Only played it once as a slow gunboat, but the neutral armies, transform feature and beautiful map made it a really fun experience (not a big fan of gunboating normally)

I don't think that's an easy problem for a computer, Carebear...

Not necessarily trivial, but I am certain work in that space was already done with the standard board. The same algorithm, with some tweaks, should be able to do other boards.

In response to

Condescension: If Player 1 exceeds the victory criterion by a greater amount than Player 2 other, then Player 1 is the winner. If both exceed the victory criterion by an equal amount, then play continues until either one player exceeds the victory criterion by a greater amount than all the other players, or only one player has achieved the victory criterion. Note, I am not the first person to use this formula in a Dip variant.

Carebear: Not in my skillset, even if I had the desire, which I do not. I do not want to make it easier for people to "achieve" a stalemate.

Also, for Standard, all that stalemate line stuff was worked out manually, in the early days of the Hobby.

Adamious: For the transform feature, you have Kaner406 to thank. He modified my variant (he also did not implement the special Pharaonic Canal rule), so really you guys are playing a variant of a variant. :^)

Presumably if such a program exists, you could also use it to check to see if any maps you are developing have stalemate lines, and if desired, eliminate them.

The problem with making a program like that is the number of combinations you'd have to check. I'm fairly sure it increases massively with each extra center on the board, so checking something like KW901 is far harder than Classic.

@DEC - What Zybodia said.

@CptM. - Yes, I understand. However, there are non-trivial techniques for approaching problems like this that reduce computational roadblocks. Knuth - The Art of Computer Programming is a great read for problems like this.

I suppose so, but I do pretty well on Brain 1.0. Of course, there are several variant design rules of thumb that make stalemate lines more difficult to form. These include, but are not limited to:

1. Lowering Map Density. Increasing the ratio of non SC provinces to SC provinces, especially if they are usefully placed, will hinder stalemate line formation, as well as providing freedom of movement, which will generally makes for more flexible and exciting play..

2. Avoiding Geographic Bottlenecks. Impassable areas which channel movement and long thin provinces with lots of compact provinces on either side, increase the likelihood of and facillitate stalemate line formation.

3. Allowing Freedom to Build. The more freedom a player has to build, that is, moving toward a Chaos-style build rule and away from Standard (or worse) build restrictions, the more difficult it will be to form a stalemate line.

4. Lessening Victory Criteria. Stayng away from supermajority dot ownership, and indeed lowering it below a majority, while also avoiding specific SC ownership requirements or other limitations will lessen the influence of stalemates on gameplay.

I'm fairly certain I could make an efficient algorithm to detect whether, given a set of 'friendly' provinces, they could all be protected by a stalemate line. It's a simple enough task given the board size...

Delete all enemy provinces that a) are not adjacent to a friendly province or b) are only connected to friendly province by a sea route and cannot be reached from an enemy HSC by fleets.
Find the border provinces (provinces bordering at least one enemy province)
For each border province b, set a variable K(b) to be equal to the number of enemy provinces adjacent to it - 1.
Delete all enemy provinces.
Delete all friendly provinces that are not either a border province or adjacent to a border province.
For each friendly province c which is not a border province and is only connected to one border province b, decrease K(b) by one and then delete c.

The problem is now:

Divide (not completely, you can have some left over) the remaining non-border provinces into disjoint sets v1, v2, v3... such that every border province can be mapped to a set which is contained entirely in its set of neighbours, and which has size equal to its k value. Additionally, the sum of the sizes of the sets must be less than or equal to the number of Supply Centers in friendly territory.

I don't know if there's an efficient way to do that, but brute forcing it shouldn't be too time consuming when we're talking about even a large Diplomacy board.

There's a few problems with this, though:

While everything that shows as 'true' as a result of this algorithm is indeed a stalemate line (with units in every border province and every province inside a V set, the ones inside a V set support holding the border province mapped to them) - not all stalemate lines will be found:

First, this algorithm doesn't take into account that, if a border province has enemy neighbour set E, it can support hold any adjacent border province where the neighbour set contains E without the cutting of support being a problem.

Second, this algorithm only covers passive stalemate lines. It misses active stalemates - lines where units are used aggressively instead of defensively. In a stalemate line, if you do not have enough units to support hold province A, you can use two units to constantly attack two different enemy units adjacent to province A in order to decrease the number of supports A must have by one. However, the two units you are using need one more adjacent unit than before (because they'll need to be protected by support moves rather than support holds).

I think this can be done with more than two units, also - with each extra 'active' unit decreasing the number of support holds needed for A by one.

I *think* if these two scenarios can be covered then you cover everything. Of course, this is with standard Diplomacy rules.

The real issue is that this is a verification algorithm. You'll have to feed it every single possible set of friendly provinces on the board - and that becomes a massive number, two to the power of the number of provinces on the board. On the smallest variant ever made (Pure, 7 provinces) this would be 2^7=128 combinations, on Classic it would be 2^75, which is insanely high (22 digits). It would grow much higher with maps like Known World.

You can't just check combinations which are a graph-cut because they miss stalemates like the Classic Turkey-England one, where the extra northern centers allow you to hold a completely unconnected area of the board.

I should reword that starting line...

"I'm fairly certain I could make an efficient algorithm to detect whether, given a set of 'friendly' provinces, they could all be protected by a stalemate line."

should be

"I'm fairly certain I could make an efficient algorithm to detect whether, given a set of 'friendly' provinces, they could all be protected by a stalemate line *which protects no other provinces*"

Actually it would be better as "Which has no friendly units outside of those provinces" rather than "which protects no other provinces". That is, it's assumed that every province not in the friendly set is occupied by an enemy unit.

Also @David -

I disagree with your design point #4.

Lowering the victory conditions below 50% of the Supply Centers often allows powers to solo without having to interact at all with players doing well on other parts of the board. This is a problem we often see over at vDip with WWIV, with the victor generally only 3 or 4 SCs ahead of a number of other players who had no chance to reach him in time to stop him.

Diplomacy should not be on a time-limit by default, and that is what putting a lower victory condition does to the game.

I will agree that lowering a victory criterion is not something that should be done lightly, I am using variable, reduced victory criteria in the global variant I am working on (Dawn of the Enightenment) mainly because, unlike in most of my variants, the Powers are starting out unequal. I have certain Powers starting all the way up at 9 units, including 3 with double strength, while other Powers are starting with only three units. Also the variant is so large, it will take a VERY long time even with reduced victory criteria. Additionally, the interaction problem you mention is lessened, because this variant starts in 1701, so there are a bunch of Powers with starting dots scattered across the globe. For example, Portugal, having units in Macau and Goa, may well be communicating with Russia, having units in Irkutsk and Okhotsk, at the beginning of the game, concerning their common neighbors, India and China.