Thanks for the advice guys. I will make a separate board object for the AI to work on. I'll probably do this by updating this object while updating the real board. Making a copy constructor is rather messy, because I have lists of pointers (for convenience sake) as data members. I will also implement a "undo" function (shouldn't be too hard ).
I haven't thought it through, but I inclining toward minimax right now (that's the one they use for chess right? [edit: yes, yes it is]). From what I understand of Monte Carlo methods is that they can fickly in terms of parameters of the randomness. I'll keep you guys posted