C++ итерации через 2D-вектор, чтобы найти 3 строки

Question

Эй, все, работая над маленькой игрой на C++, «Connect 3.» Это точно так же, как Connect 4, за исключением того, что нам нужно только матч из 3, чтобы выиграть игру. Я сохраняю свою доску в 2D-векторе, который содержит ints.

vector< vector<int> > vector2d; 

И у меня есть «X» хранятся в виде 1, и «O», хранящуюся в -1, где 0 пустое пространство. Кажется, он работает до сих пор.

Итак, в моем алгоритме для игры с компьютером он находит лучшее возможное движение. У меня закончен алгоритм, но он должен знать, когда был применен «базовый случай». (Это рекурсивная.) Базовый случай либо:

1. Кто-то получил 3 в ряд, или
2. Плата полна

Проверка, если плата полна легко. Я просто перебираю и вижу, есть ли какое-либо пространство «0». Если это так, плата не заполнена. Но прежде чем я проверю это, мне нужно выяснить, есть ли у кого-то 3 подряд, а именно у меня возникают проблемы. Единственный способ, которым я могу это сделать, большой и сложный, проходя через доску 3 раза, поиск горизонтальных совпадений 3, вертикальных совпадений 3 и диагональных матчей 3. Я даже не уверен, с чего начать делая это, и я надеюсь, что есть лучший способ сделать это. Помощь будет очень признательна!

Кроме того, не уверен, что мне разрешено использовать Boost, я еще не до сих пор, и я бы не хотел его использовать. (Не уверен, есть ли у школьных компьютеров).

Редактировать: Плата не обязательно должна быть 3 на 3. Она может быть 1 на 7, 7 на 7 или любого размера. Если это не юридический размер (0,0), мой код скажет пользователю, что любой другой совет должен работать. Я использовал размеры вектора, чтобы увидеть, насколько велика доска.

Answer 1

Итак, скажем, вы используете плату 3x3.Существует конечное число выигрышных линий, которые могут быть сформированы.

1 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 

Теперь, если вы даете каждое местоположение борту немного назначение следующим образом:

1 2 4 
8 16 32 
64 128 256 

теперь вы можете работать, что 8 выигрышные линии являются следующие:

1 | 8 | 64 = 73 
    1 | 2 | 4 = 7 
    1 | 16 | 256 = 273 
    4 | 16 | 64 = 84 
    4 | 32 | 256 = 292 
    8 | 16 | 32 = 56 
64 | 128 | 256 = 448 
    2 | 16 | 128 = 146 

Теперь, если вы сохраняете 1 в любой бит позиции, которую данный игрок может легко пройти через каждое из «решений» выше и протестировать против 8 значений выше.

Так предположим, что 2 игрока имеют следующие позиции:

1 1 0 0 0 1 
    1 0 0 0 1 1 
    1 0 1 0 1 0 

Если суммировать там значения, как это сделано для «решения» следующим образом вы получите

1 | 2 | 8 | 64 | 256 = 331 
    4 | 16 | 32 | 128  = 180 

Итак, мы знаем winnign строка - 1 | 8 | 64 = 73 линии, поэтому мы можем проверить с помощью немного мудрым и следующим

331 & 73 = 73 
    180 & 73 = 0 

Таким образом, мы можем легко обнаружить, что игрок 1 имеет 3 в ряд и имеет одну, как результат «и» не равно 0.

Это значит, что вы можете подсчитать победителя максимум за 8 шагов (т. Е. Проверить, что оба игрока имеют итоговые суммы против 8 возможных ответов).

Очевидно, что сложность возрастает по мере увеличения и может казаться намного более сложной, когда у вас заканчивается бит (посмотрите на std :: bitset, например, как справиться с этим), но конечная игра будет ВСЕГДА брать меньше итераций для проверки, чем метод грубой силы. Очевидно, что для настройки требуется немного больше времени, но вы только вычисляете условия конечной игры один раз за тип платы, чтобы время амортизировалось в нескольких играх.

Во всяком случае ... Вот как бы я это сделать: D

Answer 2

Решение C++ O(N*M) с точки зрения алгоритмической сложности является наилучшим возможным, поскольку нам необходимо проверить наихудший случай каждой ячейки платы. Он выполняет итерацию по всем ячейкам на доске (i и j), пытается идти в 4 направлениях (k), а оттуда проверяет, что 3 ячейки (l) в направлении k заняты и равны.

