Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Álvaro

Member Since 07 Mar 2002
Online Last Active Today, 03:39 PM

#5207590 Efficient way to erase an element from std::vector

Posted by Álvaro on Yesterday, 07:58 PM

http://stackoverflow.com/questions/62340/does-pop-back-really-invalidate-all-iterators-on-an-stdvector

However, in your code example, it can invalidate it when it is pointing to the last element and the value is below 10. In which case Visual Studio debug STL will mark iterator as invalidated, and further check for it not being equal to end() will show an assert.




#5207488 Using torque to rotate an object into a desired orientation

Posted by Álvaro on Yesterday, 12:55 PM

In order to solve this problem, I would start with an easier problem: Applying a force try to get a particle to reach a particular position. If you do the naive thing and accelerate towards the point, you'll get oscillations just like the ones you observe. Look up "arrive steering behavior" for some attempts at solving this problem. You can then try to adapt the steering behavior to work with rotations; I don't think that would be very hard to do.


#5207342 Efficient way to erase an element from std::vector

Posted by Álvaro on 28 January 2015 - 09:24 PM

The usual trick is to swap with the last element and then pop_back. It might be more efficient then your code in some cases.


#5207050 Change of coordinate matrix

Posted by Álvaro on 27 January 2015 - 08:46 PM

You need to apply a translation to move the point (2,2) to the origin, then do the scaling, then undo the translation.

http://www.wolframalpha.com/input/?i={{1%2C0%2C2}%2C{0%2C1%2C2}%2C{0%2C0%2C1}}.{{2%2C0%2C0}%2C{0%2C1%2C0}%2C{0%2C0%2C1}}.{{1%2C0%2C-2}%2C{0%2C1%2C-2}%2C{0%2C0%2C1}}

EDIT: Sorry, I follow the convention that points and vectors are columns, not rows. Transpose everything if you wish.


#5207016 Some programmers actually hate OOP languages? WHAT?!

Posted by Álvaro on 27 January 2015 - 05:33 PM

Object oriented is part of the continuum of preferring nouns or verbs.  Languages tend to prefer objects, the nouns, or they tend to prefer verbs, the functions or actions. When you crate an opaque structure and operate on it like C's FILE*, that is a noun. When you work the opposite direction, SELECT whatever FROM whatever WHERE whatever, you are focusing on verbs, that is more functional.


This story of some languages putting emphasis on nouns or verbs doesn't make any sense to me. When you have an opaque structure like FILE * in C, you then `fopen' it, `fread' from it, `fwrite' to it and `fclose' it. If anything the emphasis seems to be on the verbs. When you have a language that can only be used to query a bunch of tables, it looks to me like the emphasis is on the nouns; or at least you could look at it that way.

The main difference between C and SQL is that in C you specify what steps to take, while in SQL you specify the results you want, and it's up to the RDBM to figure out a good plan for getting that information (I think this is called imperative -vs- declarative).


#5206892 Some programmers actually hate OOP languages? WHAT?!

Posted by Álvaro on 27 January 2015 - 05:13 AM

DISCLAIMER: I probably fit into several of Hodgman's categories. smile.png

I happen to not like OOP, but it's not because of objects: It's because of the second "O". I understand and use objects regularly, but I don't find it healthy to orient your programming towards a particular tool. The name of the paradigm implies that you need to buy into it completely and you can't write any code outside of methods for classes.

There are certain types of programs for which OOP might be a perfectly good solution (making GUIs comes to mind). It so happens that most of the programs I like to write (board game AI is the main example) don't benefit a whole lot from structuring things into objects. For instance, when writing a chess engine there isn't much to be gained from having objects representing the pieces, the squares on the board or the players: For the most part you can use enums or even small integers to identify all those things. For higher-level concepts (the board, a game, an opening book, a transpositions table, an engine...) objects are generally a good fit.

The main strength of objects, in my opinion, is in defining clear interfaces between parts of the code. And that's primarily what I use them for.


#5206786 How to implement a wumpus world agent?

Posted by Álvaro on 26 January 2015 - 05:03 PM

