SSS*

From HandWiki

SSS* is a search algorithm introduced by George Stockman in 1979. It conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm.

SSS* is based on the notion of solution trees. Informally, a solution tree can be formed from any arbitrary game tree by pruning the number of branches at each MAX node to one. Such a tree represents a complete strategy for MAX, since it specifies exactly one MAX action for every possible sequence of moves made by the opponent. Given a game tree, SSS* searches through the space of partial solution trees, gradually analyzing larger and larger subtrees, eventually producing a single solution tree with the same root and Minimax value as the original game tree. SSS* never examines a node that alpha–beta pruning would prune, and may prune some branches that alpha–beta would not. Stockman speculated that SSS* may therefore be a better general algorithm than alpha–beta. However, Igor Roizen and Judea Pearl have shown[1] that the savings in the number of positions that SSS* evaluates relative to alpha/beta is limited and generally not enough to compensate for the increase in other resources (e.g., the storing and sorting of a list of nodes made necessary by the best-first nature of the algorithm). However, Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin have shown that a sequence of null-window alpha–beta calls is equivalent to SSS* (i.e., it expands the same nodes in the same order) when alpha–beta is used with a transposition table, as is the case in all game-playing programs for chess, checkers, etc. Now the storing and sorting of the OPEN list were no longer necessary. This allowed the implementation of (an algorithm equivalent to) SSS* in tournament quality game-playing programs. Experiments showed that it did indeed perform better than Alpha–Beta in practice, but that it did not beat NegaScout.[2]

The reformulation of a best-first algorithm as a sequence of depth-first calls prompted the formulation of a class of null-window alpha–beta algorithms, of which MTD(f) is the best known example.

Algorithm