vector<vector<int> > board(n, vector<int>(m)); // initialize 
/*   down down-right right up-right */ 
int di[] = {1, 1,   0, -1  }; // four directions i coordinate 
int dj[] = {0, 1,   1,  1  }; // four directions j coordinate 
for (int i = 0; i < n; i++) { // for each row 
    for (int j = 0; j < m; j++) { // for each column 
     for (int k = 0; k < 4; k++) { // for each direction 
      int ii = i, jj = j; 
      bool found = true; 
      if (board[ii][jj] == 0) continue; // empty space 
      for (int l = 1; l < 3 && found; l++) { // need 3 in a row 
       int iii = ii + di[k], jjj = jj + dj[k]; 
       if (iii < 0 || iii >= n) found = false, continue; // off bounds 
       if (jjj < 0 || jjj >= n) found = false, continue; // off bounds 
       if (board[iii][jjj] != board[ii][jj]) found = false; 
      } 
      if (found) { 
       printf("Hurray!\n"); 
       return; 
      } 
     } 
    } 
} 

Answer 3

Что вы просите швы о микро оптимизации. Сначала выполните его правильно, затем профиль/меру, чтобы найти узкие места, а затем подумайте, как улучшить.

Поскольку вопрос такой общий (и без примера и кода), я не думаю, что можно ответить по-другому.

Answer 4

Вам не нужно проверять всю доску каждый раз. Только новый деталь имеет значение, поэтому вам нужно только проверить те конечные условия, которые включают новый кусок. Вам нужно проверить 8 разных направлений, но каждый из них находится на одной линии и должен быть проверен вместе. Направления могут быть определены как (delta_X, delta_Y) пары: (1,0), (0,1), (1,1), (1, -1). Ваш код должен проходить в каждом направлении (как в коде от Леонида) и стараться считать столько штук с тем же значением, что и новый кусок. Затем он должен проходить в противоположном направлении, который является (-x, -y) с текущего направления, и считать эти части также. Если количество подсчитанных частей - N-1 (новая часть уже подсчитана), то у вас есть победитель.

Answer 5

Я сделал игру, как, что, первое, что я когда-либо делал в C++ на самом деле (Кому нужен привет мир: P)

И каждый может использовать его, если захочет.

Только не забудьте, что это моя первая вещь на C++, и она определенно не правильно закодирована: P, но в ней есть некоторые интересные вещи на C++. Но есть 100% оптимизированный алгоритм поиска, который проверяет абсолютное наименьшее количество требуемой перестановки, чтобы проверить три условия выигрыша строки с тяжелыми комментариями и искусством ASCII. Это может быть весьма полезно.

О, почти забыл упоминание, это консольное приложение thingy (черный экран DOS envi, что бы он ни называл). У этого есть ИИ, который (если это моя последняя версия) Должно быть хорошо. И сетка динамически построена (что было трудной частью) U может играть 3 подряд, но с максимальной сеткой 20x20 (хромая игра, которую я узнал, гораздо веселее, как 4 подряд с гравитацией)

Здесь вы найдете:

