The following are extremely simple ways of tackling this problem.
A very simple way
It can simply be
strength of AI
=(# of games won)
/(total # of games)
.
In case data for each move is available
Something like
score per game
=# of correct decisions
/total number of decisions
.
Then
strength of AI
=sum(score per game)
/total # of games
.
If each move/decision has a score associated with it
then you do
score per move
=scored points by taking a decision
/maximum possible score
.
then
score per game
=sum(score per move)
/total # of moves
and finally,
strength of AI
=sum(score per game)
/total # of games
.
How to choose optimal number of games to play?
It depends on your requirements. If you want to report your AI's strength in percentage of the games it played correct to 1 decimal place (for example, this AI won 95.1%) then 10000 is an optimal number of games your AI needs to play. Suppose your AI won 9508 games out of 10000 then you will have 95.08% strength of AI. To be able to correctly round it to 1 decimal place you need to have an additional decimal place so that you can quote the strength of you AI with reasonable confidence, in this case 95.1%.