Need help with MiniMax-Algorithm

[RockiLocky]

Right now I am trying to implement the MiniMax-algorithm to make an AI which is impossible to win against, meaning the game goes equal or the AI wins. Now I checked out wikipedia and other sides and looked into it abit.

 

What I found out(Hope you can correct me if I am wrong):

 

The MiniMax-algorithm is mainly used in smaller games where you will basically look into the future, meaning you will look at all the possibilitys that will occur. And for every of these possibilitys you will give away points. For example if the AI wins it gets +100 and if the Player will win the AI will get -100. After you went all these possibilitys you will search for the best move which will not result in you loosing at least. Meaning in the worst case you will go equal.

Now there are is alot of stuff covering that out there for example what I looked at: 

http://neverstopbuilding.com/minimax

https://en.wikipedia.org/wiki/Minimax

 

Now I looked into all of that and some other sutff.I tried to figure out a way to implement this into C# but then I got kinda mix between the solutions how to implement. For example at around 18:20 you see the whole code for the MiniMax-Algorithm in that guys tutorial(btw I didn't find anything better). His code was smaller and stuff but here is my code now:

 

 

Be aware that my code is not fully finished but the question I have will be implemented and such. I will give proper explanation of everything further down. If you are curious the most important part is the furthest down, meaning the MiniMaxCalc() Method. If you do not wnat to read through the rest that much.

[spoiler = My Code]

