http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf
hmm... if i'm reading this article right
you play each game and construct a tree as you play
if that board state is already in the tree just go to it also increment times visited in the tree
if it's not, branch and add
and at the end of the match go back up the tree and add how many times that state lead to a win/loss/tie
win+loss+tie = times visited
all leaf nodes should be categorized as wins losses or ties