basic endgames

So my new years resolution is to learn something about this game.

There are two ways to win a 4ir game, it seems to me. You can win by "tactics", i.e. you find a series of forcing moves which ends up with 4 in a row. Example (X=P1=yellow, O=P2=red)

<font face="courier"><br/><br/>h . . . . . . . .
<br/>g . . . . . . . .
<br/>f . . . . . . . .
<br/>e . . . . . . . .
<br/>d . . . . . . . .
<br/>c . . . . . . . .
<br/>b . O X X . . . O
<br/>a . O X X . . . O
<br/>  1 2 3 4 5 6 7 8
<br/><br/>    </font>

Here X can win with e.g. the sequence c3, forcing d3, and then (all O's moves are forced) c4, d4, a5, a6, b5, b6, c5, c6, d6 [if I got it right].

But you can also win by "strategy", by which I mean that once all "tricks" like the above are gone, you still might win because your opponent must move if they can, and they don't want to. For example

<font face="courier"><br/><br/>h . . O O O X O O
<br/>g . . O X X O X X
<br/>f . . X O O X O O
<br/>e . . O X X O X X
<br/>d . . X O O X O O
<br/>c . . O X X O X X
<br/>b . . X O X X X O
<br/>a . . O X X O X O
<br/>  1 2 3 4 5 6 7 8
<br/><br/>    </font>

I hope I've got this one right. In fact let me post now to see if the boards are coming out OK.

If I've got it right, X=P1 will win this game, not because of tactics, but because he will get e2. It's X to move; he just plays a2 and then waits, and wherever O moves, X just goes on top, and you see that O is doomed. X wins because he has an "odd threat"---that is, he has 3 in a row, and the 4th stone is in an odd row. Any seasoned player knows this sort of thing backwards (and I am just working it all out now, or at least trying to).

Hmm, I haven't got it right; curses. I now see that X has to be careful because O has some threats. Let me fix the problem by filling in row 1 like this:

<font face="courier"><br/><br/>h O . O O O X O O
<br/>g X . O X X O X X
<br/>f O . X O O X O O
<br/>e X . O X X O X X
<br/>d O . X O O X O O
<br/>c X . O X X O X X
<br/>b O . X O X X X O
<br/>a X . O X X O X O
<br/>  1 2 3 4 5 6 7 8
<br/><br/>    </font>

OK so now, hopefully, X plays a2 and wins simply because the rules of the game say O has to move if he can, so X gets e2 and wins.

Ok so now finally here's my question. If and when all the tactics are gone, and the endgame becomes "strategic", there will be a list of rules by which one can work out who is going to win. A good player presumably knows a huge amount of this list.

The list starts like this.

ONE THREAT

----------

If P1 has one threat and P2 has no threats then P1 wins if the threat is on an odd row, and it's a draw (a tie) otherwise. If P1 has no threats and P2 has a threat then P2 wins if the threat is on an even row, and it's a draw otherwise.

The next bit of the list is much more lengthy :-/ I should probably start using what appears to be standard technology: the threat of e2 in the position above seems to be called a "major threat".

TWO THREATS

-----------

If P1 has two major threats (and P2 has none) then P1 wins if one of them is on an odd row, and it's a draw otherwise. Similarly if P2 has two major threats then he wins if one is on an even row, and it's a draw if both are on odd rows.

If P1 and P2 have one major threat each, and if they are in different columns, then P1 wins if his is on an odd row and P2's is on an even row, it's a tie if they are both on odd rows, P2 wins if they're both on even rows, and it's a tie if P2's is on an odd row and P1's is on an even row.

However, if both major threats are in the same column, then P1 wins if his is on an odd row under P2's threat, even if P2's threat is also on an odd row. etc etc etc.

This list, in the form that I'm currently thinking about it, goes on and on and on. But that's almost certainly because I haven't grasped the basic principles of how to really think about these threats.

So how do the experts think about / remember these threat patterns? Looking at

http://homepages.cwi.nl/~tromp/c4.html

the section called "Threat Analysis" is a summary of what is clearly a better system---but at this point in my life, what is presented there is far too succinct for me to understand. Can anyone point me to an explanation which is less terse than the one there, but less verbose than the one I would end up creating if I continued in the vein above?

What I remember from a paper I've read is that in 8x8, P1 (Yellow) prefers odd threats and P2 (Red) prefers even threats.

Even threat means a threat at at even row (row b, d, f and h).

Odd threat means a threat at at odd row (row c, e and g).

Yes but what I'm saying is that that's not enough in practice. For example, even in the part of the story I worked out above, you can see "counterexamples" to your "rule of thumb". For example, if P1 gets an odd threat then P2 will lose if he makes a random even threat (unless it happens to be directly under the odd threat); a natural way for P2 to tie is to make an *odd* threat in another column! If one is going to play this game well, one needs to know a lot more than the rule of thumb---one probably has to know much more details about how these endgames work out. That's why I am asking how the experts have generalised it.

OK, so if no expert will reply then I will just occasionally post here when I have my own small insights, which I'm getting from playing 4ir games on this server.

Firstly, I have realised one theorem which makes yper's remark very concrete:

Theorem: *If P1 has no odd threats then he will not win the game.*

The proof is that P2 can just "play on top". Note that the converse is _not_ true: if P1 has an odd threat and P2 has an odd threat and an even threat, all in distinct columns, then (if I've got it right) P1 will have to sacrifice his odd threat, and then P2 sacrifices his odd threat, and then P2 wins with his even threat.

Note that P2 can have no even threats and still win: P2 can make two odd threats in distinct columns and this is enough for him. Conversely P2 can have even threats and still lose: for example if P1 has an odd threat in a distinct column. So there is no analogue of the theorem for P2, as far as I can see. This aspect of the game (endgame strategy when all tactics are gone) is *highly* asymmetric, it seems to me.

My main problem currently is that I don't know enough "theorems" like the above and am hence having to work out each strategic endgame by hand. What one wants are general results of the following form:

Theorem: *if P1 has an odd threat and P2 has (a) no odd threats and (b) no even threats under P1's odd threat, then P1 wins.*

Proof: P1 makes all columns other than his threat column have even height, and makes his threat column have odd height, and then just plays on top.

So there are two tentative first steps towards what I am aiming for.

the best is for yellow to make a even and oneven threat

and for red 2 even or 2 oneven

had yellow a oneven must make red also oneven to can win

oneven = odd.

I don't see why 2 even threats are ever more useful to red (P2) than one even threat.

Here's a theoretical result. Imagine a game on a 1000x1000 board, with all tactics gone, and just major threats left, all on different columns. Say Yellow (P1) has 23 odd threats and 57 even threats, and red has 41 odd threats and 42 even threats. Who wins?

OK so here's the general result.

Theorem. If all that is left of a game is major threats, all on distinct columns, then:

(1) If P1 has more odd threats than P2, then P1 wins.

(2) If P2 has at least two more odd threats than P1, then P2 wins.

(3) In the remaining cases [P1 odd threats = P2 odd threats, or P2 has one more than P1] then: if P2 has no even threats at all, it will be a tie, and if P2 has at least one even threat, it will be a win for P2.

In particular, in these particularly simple endgames, it's a race to see who gets the most odd threats, and if that race is tied then one even threat is enough for P2. It's also, currently, almost impossible to see what the use of even threats for P1, other than the fact that if they are under P2 odd threats then they are neutralising them.

This also makes me wonder if there is any situation where two even threats for P2 is strictly more useful than 1 even threat (in the absence of tactics, or orders of threats on columns), other than the fact that an even threat for P2 on a column neutralises an odd threat for P1 higher up on the same column.

1000x1000 board you said : red wins that

how do i know : its like algebra

2 2 = + you said yellow 23 odds 57 threads thats 70 +

1 2 = - red 41 odds 43 threads thats 84 +

+ + = + - + = -

- - = +

- = yellow : why? cause first move is on line 1 and 1 = odd = -

+ = red : why? first move can be line 2

ok so yellow ( 70 )

red ( 84 ) in 1000x1000 you said

70 = +

84= +

so + + is even and even red wins

was it 71 84

then its + - = - yellow wins

just like algebra thats for 8x8 10x10 , ... boards

6x7 idno

sry rong had to count yellow and red odds together buts its also red wins

and i did see rong i see now in numbers of threads

yellow 23 odds 57 t

red 41 odds 42 t

= 64 99

( + - ) = - yellow wins

"Say Yellow (P1) has 23 odd threats and 57 even threats, and red has 41 odd threats and 42 even threats. Who wins? "

koen: red wins this game. Play continues until the players have to start playing in threat columns---call a position "critical" when this occurs. Say the players are X and Y. Every move for player X in a critical position will either let player Y win instantly, or will let player Y kill one of player X's threats. After a threat is killed, the column (which is now safe to play in) fills up, and then the position is critical again. Whose turn it is after that depends on whether the threat that was killed was an even or an odd threat. Even threats change nothing: if player X kills one of his own even threats, then a few moves later it's critical time again and still player X's move. So play alternates with both players killing their own odd threats. Eventually Yellow runs out of odd threats to kill, so he might then kill his 57 even threats but after that he has to let Red win. It doesn't matter how many even threats either player has.

I should say that I only started playing this game a few days ago, so my analysis might be completely off! One of the first things I've learnt from playing a few games is that when you're killing your own threats you kill the odd ones first.

now i start to think my theory is not complete as you say.

1000x1000 is to much to count for me :)

8x8

when yellow has a odd red also need 1 . so your right that red normaly win @ 1000x1000

but u understand the algebra thing?

yellow needs even and odd a6 en f3 or some. 6 3 = + - = -

and red 2 even or odd a 2 en h 2 or a3 h 3 + + = + - - = +

"but u understand the algebra thing?"

Yeah, umm, doing algebra is my job ;-)