namespace TicTacToe{    class AI    {        private int[] scorecollection;                          //Collection of the scores        private int score, nof0, gscore = 0;                    //score...Score for the Ai with this Move, nof0....number of 0,gscore like score just a little diffrent        private char[] mFieldcontent;                           //The current state of the Board. Where the X's and O's are        List<int> scores = new List<int>(), positionofO = new List<int>();      // A list to save all the scores and the Position where O will be.        //Reference to the Fieldcontent for outside        public char[] Fieldcontent        {            get            {                return mFieldcontent;            }            set            {                mFieldcontent = value;            }        }        //Will the main Method which can be accessed from outside        public void AI_Move()        {            CheckforScore();            MiniMaxCalc();                    }        //This Method will be Checking if a Win or a equal occured        private void CheckforWin()        {            if (mFieldcontent[0] == 'x' && mFieldcontent[3] == 'x' && mFieldcontent[6] == 'x')            {                score = -100;            }            else if (mFieldcontent[0] == 'o' && mFieldcontent[3] == 'o' && mFieldcontent[6] == 'o')            {                score = 100;            }            else if (mFieldcontent[1] == 'x' && mFieldcontent[4] == 'x' && mFieldcontent[7] == 'x')            {                score = -100;            }            else if (mFieldcontent[1] == 'o' && mFieldcontent[4] == 'o' && mFieldcontent[7] == 'o')            {                score = 100;            }            else if (mFieldcontent[2] == 'x' && mFieldcontent[5] == 'x' && mFieldcontent[8] == 'x')            {                            score = -100;            }            else if (mFieldcontent[2] == 'o' && mFieldcontent[5] == 'o' && mFieldcontent[8] == 'o')            {                score = 100;            }            else if (mFieldcontent[0] == 'x' && mFieldcontent[1] == 'x' && mFieldcontent[2] == 'x')            {                score = -100;            }            else if (mFieldcontent[0] == 'o' && mFieldcontent[1] == 'o' && mFieldcontent[2] == 'o')            {                score = 100;            }            else if (mFieldcontent[3] == 'x' && mFieldcontent[4] == 'x' && mFieldcontent[5] == 'x')            {                score = -100;            }            else if (mFieldcontent[3] == 'o' && mFieldcontent[4] == 'o' && mFieldcontent[5] == 'o')            {                score = 100;            }            else if (mFieldcontent[6] == 'x' && mFieldcontent[7] == 'x' && mFieldcontent[8] == 'x')            {                score = -100;            }            else if (mFieldcontent[6] == 'o' && mFieldcontent[7] == 'o' && mFieldcontent[8] == 'o')            {                score = 100;            }            else if (mFieldcontent[2] == 'x' && mFieldcontent[4] == 'x' && mFieldcontent[6] == 'x')            {                score = -100;            }            else if (mFieldcontent[2] == 'o' && mFieldcontent[4] == 'o' && mFieldcontent[6] == 'o')            {                score = 100;            }            else if (mFieldcontent[0] == 'x' && mFieldcontent[4] == 'x' && mFieldcontent[8] == 'x')            {                score = -100;            }            else if (mFieldcontent[0] == 'o' && mFieldcontent[4] == 'o' && mFieldcontent[8] == 'o')            {                score = 100;            }            else if (mFieldcontent[0] != '0' && mFieldcontent[1] != '0' && mFieldcontent[2] != '0' && mFieldcontent[3] != '0' && mFieldcontent[4] != '0' && mFieldcontent[5] != '0' && mFieldcontent[6] != '0' && mFieldcontent[7] != '0' && mFieldcontent[8] != '0')            {                score = 10;            }            else            {                score = 0;            }        }        //This method will check for the Score and will go through all the possiblility's. More precice explanation will follow down where I explain why I did what.        private void CheckforScore()        {            for (int i = 0; i < mFieldcontent.Length; i++)            {                if(mFieldcontent[i] == '0')                {                    mFieldcontent[i] = 'o';                    CheckforWin();                    if (score == -100)                    {                        gscore = score + 0;                        scores.Add(gscore);                        positionofO.Add(i);                        gscore = 0;                        mFieldcontent[i] = '0';                        break;                    }                    else if(score == 100)                    {                        gscore = score - 0;                        scores.Add(gscore);                        positionofO.Add(i);                        gscore = 0;                        mFieldcontent[i] = '0';                        break;                    }                    else if(score == 10)                    {                        gscore = score - 0;                        scores.Add(gscore);                        positionofO.Add(i);                        gscore = 0;                        mFieldcontent[i] = '0';                        break;                    }                    for (int i1 = 0; i1 < mFieldcontent.Length; i1++)                    {                        if (mFieldcontent[i1] == '0')                        {                            mFieldcontent[i1] = 'x';                            CheckforWin();                            if (score == -100)                            {                                gscore = score + 1;                                scores.Add(gscore);                                positionofO.Add(i);                                gscore = 0;                                mFieldcontent[i1] = '0';                                break;                            }                            else if (score == 100)                            {                                gscore = score - 1;                                scores.Add(gscore);                                positionofO.Add(i);                                gscore = 0;                                mFieldcontent[i1] = '0';                                break;                            }                            else if (score == 10)                            {                                gscore = score - 1;                                scores.Add(gscore);                                positionofO.Add(i);                                gscore = 0;                                mFieldcontent[i1] = '0';                                break;                            }                            for (int i2 = 0; i2 < mFieldcontent.Length; i2++)                            {                                if(mFieldcontent[i2] == '0')                                {                                    mFieldcontent[i2] = 'o';                                    CheckforWin();                                    if (score == -100)                                    {                                        gscore = score + 2;                                        scores.Add(gscore);                                        positionofO.Add(i);                                        gscore = 0;                                        mFieldcontent[i2] = '0';                                        break;                                    }                                    else if (score == 100)                                    {                                        gscore = score - 2;                                        scores.Add(gscore);                                        positionofO.Add(i);                                        gscore = 0;                                        mFieldcontent[i2] = '0';                                        break;                                    }                                    else if (score == 10)                                    {                                        gscore = score - 2;                                        scores.Add(gscore);                                        positionofO.Add(i);                                        gscore = 0;                                        mFieldcontent[i2] = '0';                                        break;                                    }                                    for (int i3 = 0; i3 < mFieldcontent.Length; i3++)                                    {                                        if(mFieldcontent[i3]=='0')                                        {                                            mFieldcontent[i3] = 'x';                                            CheckforWin();                                            if (score == -100)                                            {                                                gscore = score + 3;                                                scores.Add(gscore);                                                positionofO.Add(i);                                                gscore = 0;                                                mFieldcontent[i3] = '0';                                                break;                                            }                                            else if (score == 100)                                            {                                                gscore = score - 3;                                                scores.Add(gscore);                                                positionofO.Add(i);                                                gscore = 0;                                                mFieldcontent[i3] = '0';                                                break;                                            }                                            else if (score == 10)                                            {                                                gscore = score - 3;                                                scores.Add(gscore);                                                positionofO.Add(i);                                                gscore = 0;                                                mFieldcontent[i3] = '0';                                                break;                                            }                                            for (int i4 = 0; i4 < mFieldcontent.Length; i4++)                                            {                                                if(mFieldcontent[i4] == '0')                                                {                                                    mFieldcontent[i4] = 'o';                                                    CheckforWin();                                                    if (score == -100)                                                    {                                                        gscore = score + 4;                                                        scores.Add(gscore);                                                        positionofO.Add(i);                                                        gscore = 0;                                                        mFieldcontent[i4] = '0';                                                        break;                                                    }                                                    else if (score == 100)                                                    {                                                        gscore = score - 4;                                                        scores.Add(gscore);                                                        positionofO.Add(i);                                                        gscore = 0;                                                        mFieldcontent[i4] = '0';                                                        break;                                                    }                                                    else if (score == 10)                                                    {                                                        gscore = score - 4;                                                        scores.Add(gscore);                                                        positionofO.Add(i);                                                        gscore = 0;                                                        mFieldcontent[i4] = '0';                                                        break;                                                    }                                                    for (int i5 = 0; i5 < mFieldcontent.Length; i5++)                                                    {                                                        if (mFieldcontent[i5] == '0')                                                        {                                                            mFieldcontent[i5] = 'o';                                                            CheckforWin();                                                            if (score == -100)                                                            {                                                                gscore = score + 2;                                                                scores.Add(gscore);                                                                positionofO.Add(i);                                                                gscore = 0;                                                                mFieldcontent[i5] = '0';                                                                break;                                                            }                                                            else if (score == 100)                                                            {                                                                gscore = score - 2;                                                                scores.Add(gscore);                                                                positionofO.Add(i5);                                                                gscore = 0;                                                                mFieldcontent[i5] = '0';                                                                break;                                                            }                                                            else if (score == 10)                                                            {                                                                gscore = score - 5;                                                                scores.Add(gscore);                                                                positionofO.Add(i);                                                                gscore = 0;                                                                mFieldcontent[i5] = '0';                                                                break;                                                            }                                                            for (int i6 = 0; i6 < mFieldcontent.Length; i6++)                                                            {                                                                if (mFieldcontent[i6] == '0')                                                                {                                                                    mFieldcontent[i6] = 'o';                                                                    CheckforWin();                                                                    gscore = gscore + score;                                                                    if (score == -100)                                                                    {                                                                        gscore = score + 6;                                                                        scores.Add(gscore);                                                                        positionofO.Add(i);                                                                        gscore = 0;                                                                        mFieldcontent[i6] = '0';                                                                        break;                                                                    }                                                                    else if (score == 100)                                                                    {                                                                        gscore = score - 6;                                                                        scores.Add(gscore);                                                                        positionofO.Add(i);                                                                        gscore = 0;                                                                        mFieldcontent[i6] = '0';                                                                        break;                                                                    }                                                                    else if (score == 16)                                                                    {                                                                        gscore = score - 6;                                                                        scores.Add(gscore);                                                                        positionofO.Add(i);                                                                        gscore = 0;                                                                        mFieldcontent[i6] = '0';                                                                        break;                                                                    }                                                                    for (int i7 = 0; i7 < mFieldcontent.Length; i7++)                                                                    {                                                                        if (mFieldcontent[i7] == '0')                                                                        {                                                                            mFieldcontent[i7] = 'o';                                                                            CheckforWin();                                                                            gscore = gscore + score;                                                                            if (score == -100)                                                                            {                                                                                gscore = score + 7;                                                                                scores.Add(gscore);                                                                                positionofO.Add(i);                                                                                gscore = 0;                                                                                mFieldcontent[i7] = '0';                                                                                break;                                                                            }                                                                            else if (score == 100)                                                                            {                                                                                gscore = score - 7;                                                                                scores.Add(gscore);                                                                                positionofO.Add(i);                                                                                gscore = 0;                                                                                mFieldcontent[i7] = '0';                                                                                break;                                                                            }                                                                            else if (score == 10)                                                                            {                                                                                gscore = score - 7;                                                                                scores.Add(gscore);                                                                                positionofO.Add(i);                                                                                gscore = 0;                                                                                mFieldcontent[i7] = '0';                                                                                break;                                                                            }                                                                            for (int i8 = 0; i8 < mFieldcontent.Length; i8++)                                                                            {                                                                                if (mFieldcontent[i8] == '0')                                                                                {                                                                                    mFieldcontent[i8] = 'o';                                                                                    CheckforWin();                                                                                    gscore = gscore + score;                                                                                    if (score == -100)                                                                                    {                                                                                        gscore = score + 8;                                                                                        scores.Add(gscore);                                                                                        positionofO.Add(i);                                                                                        gscore = 0;                                                                                        mFieldcontent[i8] = '0';                                                                                        break;                                                                                    }                                                                                    else if (score == 100)                                                                                    {                                                                                        gscore = score - 8;                                                                                        scores.Add(gscore);                                                                                        positionofO.Add(i);                                                                                        gscore = 0;                                                                                        mFieldcontent[i8] = '0';                                                                                        break;                                                                                    }                                                                                    else if (score == 10)                                                                                    {                                                                                        gscore = score - 8;                                                                                        scores.Add(gscore);                                                                                        positionofO.Add(i);                                                                                        gscore = 0;                                                                                        mFieldcontent[i8] = '0';                                                                                        break;                                                                                    }                                                                                    mFieldcontent[i8] = '0';                                                                                }                                                                            }                                                                            mFieldcontent[i7] = '0';                                                                        }                                                                    }                                                                    mFieldcontent[i6] = '0';                                                                }                                                            }                                                            mFieldcontent[i5] = '0';                                                        }                                                    }                                                    mFieldcontent[i4] = '0';                                                }                                            }                                            mFieldcontent[i3] = '0';                                        }                                    }                                    mFieldcontent[i2] = '0';                                }                            }                            mFieldcontent[i1] = '0';                        }                     }                    mFieldcontent[i] = '0';                }            }        }        //This is making the MiniMax calculations        private void MiniMaxCalc()        {            int bestMoveA = 0;                  //This is the number for the List positionofO where the best result for the AI will occur            int bestMoveP = 0;                  //This is the number for the List positionofO where the best result for the Player will occur            int bestScoreA = -100000;           //This is the best Score the AI will get.            int bestScoreP = 100000;            //This si the best Score the Player will get.            for(int i9 = 0; i9 < scores.Count; i9++)            {                //Checking if one of the numbers in the scores List is higher then the current bestScoreA which the AI could is.                if(scores[i9] > bestScoreA)                {                    bestMoveA = i9;                    bestScoreA = scores[i9];                }                                //Checking if on of the numbers in the scores List is lower then the current bestScoreP which the AI could get. Meaning worst case scenario loosing!                if(scores[i9] < bestScoreP)                {                    bestMoveP = i9;                    bestScoreP = scores[i9];                }                //Checking if the current score would be the same as the bestScoreA                if(scores[i9] == bestScoreA)                {                    //Checking if the position of this new bestScore is not the position of the best move for Player                    if(positionofO[i9] != positionofO[bestMoveP])                    {                        //Setting this to new best move for AI                        bestMoveA = i9;                        bestScoreA = scores[i9];                    }                }            }        }    }    } 

Now the more in depth explanation:

 

Regarding the many for's:

I am using so many for's for one reason. every for stands for 1field which will be calculated through. Meaning if there are 9fields free and the AI starts it will go through every possible ending for the game. But if there are only 3 fields free the AI will only use the first 3for's and simulate that through.

 

Regarding the score checks:

[spoiler = If statement for Scores]

//Checking if Player wonif (score == -100){     gscore = score + 4; //This is the score of the player + the steps it took for it to get there     scores.Add(gscore);      //Here the gscore will be saved in the List scores     positionofO.Add(i);  //Here the position of the O will be saved(the original O the first one)     gscore = 0;              //gscore will be set back to 0     mFieldcontent[i4] = '0'; //The Fieldcontent will be set back to 0     break;         //The for-loop will be exited because this move resulted in a win/loose/equal}//Checking if AI wonelse if (score == 100){     gscore = score - 4;       //Same as above, just for AI win     scores.Add(gscore);     positionofO.Add(i);     gscore = 0;     mFieldcontent[i4] = '0';     break;}//Checking if Equalelse if (score == 10){      gscore = score - 4;      //Same as above just for Equal      scores.Add(gscore);      positionofO.Add(i);      gscore = 0;      mFieldcontent[i4] = '0';      break;} 

 

 

Now to my problem. My problem is that the AI does not always do the right thing meaning it will loose what I do not want. So here I am asking for help.

If somebody realised I did alot of posts in this section. THis may be because I am bad at coding or because I am doing alot of coding lately and alot of learning in it. Hope you guys don't hate me for that

 

 

Hope you can help me out. 

 

Nice Greets RockiLocky

[Nineshadow]

If you do want to do it like that , just do it recursive , something like a backtrack. Just keep in mind that you will need to recalculate your choices everytime the player marks a tile , unless he marked the tile you predicted he would mark.

 

Anyway , keep in mind there are legit strategies for tic tac toe.

 

1. You are first :

• If you mark the center :
  • If the opponent marks an edge tile , then it's very easy to win . Mark the tile on the corner furthest away from the one which the opponent has chosen. Then they will probably block you , but you have another opportunity and yada yada you win.
  • 
  • If the opponent marks a corner tile , it's a little more complicated but you can still do it. You mark the opposite corner , then just keep marking for opportunities or counters , but the opponent will probably counter you as well. It will end in either a win or a tie.
  • 
• If you mark a corner :
  • 
  • 
  • 

2. If you are second :

• There's no way to guarantee your win. The only way you can win is if the opponent marks an edge tile with his first move. Otherwise, it will be a tie.
• If your opponent starts with a center tile :
  • 
• If he starts with a corner tile :
  • 

[RockiLocky]

 

-snip

 

So you would trecommend me to implement this instead of the minimax algorithm?

 

Another thing why I sued the minimax algorithm(didnt mention that above) is so I get a feeling for algorithm's I want to learn more about them and implement them.

 

If I add your solution I will make it a diffrent difficulty then the minimax or maybe let these 2 AI play against each other

[Nineshadow]

So you would trecommend me to implement this instead of the minimax algorithm?

 

Another thing why I sued the minimax algorithm(didnt mention that above) is so I get a feeling for algorithm's I want to learn more about them and implement them.

 

If I add your solution I will make it a diffrent difficulty then the minimax or maybe let these 2 AI play against each other

It depends on what you want to do.

You can use the minmax algorithm , sure. It will teach you a lot of other things that the "strategy" approach won't . Then again , the strategy approach will teach you other things as well.

Here's a good article if you want more documentation : http://neverstopbuilding.com/minimax

[RockiLocky]

It depends on what you want to do.

You can use the minmax algorithm , sure. It will teach you a lot of other things that the "strategy" approach won't . Then again , the strategy approach will teach you other things as well.

Here's a good article if you want more documentation : http://neverstopbuilding.com/minimax

ok thank you man

[Nuluvius]

A more general point regarding your code, which I'm sure that you must be aware of, is that you should really try to avoid so much nesting and use of magic numbers. Put bluntly what you have there right now is known as spaghetti code. At the very least; all of those magic numbers should be behind well named constants that have a clearly justified reason for existing, methods and classes should have exactly one single concern and the cyclomatic complexity should be kept to an absolute minimum.

 

If you haven't already perhaps have a look at:

• Single responsibility, Open-closed, Liskov substitution, Interface segregation and Dependency inversion (SOLID)
• Atomicity, Consistency, Isolation, Durability (ACID)
• Test Driven Development (TDD)
• Behaviour Driven Development (BDD)
• Design Patterns - a better link

 

I can see from your posts that you are expanding out into a lot of different concepts. This would also be an excellent point for you to start learning engineering and design principles. The sooner that you can gain an understanding and appreciation for these the better really.

[olbaze]

Another thing to note is that this kind of problem solving, having the computer simulate all the possibilities, is quite often impossible. Trying to do the same for chess would require a supercomputer and many believe it's not possible for Go.

 

Heck, the traveling salesman problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem) is an example of a similar optimal-strategy problem that occurs in real life every single day.