Melhor resposta
Sua pergunta despertou meu interesse porque é uma que me lembro de tentar resolver quando criança, desenhar linhas na areia de uma praia. Ah, memórias de infância. Mas de qualquer maneira …
Presumo que você esteja fazendo a mesma pergunta que eu fiz naquela época : 4×4 Tic-Tac-Toe (ou “Nada e Cruzes”, como o chamamos) requer que um jogador acerte quatro em uma linha, 5×5 requer 5 em uma linha, etc. Como ficou claro para mim na praia, embora eu Não poderia “provar” isso, ganhar torna-se cada vez mais difícil, por isso não é surpresa que os jogos também estejam empatados. Portanto, não faz muito sentido falar sobre uma estratégia preferida, pois não existe estratégia de vitória. Obviamente, tentar controlar o centro é geralmente uma abordagem dominante, pois aumenta as contribuições para possíveis linhas de vitória, mas mesmo contra uma defesa “abaixo do ideal”, a margem de empate é bastante alta. Com isso, quero dizer que o segundo jogador pode fazer algumas jogadas que parecem bobas e ainda garantir o empate com o jogo forçado subsequente.
Mas vamos tornar as coisas mais interessantes. Que tal precisar de três em linha em um tabuleiro 4×4? Com mais algumas linhas e um pouco mais de areia, podemos descobrir rapidamente que o primeiro jogador tem uma vitória forçada. Faça sua primeira cruz em um dos quatro quadrados centrais e seu segundo movimento em um centro adjacente quadrado. (Se você puder escolher entre dois, escolha aquele que conecta suas duas cruzes a uma linha vazia.) E o próximo passo: Você venceu!
Ótimas notícias, mas por outro lado, se estendemos o requisito de vitória para a necessidade de obter quatro em uma linha, o jogo é facilmente desenhado. Experimente você mesmo (encontre uma praia e um pedaço de pau).
Então, a próxima pergunta óbvia é: Qual é o resultado de um jogo em que é necessário obter k em uma linha em um m x n tabuleiro, onde assumimos que k m n . Agora as coisas ficam realmente interessantes! Por exemplo, acontece que quatro em uma linha é um empate mesmo em 5×5, mas uma vitória em 5×6, enquanto cinco em uma linha é uma vitória em 15×15 (!!) ou maior.
Para obter mais informações sobre o jogo da velha generalizado, consulte este excelente artigo: Jogo da velha generalizado