Help with AI possibilities

I'm trying to work on multiple difficulties for a game i'm making.
The game is 2 player either Human vc AI or Human vs Human. The gameboard is Columns by Rows with each location containing a gamepiece. Each gamepiece has 4 properties, say A-D, and each property has 4 characteristics, say 1-4. The pieces are created randomly and each player gets their own board with relatively different random pieces. Each player is randomly assigned a piece from their board as the goal, but does not know what the piece is. Each turn a player can pick one characteristic of one property of a gamepiece. If what the player picked matches the goal piece, then all pieces on the board that do not match that single characteristic are removed. If the chosen characteristic does not match the goal piece, then all pieces on the board that match the chosen characteristic are removed. My game is based on Guess Who?® Game by Milton Bradley, so if you know that game then the concept is similar. The number of characteristics only could easily (code is setup to handle) be increased or decreased upto 2, but it will be 4 until i finish the game and do playtesting. The number of columns and rows are adjustable by player with min of 2x2 (that'd be pretty boring) and a max of cols = screenwidth/3 +1 and rows = screenlength/2 +1. A decent default will be determined with the playtesting. Now that i've gotten the game rules/concepts out of the way, what i'm asking for help on is strategies on the finding the goal piece. It doesn't need to be the fastest possible as I'm looking for a variety of difficulty levels.
A few i've thought of:
The AI just picks randomly without thought. (a beginning difficulty)
The AI tallies up the characteristics each turn and picks the most common, having the best chance to remove more pieces if the choice is incorrect.
The AI tallies up the characteristics each turn and picks the least common, trying to remove the maximum number of pieces if the choice is correct.
The AI tallies... and picks an approximate median. This would remove roughly 3/4 the pieces if correct and roughly 1/4 if incorrect.

Also, what would be a good way to determine which AI strategy is "better" than the other, so I can assign them appropriate levels.

>> Also, what would be a good way to determine which AI strategy is "better" than the
>> other, so I can assign them appropriate levels.

Make both of you'r AIs play against each other. And see who wins the most.

That sounds like a good way of seeing whos the best! I wish you the best of luck in your endeavors. It sounds like a cool game and the AI doesnt sound too difficult to program. You also sound like youve got a plan so go for it!