// DrieOpEenRij.cpp : Defines the entry point for the console application. 

    #include "stdafx.h" 
    #include <iostream> 
    #include <string> 
    #include <typeinfo> 

    using namespace std; 

    typedef unsigned short USHORT; 

    //USE ONLY IN A SQUARE GRID 
    //This method checks a win for the minimimum amount of spaces covering 100% amount of the grid 
    //It has 100% coverage and close to 0% overhead, discrimination between who to check for is required and 
    //so currentMove char is required to check for win on 'H' human and 'C' Computer 
    void CheckForWin(const char* Grid_ptr , const USHORT GridSize , const USHORT GridWidth ,bool &humanWin, bool &computerWin, const char currentMove) 
    { 
     //check for an x from 1-end of array 
     //for all x's check if that makes a 3 line once per linetype 
     //check for horizontal win (dont get overhead on edges) 

    //A non square grid will have been detected by now 
    const USHORT rowStart = 0; 
    const USHORT rowEnd = GridWidth-1; 
    USHORT passRowCounter = 1; 
    const USHORT Side = GridWidth; 

    const USHORT cond1 = rowEnd-2; 
    const USHORT cond2 = GridSize-Side*2; 

    //Check for all human win options (after a human move) 
    if (currentMove == 'H') 
    { 
     //Check for human win code 
     //Check all array slots for an occurence of 'X' 
     for(USHORT i = 0; i < GridSize; i++) 
     { 
      //Local stack variables, optimizations for iterations in loops and if statements, 
      //also for readability, this is (only efficient and) done only when it is guaranteed 
      //to be used in every for jump. 
      USHORT iModSide = i % Side; 
      USHORT SideMinTwo = Side - 2; 
      USHORT SidePlusTwo = Side + 2; 
      USHORT iPlusSide = i + Side; 
      USHORT iPlusSideTimesTwo = i + Side * 2; 
      USHORT iPlusOne = i + 1; 
      USHORT iPlusTwo = i + 2; 

      //If an X is found evaluate a win scenario 
      if (Grid_ptr[i] == 'X') 
      { 
       //For each row --> 
       if (iModSide < SideMinTwo) 
       { 
        //Check horizontal win from left to right 
        if (Grid_ptr[i + 1] == 'X' && Grid_ptr[i + 2] == 'X') 
        { 
         humanWin = true; 
         break; 
        } 
       } 

       //For the two values under the 'X' (colomn wise) check for 'X''X' 
       if (iPlusSideTimesTwo < GridSize) 
       { 
        if(Grid_ptr[iPlusSide] == 'X' && Grid_ptr[iPlusSideTimesTwo] == 'X') 
        { 
         humanWin = true; 
         break; 
        } 
       } 

       //CHECK FOR DIAGONAL WIN FROM TOP LEFT TO DOWN RIGHT IN ALL POSSIBLE+LEGAL SLOTS! 
       // [X] [X] [?] [?] This illustration shows that checking only at X will suffice 
       // [X] [X] [?] [?] for this specific check in screening for all Top Left --> Down Right 
       // [?] [?] [?] [?] diagonal wins, similarly the Top Right --> Down Left is done mirrored 
       // [?] [?] [?] [?] All other wins using this vector are impossible! 
       // Using this amount of conditions to find it saves a lot of searching and with it time 
       if (iPlusSideTimesTwo < GridSize && iModSide < SideMinTwo) 
       { 
        if (Grid_ptr[i+Side+1] == 'X' && Grid_ptr[iPlusSideTimesTwo+2] == 'X') 
        { 
         humanWin = true; 
         break; 
        } 
       } 

       //CHECK FOR DIAGONAL WIN FROM TOP LEFT TO DOWN RIGHT IN ALL POSSIBLE+LEGAL SLOTS! 
       // [?] [?] [Y] [Y] This illustration shows that checking only at Y will suffice 
       // [?] [?] [Y] [Y] for this specific check in screening for all Top Right --> Down Left 
       // [?] [?] [?] [?] diagonal wins, similarly the Top Left --> Down Right is done mirrored 
       // [?] [?] [?] [?] This because all other wins using this vector are impossible! 
       // Using this amount of conditions to find it saves a lot of searching and with it time 
       if (i % Side > 1 && i + Side*2-2 < GridSize) 
       { 
        if (Grid_ptr[i+Side-1] == 'X' && Grid_ptr[i+Side*2-2] == 'X') 
        { 
         humanWin = true; 
         break; 
        } 
       } 
      } //end if arrayvalue is 'X' 
     } //end for each value in array 
    } //end if currentMove 'H' 
    else if (currentMove == 'C') 
    { 
     //Check for human win code 
     //Check all array slots for an occurence of 'X' 
     for(USHORT i = 0; i < GridSize; i++) 
     { 
      //Local stack variables, optimizations for iterations in loops and if statements, 
      //also for readability, this is (only efficient and) done only when it is guaranteed 
      //to be used in every for jump. 
      USHORT iModSide = i % Side; 
      USHORT SideMinTwo = Side - 2; 
      USHORT SidePlusTwo = Side + 2; 
      USHORT iPlusSide = i + Side; 
      USHORT iPlusSideTimesTwo = i + Side * 2; 
      USHORT iPlusOne = i + 1; 
      USHORT iPlusTwo = i + 2; 

      //If an X is found evaluate a win scenario 
      if (Grid_ptr[i] == 'O') 
      { 
       //For each row --> 
       if (iModSide < SideMinTwo) 
       { 
        //Check horizontal win from left to right 
        if (Grid_ptr[i + 1] == 'O' && Grid_ptr[i + 2] == 'O') 
        { 
         computerWin = true; 
         break; 
        } 
       } 

       //For the two values under the 'O' (colomn wise) check for 'O''O' 
       if (iPlusSideTimesTwo < GridSize) 
       { 
        if(Grid_ptr[iPlusSide] == 'O' && Grid_ptr[iPlusSideTimesTwo] == 'O') 
        { 
         computerWin = true; 
         break; 
        } 
       } 

       //CHECK FOR DIAGONAL WIN FROM TOP LEFT TO DOWN RIGHT IN ALL POSSIBLE+LEGAL SLOTS! 
       // [X] [X] [?] [?] This illustration shows that checking only at X will suffice 
       // [X] [X] [?] [?] for this specific check in screening for all Top Left --> Down Right 
       // [?] [?] [?] [?] diagonal wins, similarly the Top Right --> Down Left is done mirrored 
       // [?] [?] [?] [?] All other wins using this vector are impossible! 
       // Using this amount of conditions to find it saves a lot of searching and with it time 
       if (iPlusSideTimesTwo < GridSize && iModSide < SideMinTwo) 
       { 
        if (Grid_ptr[i+Side+1] == 'O' && Grid_ptr[iPlusSideTimesTwo+2] == 'O') 
        { 
         computerWin = true; 
         break; 
        } 
       } 

       //CHECK FOR DIAGONAL WIN FROM TOP LEFT TO DOWN RIGHT IN ALL POSSIBLE+LEGAL SLOTS! 
       // [?] [?] [Y] [Y] This illustration shows that checking only at Y will suffice 
       // [?] [?] [Y] [Y] for this specific check in screening for all Top Right --> Down Left 
       // [?] [?] [?] [?] diagonal wins, similarly the Top Left --> Down Right is done mirrored 
       // [?] [?] [?] [?] This because all other wins using this vector are impossible! 
       // Using this amount of conditions to find it saves a lot of searching and with it time 
       if (iPlusSideTimesTwo+2 < GridSize && iModSide < SidePlusTwo) 
       { 
        if (Grid_ptr[i+Side-1] == 'O' && Grid_ptr[i+Side*2-2] == 'O') 
        { 
         computerWin = true; 
         break; 
        } 
       } 
      } //end if arrayvalue is 'O' 
     } //end for each value in array 
    }// else if currentMove 'C' 
} //end method 
//useAI(char* Grid_ptr) { } 

