-The player can choose as many pieces to move as he likes. For example none, all of them, or some number inbetween. (Whereas in chess you can only move one)
That quote specifically is the part that really causes the size of your legal action set to blow up. You have a combinatorial action space here. If each of your pieces has 8 legal moves, then that is:
- 8 legal moves for the first piece (or 9 if that count didn't already include the "do nothing" option)
- for each of those, there are again 8 or 9 different choices for the second piece (leading to e.g. $8 \times 8 = 64$ possible combinations for just the first two pieces)
- for each of those, again 8 choices for the third piece (leading to $64 \times 8 = 512$ possible combinations for just the first three pieces).
This blows up way too quickly, and there's really no hope of ever getting a decent player for this using any MiniMax-based algorithm (including things like alpha-beta pruning, principal variation search etc.).
In the kinds of games that you describe, you'll want to use algorithms that can exploit the "structure" of your action space. A raw enumeration of all possible combinations blows up quickly, but many algorithms can do reasonably well by re-phrasing the problem in such a way that you have more "depth" rather than "breadth". For example, instead of viewing a full combination of choices for all pieces as a single "action", you can treat the choices per piece as a separate "action".
Rather than making a single choice out of $8 \times 8 \times 8 \times \dots$ possibilities every turn, you want to have a search tree where your player makes one choice out of $8$ (for the first piece), followed immediately by another choice out of $8$ (for the second piece), etc. The opposing player only gets to make a choice after the current player has made choices for all pieces. With such a strategy, the breadth of your search tree will no longer be a problem, but the depth will become a problem. To address this, you'll additionally want to make sure that your methods can generalize across different depth levels.
A good place to look would be combinatorial versions of Monte-Carlo Tree Search, such as those described in:
These algorithms are quite a bit more complicated than MiniMax though, MiniMax is a very basic algorithm in comparison.