The first approach should always be "how would YOU decide what to do"? Then see if you can put it down in code. You could also look at the situation as an optimization problem and then use some sort of Monte Carlo technique. But that might be overkill.

Oh, and there's always this secret website.


#5206188 Would this be considered duplicate code?

Posted by Álvaro on 23 January 2015 - 07:27 AM

From what I can gathered about duplicate code, it is if the list of code that occurs more than once. Okay, based on what context? Is a duplicate code based on the similar appearance of the code?


Sure, similar appearance is how you normally identify opportunities to remove duplicate code. But the key test for me is, if I ever need to modify one of the blocks, am I likely to need to modify the other blocks in the same way? If that's the case, it's probably worth refactoring. Hodgman's suggestion is precisely how I think this should be done: Repetitive code structures can usually be refactored so the code is compact and the different cases are handled by a data structure.


#5205460 Moving a object directly towards another object?

Posted by Álvaro on 19 January 2015 - 11:32 PM

You don't need angles for this. "Calculating the difference in x,y" is precisely the right thing to do. If your missile starts at (10,10) and needs to move to (400,420), it needs to add (390,410) to its initial position. You can do it progressively, by adding only a fraction of (390,410).

Missile_position_at_time(t) = (10,10) + (390,410) * t

If you need to rotate your missile to face in the direction of movement, you can normalize the vector (390,410) to obtain a unit-length vector in the direction the missile is facing. That's all that should be needed to do the rotation. If you are using an API that insists on using angles to express rotations, you can compute atan2(410,390) (notice the order of coordinates!).


#5203572 Algorithm for a "fill" tool in a 2D array?

Posted by Álvaro on 11 January 2015 - 05:59 PM

http://en.wikipedia.org/wiki/Flood_fill


#5203313 About computer instruction in relation to RAM consumption

Posted by Álvaro on 10 January 2015 - 01:13 PM

Your question number 1 means you don't understand anything about how a computer works. Even a Google search for "how does a computer work" will probably teach you that a processor reads its program from RAM. So a program needs to be loaded there.

I think you should probably do some reading and try to answer the other questions on your on.

I don't know what to tell you about question number 6.


#5203249 Streaming - fstream giving up

Posted by Álvaro on 10 January 2015 - 06:47 AM

No, of course there is no limit. There is a bug in your program, or your compiler, or your library, or your OS. My money is on the first. smile.png

Have you considered a memory-mapped file for what you are doing?


#5203247 How can sample rate be 44000Hz?

Posted by Álvaro on 10 January 2015 - 06:32 AM

Ohforf's description seems correct to me, except I am not sure it is all that relevant for sound at 44,100 samples per second. What if you use a crappy filter, or perhaps even no filter at all? The resulting signal is not a correct reconstruction of the original, but the difference of the two signals is guaranteed to not have any frequency components under 22.5KHz (a simple corollary of the sampling theorem), which means that an ear cannot distinguish them.


#5203176 Procedural planet, visible seams

Posted by Álvaro on 09 January 2015 - 04:32 PM

How did you compute your noise? The standard solution to this type of problem is to use 3D noise evaluated at the points of the sphere. Then your particular tessellation shouldn't be very noticeable.


#5202867 Heuristic works just when I play for black player

Posted by Álvaro on 08 January 2015 - 11:09 AM

Goodness me. You don't have a bug: You have many bugs. I'll add some comments to your code.
 
protected MoveValue executeSearch(double alpha, double beta, int depth) {
    MoveValue bestMove = null;
    double best = Double.MIN_VALUE;
    // This looks like a mistake. See https://code.google.com/p/error-prone/issues/detail?id=203
    
    ArrayList<Move> moves = sortMoves(generateLegalMoves(playerType), 0);
    Iterator<Move> movesIterator = moves.iterator();
    while (movesIterator.hasNext() && canContinue()) {
        Move move = movesIterator.next();
        board.applyMove(move);
        if (bestMove == null) {
            bestMove = new MoveValue();
            bestMove.returnMove = move;
        }
        double score = -negaScout(best, best, depth - 1, 0, playerType.opponent());
        // This call to negaScout seems incorrect. If I understand correctly and we
        // are in the function that searches the root, you want to pass (-beta, -alpha) as the search window

        board.undoLastMove();
        if (score > best) {
            bestMove = new MoveValue(score, move);
            // Where is `best' updated? Shouldn't it be here?
            // Why does `best' even exist? Why not use `alpha' instead?
            // Speaking of which, where is `alpha' used in this function?
        }
    }
    return bestMove;
}