I mean :) algebra is usefull in 4r :)

whats is your job then? :)

[although understanding the algebra in this very simple kind of endgame is clearly nowhere near enough for me to play 4ir well, as you well know ;-) ]

ok :)

I'm a mathematician! The reason I think about 1000x1000 boards is because...umm...that's the sort of things mathematicians do. I like to learn games by learning some "abstract theory" first and then trying to apply it. It sort of worked well for dots and boxes and I'm hoping it will work well here too.

I think that 4r is very easy for you then after some practice :)

wccanard,

You already reached the most important conclusions. The only thing you need now is to learn some openings, because when there are only a few moves played, there are no threats yet, but both players must work towards them while preventing the other to reach their goal first.

Some examples of what are things to whatch out for during the early stages of the game:

1. The following pattern is in fact a garanteed threat:

X X

. X

X .

Look at an examples. P1 wins when he can reach this situation:

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . X X . .

. . . . O X . .

. . . O X O . .

a b c d e f g h

(P2 to move)

.. because P2 can not allow P1 to get g3, which would give P1 a forced win in h. Given this fact, g2 will remain empty, and P1 will either get h3 or h4, and gets a normal threat on g3.

There are however some "exceptions" to this pattern. If P2 can make a threat on g4 and there are more stones in g than in h, then the pattern doesn't function anymore, since P2 can then safely play g2 and one move later g3, giving up his own g4-threat as well, but at least breaking the pattern:

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . X . . .