//weighGrid (char* Grid_ptr) { for (USHORT i = 0; i < GridSize(find out); i++) {} } 


void PrintGrid(char* Grid_ptr, USHORT GridWidth, USHORT GridHeight, USHORT GridSize) 
{ 
    //Abort this method if the Grid is not Square 
    if (GridWidth != GridHeight) 
    { 
     cout << "Warning! \n\nGrid is not square. This method will likely fail!" << endl; 
     cout << "Aborting method!" << endl; 
     cout << "Press a key to return to program";   
    } 
    else 
    { 
     //Since this code block's applicable to a square grid 
     //Width or Height is not relevant, both should work 
     //I have chosen to stick with Width everywhere.   

     USHORT rowStart = 0; 
     USHORT rowEnd = GridWidth-1; 
     USHORT passRowCounter = 1; 
     USHORT Side = GridSize/GridHeight; 

     for(USHORT i = 0; i < Side; i++) 
     { 
      //GO TO NEXT ROW CODE 
      rowEnd = Side * passRowCounter; 
      passRowCounter++;    
      //PRINT ALL IN THIS ROW 
      for (USHORT j = rowStart; j < rowEnd; j++) 
      { 
       cout << Grid_ptr[j]; 

      } 
      rowStart = rowEnd; 
      cout << "\n"; 
     } 
    } 
} 

