Here is a proof game in
19.0 moves
which goes like this:
1. b4 f5 2. Bb2 Kf7 3. Bxg7 Kg6 4. Bxh8 Kh5 5. Bd4 Bg7 6. Bxa7 Bc3 7. Bxb8 Rxa2 8. dxc3 Ra6 9. Ra5 Re6 10. Rc5 b5 11. h4 Bb7 12. Rh3 Bd5 13. Qxd5 Kg4 14. Rd3 Re4 15. Qxe4+ fxe4 16. Kd2 exd3 17. Kc1 dxc2 18. Kb2 cxb1=R+ 19. Ka3 Rxf1
To see that this is optimal, we will have to take a closer look at the position (I won't use spoiler blocks from here on out):
Obviously, the black rook on f1 is the promoted f7 pawn. In order to promote, it needed to capture at least four times. Since all dark squared white pawns (in fact, all dark squared white pieces) are still on the board, all these captures needed to consume light squared pieces. Since the Bf1 was not available, there remain only five possible pieces - Rh1, Qd1, Nb1, Pa2 and Pc2. In particular, this implies that Pf7 could not capture six times and therefore had to start its journey with a double step. As a consequence, it could not possibly have captured Pa2 - in order to do so, this pawn would have had to promote itself, which is impossible, since it could capture at most three times (rook, bishop and a pawn e.p. once).
Hence, Pf7 had to capture Nb1 to promote, which fixes his journey as f7-f5xe4xRd3xc2xNb1. (The Rh1 cannot reach any other square to be captured.)
From this fragment of the history, we can already conclude that White spent at least four moves with their light squared pieces - two moves with the rook and two moves bringing the queen to e4 (the alternative, bringing the Pc2 to e4, would need at least five moves altogether since the queen cannot be captured at home).
Before tying this in with Black's moves on light squares, we will now take a look at the plays on dark squares. Here, Black is missing quite a bit of material. Clearly, the Bf8 was captured on c3 (since no other black piece could reach that square), but the two missing pawns, the Rh8 and Nb8 had to be captured by white pieces. It is straightforward enough to see that the most efficient way to go about this is by using the Bc1 to capture at least Rh8 and then Pa7 and Nb8. The missing g7 pawn could have either been captured by the Bc1 on the way to the corner, or maybe by the Ra1 after taking a double step. Either way, the capture of this pawn consumes at least one extra move for either the rook or the bishop, which leads to a total of at least 15 white moves on dark squares: Three pawn moves, four king moves, two (three) rook moves and five (six) bishop moves.
This already brings us up to the 19 allowed moves by White. In order to achieve this minimum, we cannot spend any extra moves at all - in particular this means that Black's light squared rook and bishop needed to be captured using only the very few moves on light squares that are available to White.
But these two pieces are already quite constrained for time - if we tally up all known black moves so far, we already arrive at a total of 13 moves (four by the king, two by Bf8 to reach c3, one by Pb7, five by Pf7 to promote and finally one for Rb1xBf1).
This leaves only six more moves for the two unaccounted pieces to reach convenient squares for capture AND capture White's missing Pa2 at home.
In fact, since the first move by the white queen must be vertical (Pc2 is still blocking the path at that time), the only squares where these captures can possibly occur, are d3, d5, e4 (by the queen) and h3, d3 (by the rook). Note that among these, only e4 can be reached by Ra8, which leaves no degrees of freedom on how these two pieces move:
To see why, I will first claim that the White must have already played b4 at this point. Otherwise, we run into trouble at the start of the game - before opening Bc1 with either b4 or dxc3, White can only move h4 and Rh3 (not Rd3 because it blocks the path of the queen later). But this is not enough time for the black Bf8 to serve itself up on c3. Hence, one of the first white moves must be b4, which constrains the path of Ra8 later.
Indeed, this shows that Pa2 cannot be captured by the bishop - to reach it and get out would take four moves, leaving only two for Ra8 to reach e4 - impossible.
As such, the pawn must be captured by the rook, which then still needs three more moves to reach e4 and leaves exactly two moves for the bishop, which can barely reach d5 in time.
This finishes the proof - each player had to take at least 19 moves, which are all uniquely determined after all. (I won't go through this in detail - but many of the loose earlier estimates can be tightened up once we have the whole picture - for instance, we can now conclude that Pg7 must have been captured by Bc1 and not Ra1 so as to achieve the black minimum). Nonetheless, there is still ambiguity in the move order at several places. Maybe I will look at this later ...
To answer the final question: It is now White to move and win with 20. Rg5+.
Black can only move 20. ... Kf4 (Kh4 gets directly mated by Nf3#). Following up with 21. g3+ Ke4 (forced), we can play 22. Nf3 and threaten the two mates Re5 and Nd2, which cannot both be blocked. Black can only delay by giving two checks with the rook, after which mate directly follows.
This was quite a tricky puzzle and I had a lot of fun solving it! :)
monochromatic-chesstag now :) $\endgroup$