Ah, um jogo da velha precisa de um desses padrões? Então tá.
A principal diferença é que o padrão da estratégia é isolado, indica uma regra a ser aplicada de acordo com uma implementação externa em algum ponto específico, e pode parametrizar qualquer comportamento desejado no objeto. E o padrão da especificação é algo mais complexo e estabelece um conjunto de regras, geralmente encadeadas, que serão aplicadas em alguma parte, sendo que cada regra individual pode ser trocada, adicionada ou removida, além de mudar a ordem, e estas regras devem ser principalmente validações (em um sentido amplo, e não só a validação tradicional, pode ser uma seleção por exemplo), portanto bem mais limitada. Portando nem deveria haver confusão, eles servem a propósitos bem diferentes. Geralmente a dúvida sobre o uso do Strategy é se não seria melhor o Bridge, Adapter, State, Template Method, Decorator, e por vezes Visitor ou Facade.
Já tenho minhas dúvidas se deveria usar um deles, mas o Specification parece menos interessante aí, ainda que eu possa estar errado por não conhecer os detalhes. Quanto mais vai aplicando essas coisas tende a adotar o antipattern chamado Second System. Por outro lado se quiser insistir nele, talvez queira usar como mecanismo de "AI", e pode fazer sentido já que quer complicar a solução, usar este padrão para encadear as decisões. Lembre que ele é só um if
bem mais complicado, é OOP sendo usada onde o simples imperativo resolvia o problema. E se varia o que fazer em certas sequências então o Strategy pode ser útil, mas acho que nem é o caso, pense até em outros que eu citei acima. Eu não posso pensar por não ter detalhes.
Note que C# tem mecanismos que muitas vezes faz com que um certo padrão não seja necessário. Por isso sempre digo: as pessoas querem usar design patterns sem nem mesmo saber o que isto significa, é só porque está na moda.
Design patterns are bug reports against your programming language
-- Peter Norvig
Coloquei no GitHub para referência futura.