Q1

Algorithm：

CheckPlayStage(StartPosition, Player)：

       if player already won in this movement:

            return Good;

       if player already lost in this movement:

            return Bad;

       for all legal moves X $→$ Y:

             if CheckPlayStage(Y , $\\neg$Player) =Bad;

                   return Good, Y

         return Bad;

Proof of Correctness:

Assume for Moving stage , and player A, A[ 1 … n ], A[i] is the i th stage of the player A’s movement during the match

Base Case: When A[1] we reach the very begining of the match which have no preview movement to track back.

Recursive Case:

      Case1: 

                 when A[n-1], And CheckPlayStage(A[n],A) return Good;

    we can get from the Algorithm that the A[n-1] is a Good stage which offer player A oppertunity to win in stage A[n], which allow us to trace back to the starting stage that A[1] is a point that can lead to win.