Stack Overflow
Stack Overflow

Questions tagged [negamax]

Variant form of minimax search that relies on the zero-sum property of a two-player game. The objective is to find the best move for the player that's playing at the root node.

62 questions
7
votes
1 answer

What is the difference between Minimax and Negamax?

I'm confused with these two. is Negamax just an optimization for minimax? or is Negamax is another search tree algorithm? If negamax is another search tree algorithm, then which one is better?
James Urian
  • 123
  • 3
  • 7
6
votes
1 answer

Transposition tables for python chess engine

This is a follow-up to my last post. The code works without any errors and can calculate the next best move. I've been looking into how to incorporate transposition tables and move ordering into my negamax function to make it run faster and more…
Bruno
  • 103
  • 6
5
votes
1 answer

Transpositional tables with alpha beta pruning

I'm trying to implement the alpha beta pruning with transpositional tables, I found the pseudocode of the algorithm in wikipedia: https://en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 However I belive that this psudocode is wrong, I think that…
joan capell
  • 140
  • 2
  • 8
4
votes
1 answer

What would Negamax' initial function call look like were it to minimize root node rather than maximize?

Negamax typically looks like the below: function negamax(node, depth, α, β, color) is if depth = 0 or node is a terminal node then return color × the heuristic value of node childNodes := generateMoves(node) childNodes :=…
gator
  • 3,465
  • 8
  • 36
  • 76
3
votes
2 answers

How to memoize the repeated subtrees of a game tree (a potentially infinite rose tree)?

I am attempting to implement the Negamax algorithm in Haskell. For this, I am representing the future possibilities a game might take in a rose tree (Data.Tree.Forest (depth, move, position)). However, often there are positions that can be reached…
Qqwy
  • 5,214
  • 5
  • 42
  • 83
3
votes
1 answer

Can negamax use an asymmetric evaluation function?

TLDR: I have an asymmetric evaluation function for an implementation of negamax - is that acceptable? Or do I need to make it symmetric? Longer: I'm writing a game AI (for the chess-like board game "Hive") that was using minimax with alpha-beta…
Jon Thysell
  • 377
  • 1
  • 10
2
votes
1 answer

How to make a chess negamax algorithm prefer captures and other good moves found shallower in the decision tree?

Suppose we have the following position (FEN 8/1K6/8/4q2P/8/8/5k2/8 b - - 3 2): My chess engine produces the correct move of Qxh5 when the search depth is below 3. After that, it seems the problem is that it thinks the capture can be made later…
K. Raivio
  • 100
  • 8
2
votes
1 answer

Is there something wrong with my quiescence search?

I keep getting weird behavior in my negamax-based AI when I try to implement QuiesenceSearch. I based it on the pseudo-code from here: int Quiesce( int alpha, int beta ) { int stand_pat = Evaluate(); if( stand_pat >= beta ) return…
Jon Thysell
  • 377
  • 1
  • 10
2
votes
1 answer

Python Negamax Algorithm

I have about as simple of a negamax algorithm as possible, for evaluating positions in Tic Tac Toe. The state of the game is stored as an array in numpy, with X's pieces represented by 1, and O's pieces represented by four. I was testing this just…
Qiri
  • 251
  • 1
  • 2
  • 10
2
votes
0 answers

Bug in negamax algorithm related to evaluation function? Works some times, not others

I'm trying to develop a Tic-Tac-Toe game with an unbeatable AI and am at a point where my negamax function returns correct output most of the time. At times, though, under certain predictable conditions, the computer chooses a board move that…
Daabd00b
  • 21
  • 2
2
votes
1 answer

Trouble with Negamax game of Nim

I'm taking my first AI class and attempting to implement the NegaMax algorithm into my code in c. I am using this algorithm to play the simple game of Nim, where each player removes 1-3 matches on their turn. The computer plays against itself here.…
Delaney Warren
  • 23
  • 3
2
votes
1 answer

Adding Alpha Beta pruning to Negamax in Java

I am making a chess game in Java and (I think) have successfully implemented Negamax for the AI player. I am having some trouble adding alpha beta pruning to this to improve the algorithm. I have tried following tutorials and example code but just…
P. Brew
  • 734
  • 4
  • 12
2
votes
1 answer

Chess negamax algorithm moves pieces back and forth. What's wrong?

Okay, so I'll admit up front this one's going to be a bit long. I'm writing a chess engine for C#, with the eventual goal including UCI implementation. I've got it to the point where, given a board, the engine will generate a list of all valid…
furrysalamander
  • 183
  • 1
  • 1
  • 9
2
votes
1 answer

Tic Tac Toe negamax implementation.

I'm trying to implement the negamax search function for a tic-tac-toe application, but it does not return the optimal values, instead it appears to guess semi-randomly. Here's the relevant part of my code: public int negamax(Result result, Token…
stensootla
  • 13,945
  • 9
  • 45
  • 68
2
votes
1 answer

Negamax chess algorithm: How to use final return?

I've made a negamax algorithm for a chess-like game and I want to know how to use the final board value result. I understand the final return of the negamax algorithm represents what the board value will be after the player takes his best possible…
user3047181
1
2 3 4 5