. . . O O O . .

. . . O X X . .

. X . X O X . .

. O . O X X . .

a b c d e f g h

(P1 to move)

P1 plays g1 and wins.

The pattern can be use at differnt hights in the game (odd for P1, even for P2).

But at higher positions other "exceptions" can occur: P2 can "undercut" it. for instance:

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . X X . .

. . . . O X . .

. . . O X O . .

. . . O O X . .

. O . X O X . .

a b c d e f g h

Here P1 has a threat on g5, but... P2 has a counter to this. g1, g2, g3 will at a certain point be played. Now P1 will not want to give h5 to P2, since that would "undercut" his own threat. So in a sense h5 is a kind of odd threat to him. According to the general principle of the number of odd threats, this means P1 cannot maintain his own odd threat at g5, since he will be forced to play h4 in the end-game (assuming no other odd threats exist) and so the pattern is neutralized.

Another pattern is:

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . X . X . .

. . . O . X . .

. . . X . O . .

a b c d e f g h

where c2, e2 and g3 must be empty if P2 is to move. I leave it to the reader to further analyse this with examples and exceptions.

Enjoy!

sorry for the bad print, I should have used monospaced characters.

Just to read it more easily, thx Trincot:

wccanard,

You already reached the most important conclusions. The only thing you need now is to learn some openings, because when there are only a few moves played, there are no threats yet, but both players must work towards them while preventing the other to reach their goal first.

Some examples of what are things to whatch out for during the early stages of the game:

1. The following pattern is in fact a garanteed threat:

<br/>X X
<br/>. X
<br/>X .
<br/>

Look at an examples. P1 wins when he can reach this situation:

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . X X . .

. . . . O X . .

. . . O X O . .

a b c d e f g h

(P2 to move)

.. because P2 can not allow P1 to get g3, which would give P1 a forced win in h. Given this fact, g2 will remain empty, and P1 will either get h3 or h4, and gets a normal threat on g3.

There are however some "exceptions" to this pattern. If P2 can make a threat on g4 and there are more stones in g than in h, then the pattern doesn't function anymore, since P2 can then safely play g2 and one move later g3, giving up his own g4-threat as well, but at least breaking the pattern:

<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . X . . .
<br/>. . . O O O . .
<br/>. . . O X X . .
<br/>. X . X O X . .
<br/>. O . O X X . .
<br/><br/>a b c d e f g h
<br/>

(P1 to move)

P1 plays g1 and wins.

The pattern can be use at differnt hights in the game (odd for P1, even for P2).

But at higher positions other "exceptions" can occur: P2 can "undercut" it. for instance:

