#!/usr/local/bin/maple
#-*- maplev -*-

# Experimental Mathematics Project
# Nathaniel Shar

# * First Draft *

Help := proc():
    printf("%s",
"Public-facing functions:\n\nPlayer(Moves, Make):\nreturns a player who can play letters drawn from the set 'Moves' and who is\ntrying to make the set of patterns 'Make'. (If Make is the empty set, the\nplayer is trying to prevent the opponent from making any patterns.)\n\nAnalyzeGame(A, B, Player1, Player2, n, quiet:=1):\nreturns the result of a perfectly-played game between Player1 and Player2\nusing letters from the alphabet A and blank B on a board of length n. Settting\nquiet to 0 will produce many meaningless output messages to reassure you that\nthe program is working very hard.\n\n"):
end:

# Data type:

# Player:
# A player has the following attributes:

# moves: a set of letters the player can play

# make: a set of patterns the player is attempting to make. The empty
# set means the player is not trying to make any patterns.

module Player() option object:
export moves := {}:
export make := {}:
export ModuleApply::static :=
    proc( ):
        Object(Player, _passed):
    end:
export ModuleCopy::static :=
    proc(new::Player, proto::Player, moves::set, make::set, $):
        new:-moves := moves:
        new:-make := make:
    end:
end:


# Functions:

# IsMakerWin(w, FP, B): Recognizes whether the position w is an end state in which a Maker trying to make any of the patterns
# FP wins.

# IsBreakerWin(w, FP, B): Recognizes whether the position w is an end
# state in which a Breaker trying to prevent all of the patterns in FP
# wins. I don't actually use this function. Oh well. I might use it later.

# AnalyzeGame(A, B, Player1, Player2, n):
# Creates a board of length n on which Player1 and Player2 play a
# maker-breaker game using the alphabet A and the blank B.
# (For information on how to describe the Players, see above.)
# Player 1 goes first.

# The return value, for now, is a string that describes the winner.


IsMakerWin1 := proc(w, fp1, B) local i, v: option remember:
    if fp1 = [] then:
        return true:
    elif w = [] then:
        return false:
    elif w[1] = fp1[1] or fp1[1] = B then:
        if nops(fp1) <= nops(w) then:
            v := true:
            for i from 2 to nops(fp1) do:
                if fp1[i] <> w[i] and fp1[i] <> B then:
                    v := false:
                fi:
            od:
            if v = true then:
                return v:
            fi:
        fi:
    fi:
    return IsMakerWin1(w[2..nops(w)], fp1, B):
end:


IsMakerWin := proc(w, FP, B) local p:
    for p in FP do:
        if IsMakerWin1(w, p, B) then:
            return true:
        fi:
    od:
    return false:
end:

IsBreakerWin := proc(w, FP, B):
    if member(B, w) then:
        return false: # Not attempting to compute whether it is possible to complete the patterns -- that seems too hard.
    else:
        return not IsMakerWin(w, FP, B): # If maker didn't win, then breaker did, and vice versa.
    fi:
end:

AnalyzeGame := proc(A, B, Player1, Player2, n, quiet:=1) local value:
    value := AnalyzePosSmart([B$n], A, B, Player1, Player2, 1, quiet):
    if value = 1 then:
        return "The first player made a pattern!":
    fi:
    if value = -1 then:
        return "The second player made a pattern!":
    fi:
    if value = 0 then:
        if Player1:-make = {} then:
            return "The first player prevented the second player from making a pattern!":
        elif Player2:-make = {} then:
            return "The second player prevented the first player from making a pattern!":
        else:
            return "The game was a tie!":
        fi:
    fi:
end:

# Smart = uses alpha-beta pruning. It's not as smart as it could be yet.
AnalyzePosSmart := proc(pos, A, B, Player1, Player2, turn, quiet, alpha := -infinity, beta := infinity) local i, z, a, b, FP, p1made, p2made:
#    print(pos, alpha, beta):
    p1made := 0:
    p2made := 0:
    if IsMakerWin(pos, Player1:-make, B) then:
        p1made := 1:
    fi:
    if IsMakerWin(pos, Player2:-make, B) then:
        p2made := 1:
    fi:
    if p1made = 1 and p2made = 0 then:
#        print(pos, "player 1");
        return 1:
    elif p1made = 0 and p2made = 1 then:
#        print(pos, "player 2");
        return -1:
    elif p1made = 1 and p2made = 1 then:
#        print(pos, "draw");
        return 0:
    elif not member(B, pos) then:
#        print(pos, "game finished");
        return 0:
    else:
        a := alpha:
        b := beta:
        if turn = 1 then:
            for i from 1 to nops(pos) do:
                if pos[i] = B then:
                    for z in Player1:-moves do:
                        a := max(a, AnalyzePosSmart([op(pos[1..i-1]), z, op(pos[i+1..nops(pos)])], A, B, Player1, Player2, 1-turn, quiet, a,b)):
#                        print(a):
                        if b <= a then:
#                            print("beta-cutoff", a):
                            return a:
                        fi:
                    od:
                fi:
            od:
            if quiet = 0 then:
                print(pos, turn, a):
            fi:
            return a:
        else:
            for i from 1 to nops(pos) do:
                if pos[i] = B then:
                    for z in Player2:-moves do:
                        b := min(b, AnalyzePosSmart([op(pos[1..i-1]), z, op(pos[i+1..nops(pos)])], A, B, Player1, Player2, 1-turn, quiet, a, b)):
                        if b <= a then:
#                            print(pos, "alpha-cutoff", b):
                            return b:
                        fi:
                    od:
                fi:
            od:
            if quiet = 0 then:
                print(pos, turn, b):
            fi:
            return b:
        fi:
    fi:
end: