this is the general algorithm used for games of perfect information (and even some games of imperfect information) it won't work on its own, just like it doesn't work on its own in chess since the possible moves per position causes the game tree to fill up too fast.
here is part of the solution to the branching problem. there are many ways to do move ordering. the "greed AI" you cited is probably a good way to do a simplistic "move ordering" then a simplistic pruning could be searching only the top 3 or 4 moves in that list. a-b pruning reduces the size of the game tree for a given ply (depth) and branching factor by a factor of its square root.
bitboards are especially awesome for reversi since you can represent it as 32 or 64-bits depending on what OS you're targetting. (hint: you get about 60% gains on 64-bit cpus) and due to the fact that reversi (your reversi variant) only has 4 or 5 states a square can be in
so far i've only talked about search, but the next level is evaluation.
search lets you generate a game tree and mini-max lets you recurse up the tree to determine the best move (based on scores) the scores themselves are gotten via evaluation.
an evaluation function (similar to fitness function in genetic simulations) evaluates a position without searching it and tries to give a score. (for minimax purposes score one player as positive and another as negative)
btw, since you don't want draws, you need to count a draw as a loss for scoring purposes. or at least use a large contempt factor.
for fine tuning your evaluation function you need to isolate what parameters you want to weigh: mobility, # of legal moves, squares you control, etc. then (and this is just me. as far as i know no one else but me or very few have done it this way) you can use a genetic algorithm from a pool of having your engine play against itself thousands of times to tweak the magnitude and weights and thresholds of your evaluation function's treatment of your selected parameters.
i have gone as far as implementing neural networks to control the pruning and singular extensions aspect, but i wouldn't recommend it. i got miniscule gains and it actually resulted in weird "local optima" play where when it was presented with situations outside the realm of its training sample, it played terribly.
for the opening, giving it a small (or large) human-generated or self-generated library to help it make its first moves is a great way to give it an advantage in time and general strategic position throughout the early middle game. since your reversi variant is not studied, a book would probably give you a large advantage over other programs not using any opening book.
read about depth-tomate and depth-to-conversion tablebases. in chess it's simple, they're generated on a "n pieces left" basis. for your variant you'd want to generate them for "n empty spaces left" situations. they would have to serve as search enhancers and in the case of your variant could be applied dynamically throughout the game, not just at the end.
there is a lot more to say and i haven't even shown you the surface of what game engines can do and how they can be made to do it, but this should get you started.