This is might be vague due to my sparse knowledge; but might go be an “np hard” problem? Or, if you phrase it as “find a complete game where the final score is x, y prisoner difference, and some z starting moves”, it’s easy to verify but how difficult is it to find? how would alphago tackle this problem?
Alphago doesn’t try to solve the problem you have stated. Alphago does not have a goal to come up with a specific final end condition given set initial moves. Alphago finds the sequence of moves, in response to the opponent’s moves, that have the highest chance of meeting the winning condition. So asking how alphago would solve the problem you stated appears to be like asking how to get street directions from an abacus.
Is the problem you phrased hard? It’s not obviously hard: I’m imagining that I would lay down y prisoner stones, surround them by black stone, then set out a row of black and white stones down the middle, so the score is zero +/- the starting move stones, then nudge them until the score is x.
You didn’t say that the solution has to be a likely actual game. I think it would be awesome if you could even define what a likely actual game is! 
3 Likes
Go is EXPTime-complete, if I recall correctly. But since I cannot give you any paper or source, you see that my knowledge here is rather incomplete. I am sure that google will help you on that point. Also, keep in mind, that the answer might depend on the rules/scoring system.
Edit: I found this via “duckduckgoing”: http://www.ics.uci.edu/~eppstein/cgt/hard.html#go Who knows whether this is up to date.
1 Like
There’s some more discussion of this on SL: https://senseis.xmp.net/?RobsonsProofThatGOIsEXPTimeHard
As I understand it that proof just provides a lower bound (it might be possible to find even worse cases than the specific capturing problem it used). In general, when you ask this question about the game “go”, you ask something like: with absolutely perfect/optimal play, what is the best algorithm that can be found? This is a separate question from questions like, given an algorithm that plays go, what is its complexity? There might be approximate solvers that are much faster and still strong (in fact I really doubt that any strong computer go system is trying to truly solve an EXP-time hard problem, including alphago/alphazero).