首頁猿問確定Tic Tac Toe游戲的算法

確定Tic Tac Toe游戲的算法

Java 算法與數(shù)據(jù)結(jié)構(gòu)

忽然笑 2019-08-15 16:18:30

確定Tic Tac Toe游戲的算法我在Java中編寫了一個(gè)井字游戲，我目前確定游戲結(jié)束的方法解釋了游戲結(jié)束的以下可能情況：董事會(huì)已經(jīng)滿員，尚未宣布獲勝者：比賽是平局。克羅斯贏了。Circle贏了。不幸的是，為了做到這一點(diǎn)，它從表中讀取了一組預(yù)定義的這些場景?？紤]到電路板上只有9個(gè)空格，這并不一定是壞的，因此表格有點(diǎn)小，但有沒有更好的算法來確定游戲是否結(jié)束？確定某人是否贏了是問題的關(guān)鍵，因?yàn)闄z查9個(gè)空格是否已滿是微不足道的。表方法可能是解決方案，但如果沒有，那是什么？另外，如果電路板尺寸不大n=9怎么辦？如果它是一個(gè)更大的板，比如n=16，n=25等，造成連續(xù)放置物品的數(shù)量取勝是x=4，x=5等？一種用于所有人的通用算法n = { 9, 16, 25, 36 ... }？

查看完整描述

3 回答

牧羊人nacy

TA貢獻(xiàn)1862條經(jīng)驗(yàn) 獲得超7個(gè)贊

您知道獲勝的移動(dòng)只能在X或O進(jìn)行最近移動(dòng)之后發(fā)生，因此您只能搜索包含在該移動(dòng)中的可選診斷的行/列，以在嘗試確定獲勝板時(shí)限制搜索空間。此外，由于在最后一次移動(dòng)中，如果它不是一個(gè)獲勝的移動(dòng)，那么在平局游戲中存在固定數(shù)量的移動(dòng)它默認(rèn)為抽獎(jiǎng)游戲。

編輯：此代碼用于n個(gè)n板，連續(xù)n個(gè)贏（3x3板請(qǐng)求連續(xù)3個(gè)，等等）

編輯：添加代碼來檢查反診斷，我無法找出一個(gè)非循環(huán)的方式來確定該點(diǎn)是否在反診斷，這就是為什么這一步缺失

public class TripleT {

    enum State{Blank, X, O};

    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;

    void Move(int x, int y, State s){
        if(board[x][y] == State.Blank){
            board[x][y] = s;
        }
        moveCount++;

        //check end conditions

        //check col
        for(int i = 0; i < n; i++){
            if(board[x][i] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check row
        for(int i = 0; i < n; i++){
            if(board[i][y] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check diag
        if(x == y){
            //we're on a diagonal
            for(int i = 0; i < n; i++){
                if(board[i][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check anti diag (thanks rampion)
        if(x + y == n - 1){
            for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check draw
        if(moveCount == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }}

反對(duì) 回復(fù) 2019-08-15