Given that this is A-Level, from my own personal experience, I have found that the actual complexity of the task you are trying to achieve is less important than going through the whole development process and writing the report as a whole. So I would recommend trying to keep the actual problem relatively simple, having feature-creep or having a really complex code base can become a huge time sink if you are not careful. (As you said yourself, the actual game only makes up for 25 of 75 marks). I elected to ignore my teacher and wrote a programming language compiler for my A-level coursework which was rather time consuming, though having said that, I did enjoy doing it, and I did do very well
However, the nice thing about the compiler was that it was very modular in that I could have submitted something more bare-bones.
The best sort of game to have would be something that you know a simple AI can exist for. This is something that you should be able to implement quite quickly, but you can always build on it if you feel like you have more time.
Regarding the most practical AI methods, this entirely depends on the sort of game you are making. Most game AI is actually very simple, however this is often considered too simple for pure "computer science" applications.
Standard video game AI (Like a boss or a generic enemy) - Most commonly use some form of
state machine which is built as a collection of simple conditions and timers that transition between different states such as attacking, defending, dodging, chasing, etc;
Game Tree evaluation - This is a form of perfect AI that can be developed for games with deterministic outcomes (e.g. chess, noughts and crosses). Essentially, you pre-compute every possible move and the match outcomes and you use a heuristic function to get your AI to choose the move that leads it to the best possible outcome. (For example if one move leads you to win 95% of your games no matter what move your opponent makes, choose that one). In practise, this is much more difficult as games like Chess/Go have so many possible moves that you cannot pre-compute it all, so instead you have to be smarter. Though this is a fantastic place to start if you are making a turn based game with a limited number of moves and fixed outcomes for those moves.
Minimax, as you mentioned, is often what is used to actually make these decisions. The Evaluation will aim to maximise the heuristic score of itself and minimise that of the opponent.
I would strongly recommend this path as it is so extensible. The quality of the AI is often dependent on the "look-ahead" of your AI, this is essentially how many moves forward you can predict. You can increase this by doing things like tree pruning where you discard parts of the tree that are unlikely to happen. You know you can discard all of the moves that give yourself a bad score, and you can also discard a number of the moves that give your opponent a bad score too, as whilst there is no guarantee that they will pick a "good move", if they pick a bad move, it doesn't really matter for you anyway as you are still at an advantage.
As far as working out what moves are best, you would need some way of evaluating the current game state. In chess, you could do something simple like giving each piece on the board a value and counting them. More advanced heuristics would look into things like positioning and attack lines, but that is another natural extension of this form of AI.
Greedy AI - This is a form of AI that does not consider the future but consistently chooses the best possible move to make in any given scenario. This AI is often a nice place to start and can create difficult-to-beat behaviours but can be easily countered once you start thinking about the long game. You would most likely evaluate the situation and give a weighting to each possible move. This would be similar to a single-move look-ahead game tree.
These are just a few things. I would definitely take the Game Tree route if possible, though this requires your game to be designed in a way that it is solve-able with a game-tree. You can even extend it to include a state machine where you only use the game tree if the AI is in a certain state.
Regarding GameMaker, it is quite difficult to actually to pull off complex AI because it is difficult to cleanly represent game-states with gamemaker, and without YYC, doing the computation in real-time is going to be somewhat challenging. (Just because GameMaker isn't the fastest, nor the most memory efficient without YYC). It is possible, but this sort of thing is easier in other languages. One thing you can do (which would get you brownie points) is to use networking to connect an "AI" player to your game. This would allow you to implement the AI in a different language, but allow your game to be written in GM (which is alot easier for the game). You can use the MVC (Model-view-controller) design pattern to organise your game so that you implement the Model and View in GameMaker, but you can implement a controller in GM for the local player, and a controller in a different language for the AI.
(I know i'm blurting things out without explaining them, but they are quick to google).
If you have any questions or need any help, feel free to ask
