Optimal value in a 3 dimensional array

[annolliwohe]

Hello I wish to choose the optimal value in a 3 dimensional array is it possible to do it with this program:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getHeight(int n) {
   return (n == 1) ? 0 : 1 + log2(n / 2);
}
int minmax(int height, int depth, int nodeIndex,
bool maxPayer, int values[], int alpha,
int beta) {
   if (depth == height) {
      return values[nodeIndex];
   }
   if (maxPayer) {
      int bestValue = INT_MIN;
      for (int i = 0; i < height - 1; i++) {
         int val = minmax(height, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
         bestValue = max(bestValue, val);
         alpha = max(alpha, bestValue);
         if (beta <= alpha)
            break;
      }
      return bestValue;
   } else {
      int bestValue = INT_MAX;
      for (int i = 0; i < height - 1; i++) {
         int val = minmax(height, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
         bestValue = min(bestValue, val);
         beta = min(beta, bestValue);
         if (beta <= alpha)
            break;
      }
      return bestValue;
   }
}
int main() {
   int values[] = {13, 8, 24, -5, 23, 15, -14, -20};
   int height = getHeight(SIZE(values));
   int result = minmax(height, 0, 0, true, values, INT_MIN, INT_MAX);
   cout <<"Result : " << result << "\n";
   return 0;
}

I would like to do it with a painting of this type (3D) :

int arr[1][1][1] = { { {100, 2, 3}, {99, 8, 6}, {78, 5, 4} },
                     { {250, 35, 54}, {154, 12, 24}, {28, 3, 19} } };

Except that I have to modify the array because it will contain double values. Can you please help me?

A little joke for the road :
"The way to hell is paved with unicode intentions" lool

[lastchance]

http://www.cplusplus.com/reference/algorithm/minmax_element/

If you use ordinary arrays then the elements are stored in contiguous memory so you can still use a single call to this. It doesn't matter if your array is of int or double type.

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int main()
{
   const int N0 = 2, N1 = 3, N2 = 3;
   int arr[N0][N1][N2] = { {  { 100,  2,  3 }, {  99,  8,  6 }, { 78, 5, 4  }  },
                           {  { 250, 35, 54 }, { 154, 12, 24 }, { 28, 3, 19 }  }   };
   auto pr = minmax_element( &arr[0][0][0], &arr[0][0][0] + N0*N1*N2 );
   cout << "Minimum: " << *pr.first  << '\n'
        << "Maximum: " << *pr.second << '\n';
}

[annolliwohe]

Hello, I misspoke. I would like to select the optimal triplet with a tic-tac-toe or alpha-beta-pruning. The problem is that the code I posted only works with a 1-dimensional array.

If I have a list of three values like this one

line 1: 600; 0.438; 0.000384
line 2: 50; 1.948; 9.9833
line 3: 8.33; 90.209; 2.489
line 4 :20 ; 254.39 ; 25.0209

What is the optimal value line to choose? I would like to find the answer with a tic-tac-toe or alpha-beta pruning.
Is it possible to do this?

[lastchance]

(1) Your latest example is a 2-dimensional array, not a 3-d one.

(2) What do you mean by "optimal value line"?

(3) You don't have a tree or heap; why do you suppose this can be done with an array?

[annolliwohe]

Hello, I want to identify the line of 3 values that represents the best strategy as we do in the game of chess with tic-tac-toe or alpha-beta pruning. I need to have a table with rows of three values and identify which three values represent the best "strategy".

In my example I put 4 lines of 3 values, in the execution of the code I have many more lines. I want to make some kind of decision support. I think I can do it with the code I posted but I can't do it.

I used an array because the program uses an array and I don't know how to use a tree.

[keskiverto]

Why do you talk about 3D when your data is 1D?

line 1: 600; 0.438; 0.000384
line 2: 50; 1.948; 9.9833
line 3: 8.33; 90.209; 2.489
line 4 :20 ; 254.39 ; 25.0209

That is not 3D. It could be 2D, but you did show that it is 1D.

Your problem is this:
You have two values: A and B. You need to know whether A < B.

Your "line" could be an object of type Line:

struct Line {
  double x {};
  double y {};
  double z {};
};

Here is a 1D array that has 3 Lines:

Line values[] {
  {600, 0.438, 0.000384},
  {50, 1.948, 9.9833},
  {20, 254.39, 25.0209} };

Lets take values[0] < values[1]. Is that expression true or false?

You can define, aka "overload", operator<

// operator returns true, if A < B
bool operator< ( const Line& A, const Line& B )
{
  // use A.x, A.y, A.z, B.x, B.y, and B.z to compute the result
}

[annolliwohe]

I understand the idea, but I'm not interested in which value is smaller or larger. In this example the third value and the second value must be the smallest possible while the first must be the largest. I'm talking about game theory for line selection. How can I have a tic-tac-toe or alpha-beta pruning that selects the line that represents the best strategy? By following the principle of the code I posted at the beginning? Is it possible that this code selects three values in the choice it makes ?

[lastchance]

annolliwohe wrote:

but I'm not interested in which value is smaller or larger

Then how do you define "optimal"?

annolliwohe wrote:

I'm talking about game theory for line selection.

Not convinced.

[keskiverto]

I understand the idea

Are you sure?

the third value and the second value must be the smallest possible while the first must be the largest

In other words, A < B is clearly true, if A.x < B.x and A.y > B.y and A.z > B.z
Similarly A < B is clearly false, if A.x > B.x and A.y < B.y and A.z < B.z
It is up to you to formulate the less clear cases.

If you can say which of the lines is "best" based on its values, then you can write the operator<

[annolliwohe]

Okay, I don't understand the idea and I'm not talking about game theory. In fact I don't know why I'm asking a question. I don't want A.x < B.x or A.y > B.y I want A.x to be bigger than all A.x and A.y to be smaller than all A.y and A.z to be smaller than all A.z. Stop believing that because you know how to code better, you are able to think for people. The code I posted is to evaluate moves to play in a game, it's game theory, the return of the code is not the minimum value that I know. It returns 13, not -20.

[lastchance]

You cannot guarantee that there is ANY single line such that ITS x value is bigger than ALL other lines' x values and ITS y is less than ALL other lines' y values and ITS z is less than ALL other z values. Such a line may simply not exist. As a simple example, take
1,1,1
2,2,2
3,3,3

You could devise a "score" relating to how many other lines these individual comparisons were true ... but you couldn't guarantee that any line would have a score of 100%. Nevertheless, it would allow you to define "optimal". In my example above, the first line scores 4, the second line scores 3, and the third line scores 2.

Unfortunately, the fact that it corresponds to moves in a game does not make it "game theory".

[annolliwohe]

Ok I have to assign a score to all 3 values with a scale that allows me to distinguish the importance of each value between them. To be able to judge which are the 3 values to select. Even if I'm not 100% sure about a decision, I would have an average decision.

Look at the bottom of the page :

https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

[lastchance]

Yes, but you don't have a tree (or a heap). So which "branches" would you like to cut off?

You could simply SCORE your lines (by a sequence of comparisons against all other lines) as I showed in my previous post. Then choose the line with the highest score. That is what I would regard as "optimal".

You are doing three distinct comparisons per line. That is NOT the same as the 1-dimensional less-than vs greater-than comparisons that apply to building a tree.

[lastchance]

Try this:

#include <iostream>
#include <vector>
using namespace std;


struct line
{
   double x, y, z;
};


int main()
{
   vector<line> L = { { 1, 1, 1 },
                      { 2, 2, 2 },
                      { 3, 3, 3 } };

   // Score lines
   int maxScore = -1, maxi = -1;
   for ( int i = 0; i < L.size(); i++ )
   {
      int score = 0;
      for ( int j = 0; j < L.size(); j++ ) score += ( L[i].x > L[j].x ) + ( L[i].y < L[j].y ) + ( L[i].z < L[j].z );
      if ( score > maxScore ) { maxScore = score;   maxi = i; }
      cout << "Line " << i << " scores " << score << '\n';
   }

   cout << "The optimal line is " << L[maxi].x << ", " << L[maxi].y << ", " << L[maxi].z << " with score " << maxScore << '\n';
}

Line 0 scores 4
Line 1 scores 3
Line 2 scores 2
The optimal line is 1, 1, 1 with score 4

[keskiverto]

Lets take just two "dimensions":

I don't want A.x < B.x or A.y > B.y I want A.x to be bigger than all A.x and A.y to be smaller than all A.y

{ 1, 3 }
{ 2, 7 }

Two lines. "Two A's", but lets call fist line "A" and second "B".
A.x < B.x (1 < 2), and thus B.x is bigger than all A.x
A.y < B.y (3 < 7), and thus A.y is smaller than all B.y

All the data that you have are the four numbers: {{ 1, 3 }, { 2, 7 }}
Looking at just x the B is the winner. Looking at just y the A is the winner.

Which of the two is the winner? Why?
Is it a tie and both lines are equally good?

[annolliwohe]

Thanks for the code proposal, I will try this solution. On my side I looked to sort values and I found ranking codes like this one but it's always for a single value with respect to others and not several values between them:

    #include <algorithm>

    #include <vector>

    #include <iostream>

    template < typename Vector >
      std::vector < double > rank(const Vector & v) {
        std::vector < std::size_t > w(v.size());
        std::iota(begin(w), end(w), 0);
        std::sort(begin(w), end(w),
          [ & v](std::size_t i, std::size_t j) {
            return v[i] < v[j];
          });

        std::vector < double > r(w.size());
        for (std::size_t n, i = 0; i < w.size(); i += n) {
          n = 1;
          while (i + n < w.size() && v[w[i]] == v[w[i + n]]) ++n;
          for (std::size_t k = 0; k < n; ++k) {
            r[w[i + k]] = i + (n + 1) / 2.0; // average rank of n tied values
            // r[w[i+k]] = i + 1;     // min 
            // r[w[i+k]] = i + n;     // max
            // r[w[i+k]] = i + k + 1; // random order
          }
        }
        return r;
      }

    int main() {
      std::vector < double > v = {
        7.3,
        3.5,
        0.01,
        3,
        5
      };
      std::vector < double > ranks = rank(v);

      for (std::size_t i = 0; i < v.size(); ++i)
        std::cout << v[i] << " : " << ranks[i] << '\n';

      return 0;
    }

It is to sort out the covariance, volatility and return. The example given is not real. But this is the meaning of the 3 values, the covariance to look for is positive but as close as possible to 0 and the volatility must also be as close as possible to 0 but different from 0 and the return must be maximum.

And yes somehow two lines can be equally good.

[annolliwohe]

Hello how can I declare vector<line> to be valid for the whole program outside the main function please? And how do I clean it with clear like a normal vector, I don't know vector<line> ?

[lastchance]

There is no need to declare it outside the main program - just pass it via a function argument. There are a few uses for global variables, but this isn't one of them.

vector<line> is just a type of container, in the same way that vector<int> is a type of container. The variable name is just L, and you would clear it with L.clear(), the same as for any other vector.

[annolliwohe]

Hello, ok thanks for the details it's great.