Igor Steinberg

From Chessprogramming wiki
Jump to: navigation, search

Home * People * Igor Steinberg

Igor Steinberg [1]

Igor Steinberg,
an American computer scientist, solution architect, teacher, and program manager, with director-level IT executive experience in the higher education, government, and private sector [2]. He holds a Ph.D. from University of Wisconsin-Madison in 1991 on the topic of parallel game tree search [3], and researched and published along with his thesis advisor Marvin Solomon on a parallel game tree search algorithm dubbed ER (Evaluate and Refute) algorithm.

Algorithm ER

Abstract

Abstract of Searching Game Trees in Parallel [4]

We present a new parallel game-tree search algorithm. Our approach classifies a processor's available work as either mandatory (necessary for the solution) or speculative (may be necessary for the solution). Due to the nature of parallel game tree search, it is not possible to keep all processors busy with mandatory work. Our algorithm ER allows potential speculative work to be dynamically ordered, thereby reducing starvation without incurring an equivalent increase in speculative loss. Measurements of ER's performance on both random trees and trees from an actual game show that at least 16 processors can be applied profitably to a single search. These results contrast with previously published studies, which report a rapid drop-off of efficiency as the number of processors increases. 

Pseudo Code

Negamax C++ like pseudo code implementation of the serial algorithm ER:

struct Node {
  int val;
  bool done;
  vector<Node> childs;
};

int er(Node& p, int α, int β) {
  p.val = α;
  p.childs = generatedChilds(p);
  int d = p.childs.size();
  if (d ==0 ) return staticEval(p);
  for (int i=0; i < d; ++i) {
    int t = -evalFirst(p.childs[i], -β, -p.val);
    if (p.childs[i].done) {
      p.val = max (t, p.val);
      if (p.val >= β) return p.val;
    }
  }
  sort(p.childs);
  for (int i=0; i < d; ++i) {
    if (!p.childs[i].done) {
      int t = -refuteRest(p.childs[i], -β, -p.val);
      p.val = max (t, p.val);
      if (p.val >= β) return p.val;
    }	
  }
  return p.val;
}  
  
int evalFirst(Node& p, int α, int β) {
  p.val = α;
  p.childs = generatedChilds(p);
  int d = p.childs.size();
  if (d ==0 ) {
    p.done = true;
    return staticEval(p);
  } else {
    int t = -er(p.childs[0], -β, -p.val);
    p.val = max (t, p.val);
    p.done = (p.val >= β) || d == 1;
  }
  return p.val;
}
  
int refuteRest(Node p, int α, int β) {
  p.val = α;
  int d = p.childs.size(); // childs already generated in evalFirst
  for (int i=1; i < d; ++i) { 
    int t = -evalFirst(p.childs[i], -β, -p.val);
    if (!p.childs[i].done)
      t = -refuteRest(p.childs[i], -β, -p.val);
    p.val = max (t, p.val);
    if (p.val >= β) return p.val;
  }
  return p.val;
}

Selected Publications

[5]

External Links

References

  1. Igor Steinberg | LinkedIn
  2. Igor Steinberg | LinkedIn
  3. Igor Steinberg (1991). Design and Analysis of Parallel Algorithms for Game-Tree Search. Ph.D. thesis, University of Wisconsin-Madison
  4. Igor Steinberg, Marvin Solomon (1989). Searching Game Trees in Parallel. University of Wisconsin-Madison, Technical report 877, pdf, pdf
  5. dblp: Igor Steinberg

Up one level