There is a priority queue OPEN that stores states (J,s,h) or the nodes, where J - node identificator (Dot-decimal notation is used to identify nodes, ϵ is a root), s∈{L,S} - state of the node J (L - the node is live, which means it's not solved yet and S - the node is solved), h∈(−∞,∞) - value of the solved node. Items in OPEN queue are sorted descending by their h value. If more than one node has the same value of h, a node left-most in the tree is chosen. 

OPEN := { (e, L, inf) }
while true do   // repeat until stopped
    pop an element p=(J, s, h) from the head of the OPEN queue
    if J = e and s = S then
        STOP the algorithm and return h as a result
    else
        apply Gamma operator for p

Γ operator for p=(J,s,h) is defined in the following way: 

if s = L then
    if J is a terminal node then
        (1.) add (J, S, min(h, value(J))) to OPEN
    else if J is a MIN node then
        (2.) add (J.1, L, h) to OPEN
    else
        (3.) for j=1..number_of_children(J) add (J.j, L, h) to OPEN
else
    if J is a MIN node then
        (4.) add (parent(J), S, h) to OPEN
             remove from OPEN all the states that are associated with the children of parent(J)
    else if is_last_child(J) then   // if J is the last child of parent(J)
        (5.) add (parent(J), S, h) to OPEN
    else
        (6.) add (parent(J).(k+1), L, h) to OPEN   // add state associated with the next child of parent(J) to OPEN

References

  1. ↑ Roizen, Igor; Judea Pearl (March 1983). "A minimax algorithm better than alpha–beta?: Yes and No". Artificial Intelligence 21 (1–2): 199–220. doi:10.1016/s0004-3702(83)80010-1. 
  2. ↑ Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (November 1996). "Best-first Fixed-depth Minimax Algorithms". Artificial Intelligence 87 (1–2): 255–293. doi:10.1016/0004-3702(95)00126-3. 

Template:Graph traversal algorithms

Short description: SIMD instruction set

Supplemental Streaming SIMD Extensions 3 (SSSE3 or SSE3S) is a SIMD instruction set created by Intel and is the fourth iteration of the SSE technology.

History

SSSE3 was first introduced with Intel processors based on the Core microarchitecture on June 26, 2006 with the "Woodcrest" Xeons.

SSSE3 has been referred to by the codenames Tejas New Instructions (TNI) or Merom New Instructions (MNI) for the first processor designs intended to support it.

SSSE3 has enhanced for HD audio/video decoding/encoding, for example AAC.

Functionality

SSSE3 contains 16 new discrete instructions. Each instruction can act on 64-bit MMX or 128-bit XMM registers. Therefore, Intel's materials refer to 32 new instructions. They include:[1]

  • Twelve instructions that perform horizontal addition or subtraction operations.
  • Six instructions that evaluate absolute values.
  • Two instructions that perform multiply-and-add operations and speed up the evaluation of dot products.
  • Two instructions that accelerate packed integer multiply operations and produce integer values with scaling.
  • Two instructions that perform a byte-wise, in-place shuffle according to the second shuffle control operand.
  • Six instructions that negate packed integers in the destination operand if the corresponding element in the source operand is negative.
  • Two instructions that align data from the composite of two operands.

CPUs with SSSE3

New instructions

In the table below, satsw(X) (read as 'saturate to signed word') takes a signed integer X, and converts it to −32768 if it is less than −32768, to +32767 if it is greater than 32767, and leaves it unchanged otherwise. As normal for the Intel architecture, bytes are 8 bits, words 16 bits, and dwords 32 bits; 'register' refers to an MMX or XMM vector register.[1]

Instruction Definition Explanation
PSIGNB, PSIGNW, PSIGND Packed Sign Negate the elements of a register of bytes, words or dwords if the sign of the corresponding elements of another register is negative.
PABSB, PABSW, PABSD Packed Absolute Value Fill the elements of a register of bytes, words or dwords with the absolute values of the elements of another register
PALIGNR Packed Align Right take two registers, concatenate their values, and pull out a register-length section from an offset given by an immediate value encoded in the instruction.
PSHUFB Packed Shuffle Bytes takes registers of bytes A = [a0 a1 a2 ...] and B = [b0 b1 b2 ...] and replaces A with [ab0 ab1 ab2 ...]; except that it replaces the ith entry with 0 if the top bit of bi is set.
PMULHRSW Packed Multiply High with Round and Scale treat the 16-bit words in registers A and B as signed 16-bit fixed-point numbers between −1.00000000 and +0.99996948... (e.g. 0x4000 is treated as +0.5 and 0xA000 as −0.75), and multiply them together with correct rounding.
PMADDUBSW Multiply and Add Packed Signed and Unsigned Bytes Take the bytes in registers A and B, multiply them together, add pairs, signed-saturate and store. I.e. [a0 a1 a2 ...] PMADDUBSW [b0 b1 b2 ...] = [satsw(a0b0 + a1b1) satsw(a2b2 + a3b3) ...]
PHSUBW, PHSUBD Packed Horizontal Subtract (Words or Doublewords) takes registers A = [a0 a1 a2 ...] and B = [b0 b1 b2 ...] and outputs [a0−a1 a2−a3 ... b0−b1 b2−b3 ...]
PHSUBSW Packed Horizontal Subtract and Saturate Words like PHSUBW, but outputs [satsw(a0−a1) satsw(a2−a3) ... satsw(b0−b1) satsw(b2−b3) ...]
PHADDW, PHADDD Packed Horizontal Add (Words or Doublewords) takes registers A = [a0 a1 a2 ...] and B = [b0 b1 b2 ...] and outputs [a0+a1 a2+a3 ... b0+b1 b2+b3 ...]
PHADDSW Packed Horizontal Add and Saturate Words like PHADDW, but outputs [satsw(a0+a1) satsw(a2+a3) ... satsw(b0+b1) satsw(b2+b3) ...]

See also

References

  1. ↑ 1.0 1.1 "2.9.5". Intel 64 and IA-32 Architectures Optimization Reference Manual (PDF) (Technical report). Intel.com. 2016. pp. 92–93. Archived (PDF) from the original on June 20, 2018. Retrieved June 22, 2018.

Warning: Default sort key "Ssse3" overrides earlier default sort key "SSS".



Retrieved from "https://handwiki.org/wiki/index.php?title=SSS*&oldid=3978959"