protected double negaScout(double alpha, double beta, int maxDepth, int currentDepth, MarbleType player) {
    if (!canContinue()) {
        // This happens when time's up so we don't need to go on.
        // You probably shouldn't be checking this every single node. You might find out you spend a significant chunk of time checking the clock
        return 0;
    }
    if (maxDepth == 0 || board.isGameOver()) {
        return currentHeuristic.evaluateBoard();
        // Aha! Your evaluation function is expected to return a score from the point of view of the player to move.
    }
    long hash = ZobristKey.generateHash();
    HashEntry entry = transpositionTable.get(hash);
    if (entry != null) {
        if (entry.depth >= currentDepth) {
            switch (entry.flag) {
                case LOWER_BOUND: {
                    alpha = Math.max(alpha, entry.score);
                    break;
                }
                case UPPER_BOUND: {
                    beta = Math.min(beta, entry.score);
                    break;
                }
                case EXACT_SCORE: {
                    return entry.score;
                }
            }
            if (alpha >= beta) {
                return alpha;
            }
        }
    }
    // You should probably also store a first move to try in the hash tables.
    // But this can wait until you get your signs right. :)
	
// Null move pruning
    double nullValue = -negaScout(-beta, -beta - 1, 0, 0, player.opponent());
    if (nullValue >= beta) {
        updateTranspositionTableEntry(nullValue, alpha, beta, currentDepth, hash);
        return nullValue;
    }
    ArrayList<Move> moves = sortMoves(generateLegalMoves(player), currentDepth);
    double scoutWindow = beta, currentValue = alpha;
    Iterator<Move> movesIterator = moves.iterator();
    while (movesIterator.hasNext() && canContinue()) {
        Move move = movesIterator.next();
        board.applyMove(move);
        double score = -negaScout(-scoutWindow, -currentValue, maxDepth--, currentDepth++, player.opponent());
        // Operators -- and ++ don't do what you think they do. You want `maxDepth - 1' and
        // `currentDepth + 1' instead.
        
        // You could call undoLastMove here, instead of doing it in three different places further down.
        
        if (score > currentValue) {
            currentValue = score;
        }
        if (currentValue >= beta) {
            board.undoLastMove();
            // History sorting based on prunings
            int prunings = 0;
            if (historyTable.containsKey(move)) {
                prunings = historyTable.get(move);
            }
            historyTable.put(move, prunings++);
            // Again, you probably mean `prunings + 1', unless this is a bizarre language where that's what ++ means.
            break;
        }
        if (currentValue >= scoutWindow) {
            currentValue = -negaScout(-beta, -currentValue, maxDepth--, currentDepth++, player.opponent());
            // -- and ++, as above
            if (currentValue >= beta) {
                board.undoLastMove();
                // History sorting based on prunings
                int prunings = 0;
                if (historyTable.containsKey(move)) {
                    prunings = historyTable.get(move);
                }
                historyTable.put(move, prunings++);
                break;
            }
        }
        scoutWindow = currentValue++;
        // ++, as above
        board.undoLastMove();
    }
    updateTranspositionTableEntry(currentValue, alpha, beta, currentDepth, hash);
    return currentValue;
}
You really should sort out the sign issue before you introduce transposition tables or even scout search, just because those are extra sources of bugs. I would actually recommend you start with vanilla NegaMax and progressively introduce alpha-beta cuts, transposition tables and scout search, probably in that order.

It is possible your scout implementation is sound, but I find it easier to think about if you follow the pseudo-code in the Wikipedia article about PVS.

Another piece of advice: Use integers as evaluation values. It's not like you can't use doubles, but it gets trickier, and all the pieces of code you based your code on were actually using integers as scores. That's why you add 1 to the current best score for the scout search, instead of using something like java.lang.Math.nextAfter.




PARTNERS