void useAI(char* Grid_ptr, USHORT GridSize, USHORT GridWidth) 
{ 
    //Check all values in the array 
    //If the value is '?' weigh the priority 
    //else continue 

    //Weighing the priority 
    //If ('O' Present in legal ranges) add prio +1 

    //The AI Will function on this concept 
    //All array slots have a weight, the highest weight means the best position 
    //From top prio to lowest prio that means --> 
    //WIN IN ONE MOVE (weight + 50) 
    //NOT LOSE IN ONE MOVE (weight + 15) 
    //BLOCK ENEMY + LINK UP OWN (Equal prio but stacks so both matter) weight +1 

    //These weights are determined using 8 directional vectors sprouting from all 'X' and 'O' locations in the grid 
    //In it's path if it encounters on loc 1 'X' loc 2 + weight = 50 , and vice versa, else +1 for all 8 vectors 

    //Create a weightgrid to store the data 
    USHORT* WeightGrid_ptr = new USHORT[GridSize]; 
    USHORT* fattest_ptr = new USHORT(0); 
    USHORT* fattestIndex_ptr = new USHORT(0); 

    USHORT Side = GridWidth; 

    //Suggestion for optimization , make a forumula table to play all 8 vectors instead 
    //Per vector u need Condition for the direction first space and next space. 24 statements in a list 
    //A bit complex and harder to read so for now went the east 8 vectors copy pasting. But aware of the 
    //solution none-the-less! Unfortunatly though it seems like a maze of code, it is well documented and 
    //it's length is over 50% due to optimizations. 

    for(USHORT i = 0; i < GridSize; i++) 
    { 
     if (Grid_ptr[i] == 'X') 
     { 
      //CHECK X --> Mid Right Vector 
      //If within allowed parameters 
      if(i % Side < Side-2) 
      { 
       if(Grid_ptr[i+1] == '?' && Grid_ptr[i+2] == '?') 
       { 
        WeightGrid_ptr[i+1] += 1; 
        WeightGrid_ptr[i+2] += 1; 
       } 
       else if(Grid_ptr[i+1] == 'X') 
       { 
        WeightGrid_ptr[i+2] += 15; 
       } 
       else if (Grid_ptr[i+2] == 'X') 
       { 
        WeightGrid_ptr[i+1] += 15; 
       } 
      } 
      //CHECK X --> Down Right Vector 
      //If within allowed parameters 
      if (i % Side < Side -2 && i + Side*2 < GridSize) 
      { 
       if (Grid_ptr[i+Side+1] == '?' && Grid_ptr[i+Side*2+2] == '?') 
       { 
        WeightGrid_ptr[i+Side+1] += 1; 
        WeightGrid_ptr[i+Side*2+2] += 1; 
       } 
       else if(Grid_ptr[i+Side+1] == 'X') 
       { 
        WeightGrid_ptr[i+Side*2+2] += 15; 
       } 
       else if (Grid_ptr[i+Side*2+2] == 'X') 
       { 
        WeightGrid_ptr[i+Side+1] += 15; 
       } 
      } 
      //CHECK X --> Down Mid Vector 
      //If within allowed paramaters 
      if (i + Side*2 < GridSize) 
      { 
       if (Grid_ptr[i+Side] == '?' && Grid_ptr[i+Side*2] == '?') 
       { 
        WeightGrid_ptr[i+Side] += 1; 
        WeightGrid_ptr[i+Side*2] += 1; 
       } 
       else if (Grid_ptr[i+Side] == 'X') 
       { 
        WeightGrid_ptr[i+Side*2] += 15; 
       } 
       else if (Grid_ptr[i+Side*2] == 'X') 
       { 
        WeightGrid_ptr[i+Side] += 15; 
       } 
      } 
      //CHECK X --> Down Left Vector 
      //If within allowed paramaters 
      if(i % Side > 1 && i + Side*2 < GridSize) 
      { 
       if (Grid_ptr[i + Side*2-1] == '?' && i + Side*2-2 == '?') 
       { 
        WeightGrid_ptr[i+Side*2-1] += 1; 
        WeightGrid_ptr[i+Side*2-2] += 1; 
       } 
       else if(Grid_ptr[i + Side*2-2] == 'X') 
       { 
        WeightGrid_ptr[i+Side*2-1] += 15; 
       } 
       else if(Grid_ptr[i+Side*2-1] == 'X') 
       { 
        WeightGrid_ptr[i+Side*2-2] += 15; 
       } 
      } 
      //CHECK X --> Mid Left Vector 
      //If within allowed parameters 
      if(i % Side > 1) 
      { 
       if (Grid_ptr[i-1] == '?' && Grid_ptr[i-2] == '?') 
       { 
        WeightGrid_ptr[i-1] += 1; 
        WeightGrid_ptr[i-2] += 1; 
       } 
       else if(Grid_ptr[i-1] == 'X') 
       { 
        WeightGrid_ptr[i-2] += 15; 
       } 
       else if(Grid_ptr[i-2] == 'X') 
       { 
        WeightGrid_ptr[i-1] += 15; 
       } 
      } 
      //CHECK X --> Top Left Vector 
      //If within allowed parameters 
      if((i) % (Side > 1) && i > Side*2) 
      { 
       if (Grid_ptr[i-Side-1] == '?' && Grid_ptr[i-Side*2-2] == '?') 
       { 
        WeightGrid_ptr[i-Side-1] += 1; 
        WeightGrid_ptr[i-Side*2-2] += 1; 
       } 
       else if (Grid_ptr[i-Side-1] == 'X') 
       { 
        WeightGrid_ptr[i-Side*2-2] += 15; 
       } 
       else if (Grid_ptr[i-Side*2-2] == 'X') 
       { 
        WeightGrid_ptr[i-Side-1] += 15; 
       } 
      } 
      //CHECK X --> Mid Top Vector 
      //If within allowed parameters 
      if (i > Side*2) 
      { 
       if(Grid_ptr[i + Side] == '?' && Grid_ptr[i + Side*2] == '?') 
       { 
        WeightGrid_ptr[i + Side] += 1; 
        WeightGrid_ptr[i + Side*2] += 1; 
       } 
       else if(Grid_ptr[i + Side] == 'X') 
       { 
        WeightGrid_ptr[i + Side*2] += 15; 
       } 
       else if (Grid_ptr[i + Side*2] == 'X') 
       { 
        WeightGrid_ptr[i + Side] += 15; 
       } 
      } 
     } //end if 'X' detected 
     else if (Grid_ptr[i] == 'O') 
     { 
      //CHECK 8 VECTORS 
      //Add weights 

      //CHECK O --> Mid Right Vector 
      //If within allowed parameters 
      if(i % Side < Side-2) 
      { 
       if(Grid_ptr[i+1] == '?' && Grid_ptr[i+2] == '?') 
       { 
        WeightGrid_ptr[i+1] += 1; 
        WeightGrid_ptr[i+2] += 1; 
       } 
       else if(Grid_ptr[i+1] == 'O') 
       { 
        WeightGrid_ptr[i+2] += 50; 
       } 
       else if (Grid_ptr[i+2] == 'O') 
       { 
        WeightGrid_ptr[i+1] += 50; 
       } 

      } 

      //CHECK O --> Down Right Vector 
      //If within allowed parameters 
      if (i % Side < Side -2 && i + Side*2 < GridSize) 
      { 
       if (Grid_ptr[i+Side+1] == '?' && Grid_ptr[i+Side*2+2] == '?') 
       { 
        WeightGrid_ptr[i+Side+1] += 1; 
        WeightGrid_ptr[i+Side*2+2] += 1; 
       } 
       else if(Grid_ptr[i+Side+1] == 'O') 
       { 
        WeightGrid_ptr[i+Side*2+2] += 50; 
       } 
       else if (Grid_ptr[i+Side*2+2] == 'O') 
       { 
        WeightGrid_ptr[i+Side+1] += 50; 
       } 
      } 

      //CHECK O --> Down Mid Vector 
      //If within allowed paramaters 
      if (i + Side*2 < GridSize) 
      { 
       if (Grid_ptr[i+Side] == '?' && Grid_ptr[i+Side*2] == '?') 
       { 
        WeightGrid_ptr[i+Side] += 1; 
        WeightGrid_ptr[i+Side*2] += 1; 
       } 
       else if (Grid_ptr[i+Side] == 'O') 
       { 
        WeightGrid_ptr[i+Side*2] += 50; 
       } 
       else if (Grid_ptr[i+Side*2] == 'O') 
       { 
        WeightGrid_ptr[i+Side] += 50; 
       } 
      } 

      //CHECK O --> Down Left Vector 
      //If within allowed paramaters 
      if(i % Side > 1 && i + Side*2 < GridSize) 
      { 
       if (Grid_ptr[i + Side*2-1] == '?' && i + Side*2-2 == '?') 
       { 
        WeightGrid_ptr[i+Side*2-1] += 1; 
        WeightGrid_ptr[i+Side*2-2] += 1; 
       } 
       else if(Grid_ptr[i + Side*2-2] == 'O') 
       { 
        WeightGrid_ptr[i+Side*2-1] += 50; 
       } 
       else if(Grid_ptr[i+Side*2-1] == 'O') 
       { 
        WeightGrid_ptr[i+Side*2-2] += 50; 
       } 
      } 

      //CHECK O --> Mid Left Vector 
      //If within allowed parameters 
      if(i % Side > 1) 
      { 
       if (Grid_ptr[i-1] == '?' && Grid_ptr[i-2] == '?') 
       { 
        WeightGrid_ptr[i-1] += 1; 
        WeightGrid_ptr[i-2] += 1; 
       } 
       else if(Grid_ptr[i-1] == 'O') 
       { 
        WeightGrid_ptr[i-2] += 50; 
       } 
       else if(Grid_ptr[i-2] == 'O') 
       { 
        WeightGrid_ptr[i-1] += 50; 
       } 
      } 

      //CHECK O --> Top Left Vector 
      //If within allowed parameters 
      if((i) & (Side > 1) && i > Side*2) 
      { 
       if (Grid_ptr[i-Side-1] == '?' && Grid_ptr[i-Side*2-2] == '?') 
       { 
        WeightGrid_ptr[i-Side-1] += 1; 
        WeightGrid_ptr[i-Side*2-2] += 1; 
       } 
       else if (Grid_ptr[i-Side-1] == 'O') 
       { 
        WeightGrid_ptr[i-Side*2-2] += 50; 
       } 
       else if (Grid_ptr[i-Side*2-2] == 'O') 
       { 
        WeightGrid_ptr[i-Side-1] += 50; 
       } 
      } 

      //CHECK O --> Mid Top Vector 
      //If within allowed parameters 
      if (i > Side*2) 
      { 
       if(Grid_ptr[i + Side] == '?' && Grid_ptr[i + Side*2] == '?') 
       { 
        WeightGrid_ptr[i + Side] += 1; 
        WeightGrid_ptr[i + Side*2] += 1; 
       } 
       else if(Grid_ptr[i + Side] == 'O') 
       { 
        WeightGrid_ptr[i + Side*2] += 50; 
       } 
       else if (Grid_ptr[i + Side*2] == 'O') 
       { 
        WeightGrid_ptr[i + Side] += 50; 
       } 
      } 
     } 
    } // end for scan 'X' 'O' 

    //Get highest value from weightgrid, add an 'O' to that position, end method automatically 
    for (USHORT q = 0; q < GridSize; q++) 
    { 
     if (Grid_ptr[q] == '?') 
     { 
      //If a better spot is found 
      if (WeightGrid_ptr[q] > *fattest_ptr) 
      { 
       *fattest_ptr = WeightGrid_ptr[q]; 
       *fattestIndex_ptr = q; 
      } 
     } 
    } 

    Grid_ptr[*fattestIndex_ptr] = 'O'; 

    //SAFE DELETE POINTER WeightGrid_ptr 
    if (WeightGrid_ptr != NULL) 
    { 
     delete[] WeightGrid_ptr; 
     WeightGrid_ptr = NULL;  
    } 
    //SAFE DELETE POINTER fattest_ptr 
    if (fattest_ptr != NULL) 
    { 
     delete fattest_ptr; 
     fattest_ptr = NULL;  
    } 
    //SAFE DELETE POINTER fattestIndex_ptr 
    if (fattestIndex_ptr != NULL) 
    { 
     delete fattestIndex_ptr; 
     fattestIndex_ptr = NULL;   
    } 

} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    //& adress off  |-| &x = 0x? 
    //* value pointed by |-| a = *b 

    //Make the required variables on the heap 
    USHORT GridHeight = 0; 
    USHORT GridWidth = 0; 
    USHORT GridSize = 0; 
    USHORT moveCounter = 0; 



    char currentMove; 

    USHORT input; 
    //bool* humanWin_ptr = new bool(false); 
    //bool* computerWin_ptr = new bool(false); 

    bool humanWin_ptr = false; 
    bool computerWin_ptr = false; 

    bool Draw = false; 

    cout << "A challanger has arrived!" << endl; 

    //WARNING FOR THIS BLOCK! Special condition on for loop! 
    for(;;) 
    { 
     cout << "Please state the width for the grid \n"; 
     scanf_s("%hu", &input); 
     if (input > 2 && input < 20) 
     { 
      GridWidth = input; 
      break; //CRITICAL CODE 
     } 
     else 
     { 
      cout << "Input was not correct, please state a number between 3 and 20 \n\n"; 
      cout << "Example of correct input '3' (without quotes) \n";   
     } 
    } 

    //WARNING FOR THIS BLOCK! Special condition on for loop! 
    for(;;) 
    { 
     cout << "Please state the height for the grid \n"; 
     scanf_s("%hu", &input); 
     if (input > 2 && input < 20) 
     { 
      GridHeight = input; 
      break; //CRITICAL CODE 
     } 
     else 
     { 
      cout << "Input was not correct, please state a number between 3 and 20 \n\n"; 
      cout << "Example of correct input '3' (without quotes) \n"; 
     } 
    } 

    cout << "You have succesfully filled in the paperwork to create the Grid" << endl; 

    GridSize = GridHeight * GridWidth; 
    cout << "The total GridSize is " << GridSize << " tiles in size" << endl; 

    //if (GridWidth != GridHeigth) 
    //{ 
    // cout << "Warning! \n\nGrid is not square. Program may run irregularly!"; 
    // cout << "Close the program or press a key to continue"; 
    // scanf(); 
    //} 

    //Note: pointer to a Grid object on the heap 
    char* Grid_ptr = new char[GridSize]; 


    //Initialize Grid as empty 
    for (USHORT i = 0; i < GridSize; i++) 
    { 
     Grid_ptr[i] = '?';  
    } 



    //Visualize this step 
    cout << "Grid created as empty Grid" << endl; 
    cout << endl; 

    cout << "Please read the following introduction if you wish for an explanation of the game" << endl; 
    cout << "You will be reffered to as Player One equally so the opponent as AI" << endl; 
    cout << "You always start with the first move" << endl; 
    cout << "The condition for victory is a line of X X X (3 total) in a single line, colomn or a diagonal line across the Grid" << endl; 
    cout << "Turns are exchanged per move 1 : 1, there are no time limits so use all you need" << endl; 
    cout << "Player One can not lose this 3x3 Grid game when the best option is always chosen" << endl; 
    cout << "Consider playing a larger field if you wish to win, Best of luck!" << endl; 
    cout << "The grid is filled in like this!" << endl; 

    PrintGrid(Grid_ptr, GridWidth, GridHeight, GridSize); 

    while(humanWin_ptr == false && computerWin_ptr == false && Draw == false) 
    { 
     cout << "Players One's Turn! \n"; 
     cout << "Please fill in the number your X";  

     currentMove = 'H'; 
     for(;;) 
     { 
      scanf_s("%i" , &input); 
      if (Grid_ptr[input] == 'X' || Grid_ptr[input] == 'O') 
      { 
       cout << "That space is already taken ,try another"; 
      } 
      else 
      { 
       Grid_ptr[input] = 'X'; 
       moveCounter++; 
       break; 
      } 
     } 

     cout << '\n'; 
     PrintGrid(Grid_ptr, GridWidth, GridHeight, GridSize); 
     CheckForWin(Grid_ptr, GridSize, GridWidth, humanWin_ptr, computerWin_ptr, currentMove); 

     cout << "AI is making a move!" << endl; 

     currentMove = 'C'; 
     useAI(Grid_ptr, GridSize, GridWidth); 
     cout << '\n'; 
     PrintGrid(Grid_ptr, GridWidth, GridHeight, GridSize); 
     CheckForWin(Grid_ptr, GridSize, GridWidth, humanWin_ptr, computerWin_ptr, currentMove); 

     if (humanWin_ptr) 
     { 
      cout << "Congratulations you have won the game! \n"; 
      char c; 
      puts ("Enter any text. Include a Space ('.') in a sentence to exit: \n"); 
      do 
      { 
       c=getchar(); 
       putchar (c); 
      } 
      while (c != ' '); 
     } 
     else if (computerWin_ptr) 
     { 
      cout << "The computer won this match, better luck next time! \n"; 
      char c; 
      puts ("Enter any text. Include a Space ('.') in a sentence to exit: \n"); 
      do 
      { 
       c=getchar(); 
       putchar (c); 
      } 
      while (c != ' ');    
     } 

     if (moveCounter >= GridSize) 
     { 
      Draw = true; 
      cout << "The game was a draw, good fighting!"; 
     } 
    } 

    //int ch = 0; 
    //ch = _getch(); 
    //wint_t _getwch(void); 


    //SAFE DELETE POINTER GRID 
    if (Grid_ptr != NULL) 
    { 
     delete[] Grid_ptr; 
     Grid_ptr = NULL;  
    } 
    /* 
    //SAFE DELETE POINTER Human Win 
    if (humanWin_ptr != NULL) 
    { 
     delete humanWin_ptr; 
     humanWin_ptr = NULL;   
    } 
    //SAFE DELETE POINTER Computer Win 
    if (computerWin_ptr != NULL) 
    { 
     delete computerWin_ptr; 
     computerWin_ptr = NULL;  
    }*/ 



    return 0; 
}