/sci/ - Science & Math

[Anonymous No.5664274]

Assuming neither player makes a mistake, is this really a draw? Can you prove it?

[Anonymous No.5664304]

Depends on what you mean by mistake. Chess was technically already proven to be unwinnable assuming the starter doesn't make a mistake although it requires a number of moves and counter moves to be memorized that is beyond human players.

[Anonymous No.5664347]

>>5664304
I don't think chess is solved.
They say it is sometimes on April 1.

Luckily this problem is a lot simpler than chess itself.

[Anonymous No.5664365]

>>5664304
I think it's only conjectured that Chess with perfect players always draws.

[Anonymous No.5664390]

that particular position is a draw and can be proven with endgame tablebases

http://en.wikipedia.org/wiki/Endgame_tablebase

Although it is not proven that chess in general is a drawn, its is obviously the case and anyone that knows anything about chess will agree

[Anonymous No.5664405]

>>5664390
Well that one is small enough so that it can be proven using simple game theory algorithms.

The game theory algorithms to prove the existence of a winning strategy in such a situation are simple:
- You draw the graph G of every game configuration that can be reached from the current position. Game configurations include the position of the 2 kings and rooks, as well as which turn it is. You call "W-vertices" the vertices that are on white's turn, "B-vertices" the one that are on black's turn. You name "W-edges" the edges that correspond to a move for white (from a W-vertex to a B-vertex, and "B-edges" the ones that correspond to a move for black.
- You call w(0) the set of all winning positions for white (black is checkmate),
1) Let n=0,
2) Starting from w(n), define w(n+1):=w(n),
3) From every node in w(n), move one step BACKWARD. For any vertex that can be reached by moving one step backward:
--- if that node is a W-vertex, put it into w(n+1),
--- if that node is a B-vertex, put it into w(n+1) if EVERY move from that vertex goes to w(n).
- If w(n+1)=w(n) (no new vertex was added), stop.

After that, the last w(last_n) is the list of all states of the game from which white has a winning strategy (against which black has no counter-strategy).

Do the same for black (call the sets b(m) instead of w(n)). If the starting position is not in w(last_n) and not in b(last_m), then the game should end with a draw if no player does a mistake.

[tn No.5664411]

>>5664405
(cont)

The computational complexity of that algorithm isn't that much:
- last_n is at most the number of vertices in the graph (because we add at last one to w(n) each time we increment n, otherwise we stop).
- for each n, we have a number of operations to do which is at most linear in the number of vertices in the graph (assuming the number of possible moves from a given position is small compared to the number of vertices in the graph).

Therefore if there are N states in the graph, the complexity is in O(N^2). However in fact, by tweaking the algorithm a bit, you can make sure you don't process the same node too many times uselessly, and have run times that are roughly O(N).

For our example, N is at most 2*64*63*62*61 (some possibilities can most likely be excluded). That's roughly 30 million. Easy.

[Anonymous No.5664425]

>>5664405
>>5664411
thanks for explaining retrograde analysis to me i guess

[Anonymous No.5664433]

Whos turn to move?

[tn No.5664435]

>>5664425
Well, not specifically to you. Hopefully even if you knew all about it, OP learned something anyway :)

[Anonymous No.5665631]

>>5664435
Well, I thought it was very interesting. When did sci get so grouchy?