<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . X X . .
<br/>. . . . O X . .
<br/>. . . O X O . .
<br/>. . . O O X . .
<br/>. O . X O X . .
<br/><br/>a b c d e f g h
<br/>

Here P1 has a threat on g5, but... P2 has a counter to this. g1, g2, g3 will at a certain point be played. Now P1 will not want to give h5 to P2, since that would "undercut" his own threat. So in a sense h5 is a kind of odd threat to him. According to the general principle of the number of odd threats, this means P1 cannot maintain his own odd threat at g5, since he will be forced to play h4 in the end-game (assuming no other odd threats exist) and so the pattern is neutralized.

Another pattern is:

<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . . . . . .
<br/>. . . X . X . .
<br/>. . . O . X . .
<br/>. . . X . O . .
<br/><br/>a b c d e f g h
<br/>

where c2, e2 and g3 must be empty if P2 is to move. I leave it to the reader to further analyse this with examples and exceptions.

Enjoy!

Thanks Carroll.

It seems to me that the principle of major odd threats that I wrote down above (if yellow has more then he wins, if red has 2 more then he wins, otherwise red wins if he has an even threat and it's a draw otherwise) can be generalised slightly because, in some sense, positions like the one directly above (a "double weak odd minor threat" or whatever it's called) can actually be re-interpreted as a single odd major threat. The "J escapes" above are interesting but to a certain extent are tactical rather than strategic.

I need to think a bit more about this. Hopefully I'll have the hang of things a lot better, later on in the week.

I thought about it more and just got confused :-/

OK so from the above, we all understand how to evaluate a strategical endgame if there are just major threats left. Now the question is: what happens if we try to add some threats which are more complicated, but which still show up commonly on the 8x8 board. For example, one thing I've seen a few times is an "odd minor plus even major in the same column". In pictures I'm thinking about

<font face="courier"><br/><br/>. X O . O .
<br/>. O X . O .
<br/>. X O . X .
<br/>. O X . O .
<br/>. X O . X .
<br/>a b c d e f
<br/>    </font>

I'm going to use chess notation because, to be frank, I think the notation here is daft. Now O has a major threat at d4 and a minor threat at d5,f5 (the point being that d4 and d5 are in the same column). Now this position, it seems to me, is (from a strategic point of view) very close to an odd major threat [on a board with all column heights even---let me stress that all my analysis assumes this]. Because if the d column is filled up to d2 and then left alone, and if the f column is filled up to f3, and if X has to play first in the region, then X won't play d (he'll lose instantly) so he'll play f, and will lose in a few moves anyway because O takes f5 and then just starts playing in d and wins at d4 or d5. Hence all moves by O lose essentially immediately, just like a single odd major threat [note it's not the same as a single even major threat because if the position were replaced by a single even major threat then it would be the other guy's turn to move!]

The difference, it seems to me, is when O is on the defensive and has to play first. For a single odd major threat, if O plays in it, he loses the threat but gains a tempo [i.e. X now has to make the next "critical move"]. But for the position above, X can give up the f row and then keep the even threat. If X was player 2 then this is of some use to him, as we saw above!

I don't quite know how to 'quantify' such results.

[a col should be filled with XOXOX]

OK here's a general result.

Theorem: An isolated major even threat is no use to yellow!

More precisely, if G is a strategical game of 4ir (i.e. no tactical threats left) and H is an isolated major even threat for yellow then the value (i.e. "win for red", "win for yellow" or "draw") of G and G+H are the same.

"Proof". I haven't thought much about foundational issues but I think this sort of argument must work. It's a man in the middle argument. I will play as red in G+H and as yellow in G, against two perfect players. If I can break even then I've proved the theorem. I think. If an expert plays in G in one game, I respond in G in the other. If yellow plays in H I play on top and H has become an even number of dead moves, which get played out at some point (I just "play on top" whenever my opponent plays there). The only case left to check is what happens if G disappears completely. Then I have drawn G, and H is all that is left of G+H, but it must be yellow's move in H, so I'm going to draw G+H too. So done.

Does this mean that yellow should never bother making an even threat? I don't think so: for example an even threat with an odd threat directly above it is (essentially always) an immediate win for the player with the threats.

Once the set of threats is fixed, it's relatively easy to determine the outcome.

Around the time connect-4 was first solved, I had a program that would compute

the end-game-value incrementally. The relevant information about each column

can be concisely represented in a 12-bit number, such that the sum of all these

numbers (one for each column) modulo 2^12 can be use to lookup the game result

in a table of size 4096.

Even with this ability, my program was far from perfect, as the game is often

decided by threats that have yet to materialize...